* [lno] Simple heuristics for loop interchange (call for twiddling)
@ 2004-07-25 13:26 Sebastian Pop
2004-07-25 14:52 ` Daniel Berlin
2004-07-26 19:14 ` Sebastian Pop
0 siblings, 2 replies; 4+ messages in thread
From: Sebastian Pop @ 2004-07-25 13:26 UTC (permalink / raw)
To: gcc-patches, dberlin
Hi,
In the distance vectors one finds the information about how often a
data reference is reused (how many iterations we have to wait until
the data referenced is used again). This patch uses a very dumb
heuristic, maybe not very useful in the way it is in this patch, but
maybe with the help of experiments could be improved. Basically the
function that computes the profitability is sum_distances_on_loop.
Using this function could be non profitable in some strange cases,
when some of the distances are huge, thus if somebody wants to play
with it and propose better heuristics, welcome!
Dan, could you verify that the comments that I've added or fixed are
correct? Thanks.
Bootstrapped on i686-pc-linux-gnu with BOOT_CFLAGS="-O2 -g
-ftree-loop-linear".
Sebastian
* lambda-code.c (lambda_transform_legal_p): Add more comments.
* lambda-mat.c (lambda_matrix_col_add): Fix comment.
(lambda_matrix_hermite): Add more comments.
* tree-loop-linear.c (sum_distances_on_loop,
try_interchange_loops): New.
(linear_transform_loops): Use try_interchange_loops.
Index: lambda-code.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/lambda-code.c,v
retrieving revision 1.1.2.14
diff -d -u -p -r1.1.2.14 lambda-code.c
--- lambda-code.c 6 Jul 2004 19:25:08 -0000 1.1.2.14
+++ lambda-code.c 24 Jul 2004 17:43:09 -0000
@@ -1947,7 +1947,17 @@ lambda_deps_positive (lambda_vector dir,
/* Return true if TRANS is a legal transformation matrix that respects
- the dependence vectors in DISTS and DIRS. */
+ the dependence vectors in DISTS and DIRS.
+
+ "Wolfe proves that a unimodular transformation represented by the
+ matrix T is legal when applied to a loop nest with a set of
+ lexicographically non-negative distance vectors RDG if and only if
+ for each vector d in RDG, (T.d >= 0) is lexicographically positive.
+ ie.: if and only if it transforms the lexicographically positive
+ distance vectors to lexicographically positive vectors. Note that
+ a unimodular matrix must transform the zero vector (and only it) to
+ the zero vector." S.Muchnick. */
+
bool
lambda_transform_legal_p (lambda_trans_matrix trans,
int nb_loops,
Index: lambda-mat.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/lambda-mat.c,v
retrieving revision 1.1.2.3
diff -d -u -p -r1.1.2.3 lambda-mat.c
--- lambda-mat.c 28 Jun 2004 19:59:58 -0000 1.1.2.3
+++ lambda-mat.c 24 Jul 2004 17:43:09 -0000
@@ -232,7 +232,7 @@ lambda_matrix_col_exchange (lambda_matri
}
/* Add a multiple of column C1 of matrix MAT with M rows to column C2:
- C2 = C1 + CONST1 * C2. */
+ C2 = C2 + CONST1 * C1. */
void
lambda_matrix_col_add (lambda_matrix mat, int m, int c1, int c2, int const1)
@@ -413,7 +413,7 @@ lambda_matrix_inverse_hard (lambda_matri
}
/* Decompose MAT to a product of a lower triangular H and a unimodular
- U matrix. */
+ U matrix such that MAT = H.U. N is the size of the rows of MAT. */
void
lambda_matrix_hermite (lambda_matrix mat, int n,
Index: tree-loop-linear.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-loop-linear.c,v
retrieving revision 1.1.2.8
diff -d -u -p -r1.1.2.8 tree-loop-linear.c
--- tree-loop-linear.c 28 Jun 2004 19:59:58 -0000 1.1.2.8
+++ tree-loop-linear.c 24 Jul 2004 17:43:12 -0000
@@ -55,6 +55,71 @@ Software Foundation, 59 Temple Place - S
transform matrix for locality purposes.
TODO: Completion of partial transforms. */
+/* Returns the sum of all the data dependence distances carried by
+ loop COL. */
+
+static int
+sum_distances_on_loop (varray_type dists,
+ unsigned int loop_number)
+{
+ int res = 0;
+ unsigned int i;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (dists); i++)
+ {
+ lambda_vector distance = VARRAY_GENERIC_PTR (dists, i);
+ res += distance[loop_number];
+ }
+
+ return res;
+}
+
+/* Apply to TRANS any loop interchange that minimize inner loop steps.
+ Returns the new transform matrix. The smaller the reuse vector
+ distances in the inner loops, the fewer the cache misses. */
+
+static lambda_trans_matrix
+try_interchange_loops (lambda_trans_matrix trans,
+ unsigned int depth,
+ varray_type classic_dir,
+ varray_type classic_dist)
+{
+ unsigned int loop_i, loop_j;
+ int sum_i, sum_j;
+
+ for (loop_i = 0; loop_i < depth; loop_i++)
+ for (loop_j = 0; loop_j < depth; loop_j++)
+ {
+ if (loop_i != loop_j)
+ {
+ /* Try to permute rows LOOP_I and LOOP_J. The basic
+ profitability model is the minimization of the steps in
+ the inner loops. */
+ sum_i = sum_distances_on_loop (classic_dist, loop_i);
+ sum_j = sum_distances_on_loop (classic_dist, loop_j);
+
+ /* When LOOP_I contains smaller steps than LOOP_J, and
+ LOOP_I is outer than LOOP_J, then interchange
+ loops. */
+ if (sum_i < sum_j
+ && loop_i < loop_j)
+ lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
+
+ /* Validate the resulting matrix. When the transformation
+ is not valid, reverse to the previous matrix.
+
+ FIXME: In this case of transformation it could be
+ faster to verify the validity of the interchange
+ without applying the transform to the matrix. But for
+ the moment do it cleanly: this is just a prototype. */
+ if (!lambda_transform_legal_p (trans, depth, classic_dir, classic_dist))
+ lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
+ }
+ }
+
+ return trans;
+}
+
/* Perform a set of linear transforms on LOOPS. */
void
@@ -143,6 +208,7 @@ linear_transform_loops (struct loops *lo
trans = lambda_trans_matrix_new (depth, depth);
#if 1
lambda_matrix_id (LTM_MATRIX (trans), depth);
+ trans = try_interchange_loops (trans, depth, classic_dir, classic_dist);
#else
/* This is a 2x2 interchange matrix. */
LTM_MATRIX (trans)[0][0] = 0;
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [lno] Simple heuristics for loop interchange (call for twiddling)
2004-07-25 13:26 [lno] Simple heuristics for loop interchange (call for twiddling) Sebastian Pop
@ 2004-07-25 14:52 ` Daniel Berlin
2004-07-26 19:14 ` Sebastian Pop
1 sibling, 0 replies; 4+ messages in thread
From: Daniel Berlin @ 2004-07-25 14:52 UTC (permalink / raw)
To: Sebastian Pop; +Cc: gcc-patches
On Jul 24, 2004, at 12:41 PM, Sebastian Pop wrote:
> Hi,
>
> In the distance vectors one finds the information about how often a
> data reference is reused (how many iterations we have to wait until
> the data referenced is used again). This patch uses a very dumb
> heuristic, maybe not very useful in the way it is in this patch, but
> maybe with the help of experiments could be improved. Basically the
> function that computes the profitability is sum_distances_on_loop.
> Using this function could be non profitable in some strange cases,
> when some of the distances are huge, thus if somebody wants to play
> with it and propose better heuristics, welcome!
>
> Dan, could you verify that the comments that I've added or fixed are
> correct? Thanks.
>
They are.
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [lno] Simple heuristics for loop interchange (call for twiddling)
2004-07-25 13:26 [lno] Simple heuristics for loop interchange (call for twiddling) Sebastian Pop
2004-07-25 14:52 ` Daniel Berlin
@ 2004-07-26 19:14 ` Sebastian Pop
2004-07-26 22:35 ` Daniel Berlin
1 sibling, 1 reply; 4+ messages in thread
From: Sebastian Pop @ 2004-07-26 19:14 UTC (permalink / raw)
To: gcc-patches, dberlin
Hi,
This patch slightly cleans the code for computing the data dependence
graph. Now we build as some months ago the whole graph including
read-read relations, because these relations are used by the heuristic
for loop interchange.
This patch also cleans the validation of a linear transform matrix.
Dan could you verify that I have it right? Thanks.
The patch introduces a second heuristic for loop interchange: keep in
the inner loops as much dependences not carried by the inner loop as
possible. The relations that fall into this case have a zero distance
on a loop, meaning that they are reused at each iteration of the loop.
This could also lead to better parallelisation/vectorization of inner
loops, though I'm not sure if this catches enough real cases... we
should tune these heuristics on some known benchmarks ;-), but so far
I didn't tested.
Bootstrapped as before on i686 with same BOOT_CFLAGS.
Seb
? temporal.c
Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.234
diff -d -u -p -r1.1.2.234 ChangeLog.lno
--- ChangeLog.lno 24 Jul 2004 18:07:40 -0000 1.1.2.234
+++ ChangeLog.lno 26 Jul 2004 05:02:09 -0000
@@ -1,3 +1,45 @@
+2004-07-25 Sebastian Pop <pop@cri.ensmp.fr>
+
+ * Makefile.in (LAMBDA_H, TREE_DATA_REF_H): New.
+ (tree-ssa-loop.o, tree-data-ref.o, tree-vectorizer.o,
+ tree-loop-linear.o, lambda-code.o): Depend on TREE_DATA_REF_H.
+ (GTFILES): tree-data-ref.h no longer GTYfied.
+ * lambda-code.c (dir_dist_pair, reverse_dep, lambda_dep_mult_constant,
+ lambda_dep_add, lambda_vec_distdirvec_mult, lambda_vec_distdirmat_mult,
+ lambda_deps_positive): Removed.
+ (lambda_vector_lexico_pos): New.
+ (lambda_transform_legal_p): Use lambda_vector_lexico_pos. Use the
+ information from dependence_relations instead of classic_dist, and
+ classic_dir vectors.
+ * lambda.h (lambda_transform_legal_p): Pass in parameter only the
+ dependence_relations varray.
+ * tree-data-ref.c (build_classic_dist_vector,
+ build_classic_dir_vector): Store in the dependence_relations the
+ information. Each arc in the dependence_relations graph is labelled
+ with the distance and direction vectors.
+ (compute_rw_wr_ww_dependences): Renamed again compute_all_dependences.
+ Now computes again the whole dependence graph including read-read
+ relations.
+ (compute_data_dependences_for_loop): Now dependence_relations contains
+ all the data, and thus it doesn't need to initialize the classic_dir
+ and classic_dist vectors.
+ (analyze_all_data_dependences): Adjusted for using the new interface of
+ compute_data_dependences_for_loop. Remove the statistics dump.
+ * tree-data-ref.h: Include lambda.h.
+ (subscript, data_dependence_relation): Remove GTYfier.
+ (data_dependence_relation): Add dir_vect and dist_vect fields.
+ (DDR_DIR_VECT, DDR_DIST_VECT): New.
+ (compute_data_dependences_for_loop): Adjust parameters.
+ * tree-loop-linear.c (sum_distances_on_loop): Renamed
+ gather_interchange_stats. Pass in the dependence_relations.
+ Now is able to sum also on read-read relations. Gather also
+ the number of dependences that are not carried by the loop.
+ (try_interchange_loops): Careful on unknown dependence relations.
+ Use the new interface of lambda_transform_legal_p. Add a heuristic
+ based on the number of dependence relations not carried by a loop.
+ (linear_transform_loops): Adjusted for the new interfaces of
+ compute_data_dependences_for_loop and lambda_transform_legal_p.
+
2004-07-24 Sebastian Pop <pop@cri.ensmp.fr>
* lambda-code.c (lambda_transform_legal_p): Add more comments.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.158.2.42
diff -d -u -p -r1.903.2.158.2.42 Makefile.in
--- Makefile.in 18 Jul 2004 23:12:08 -0000 1.903.2.158.2.42
+++ Makefile.in 26 Jul 2004 05:02:09 -0000
@@ -730,6 +730,8 @@ PRETTY_PRINT_H = pretty-print.h input.h
DIAGNOSTIC_H = diagnostic.h diagnostic.def $(PRETTY_PRINT_H)
C_PRETTY_PRINT_H = $(PRETTY_PRINT_H) $(C_COMMON_H) $(TREE_H)
SCEV_H = tree-scalar-evolution.h $(GGC_H) tree-chrec.h
+LAMBDA_H = lambda.h $(GGC_H)
+TREE_DATA_REF_H = tree-data-ref.h $(LAMBDA_H)
#\f
# Now figure out from those variables how to compile and link.
@@ -1684,7 +1686,7 @@ tree-eh.o : tree-eh.c $(TREE_FLOW_H) $(C
tree-ssa-loop.o : tree-ssa-loop.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) tree-inline.h \
output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
- tree-pass.h flags.h $(SCEV_H) tree-vectorizer.h function.h
+ tree-pass.h flags.h $(SCEV_H) tree-vectorizer.h function.h $(TREE_DATA_REF_H)
tree-ssa-loop-unswitch.o : tree-ssa-loop-unswitch.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) domwalk.h $(PARAMS_H)\
output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
@@ -1752,7 +1754,7 @@ tree-scalar-evolution.o: tree-scalar-evo
tree-data-ref.o: tree-data-ref.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
errors.h $(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) diagnostic.h \
$(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) cfgloop.h \
- tree-data-ref.h $(SCEV_H) tree-pass.h lambda.h
+ $(TREE_DATA_REF_H) $(SCEV_H) tree-pass.h
tree-elim-check.o: tree-elim-check.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
errors.h $(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) diagnostic.h \
$(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) cfgloop.h $(SCEV_H) \
@@ -1760,11 +1762,11 @@ tree-elim-check.o: tree-elim-check.c $(C
tree-vectorizer.o: tree-vectorizer.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
errors.h $(GGC_H) $(OPTABS_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) diagnostic.h \
$(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) cfgloop.h tree-pass.h \
- tree-vectorizer.h tree-data-ref.h $(SCEV_H)
+ tree-vectorizer.h $(TREE_DATA_REF_H) $(SCEV_H)
tree-loop-linear.o: tree-loop-linear.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
errors.h $(GGC_H) $(OPTABS_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) diagnostic.h \
$(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) cfgloop.h tree-pass.h \
- tree-data-ref.h $(SCEV_H)
+ $(TREE_DATA_REF_H) $(SCEV_H)
tree-gimple.o : tree-gimple.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) $(EXPR_H) \
$(RTL_H) $(TREE_GIMPLE_H) $(TM_H) coretypes.h bitmap.h $(GGC_H)
tree-mudflap.o : $(CONFIG_H) errors.h $(SYSTEM_H) $(TREE_H) tree-inline.h \
@@ -1942,7 +1944,7 @@ lambda-trans.o: lambda-trans.c lambda.h
lambda-code.o: lambda-code.c lambda.h $(GGC_H) $(SYSTEM_H) $(CONFIG_H) \
errors.h $(TM_H) $(OPTABS_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) diagnostic.h \
$(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) cfgloop.h \
- tree-data-ref.h $(SCEV_H)
+ $(TREE_DATA_REF_H) $(SCEV_H)
resource.o : resource.c $(CONFIG_H) $(RTL_H) hard-reg-set.h $(SYSTEM_H) coretypes.h \
$(TM_H) $(BASIC_BLOCK_H) $(REGS_H) $(FLAGS_H) output.h $(RESOURCE_H) function.h toplev.h \
$(INSN_ATTR_H) except.h $(PARAMS_H) $(TM_P_H)
@@ -2397,7 +2399,7 @@ GTFILES = $(srcdir)/input.h $(srcdir)/co
$(srcdir)/dbxout.c $(srcdir)/dwarf2out.c $(srcdir)/dwarf2asm.c \
$(srcdir)/dojump.c \
$(srcdir)/emit-rtl.c $(srcdir)/except.c $(srcdir)/explow.c $(srcdir)/expr.c \
- $(srcdir)/fold-const.c $(srcdir)/function.c $(srcdir)/tree-data-ref.h \
+ $(srcdir)/fold-const.c $(srcdir)/function.c \
$(srcdir)/gcse.c $(srcdir)/integrate.c $(srcdir)/lists.c $(srcdir)/optabs.c \
$(srcdir)/profile.c $(srcdir)/ra-build.c $(srcdir)/regclass.c \
$(srcdir)/reg-stack.c $(srcdir)/cfglayout.c \
Index: lambda-code.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/lambda-code.c,v
retrieving revision 1.1.2.15
diff -d -u -p -r1.1.2.15 lambda-code.c
--- lambda-code.c 24 Jul 2004 18:07:40 -0000 1.1.2.15
+++ lambda-code.c 26 Jul 2004 05:02:09 -0000
@@ -1761,193 +1761,29 @@ lambda_loopnest_to_gcc_loopnest (struct
}
}
-/* A data dependence direction and distance pair. */
-
-typedef struct dir_dist_pair
-{
- enum data_dependence_direction dir;
- int dist;
-} dd_pair;
-
-/* If a dependence direction is reversed, reverse_dep[old_direction]
- gives the new direction. MUST BE KEPT IN SYNC WITH enum
- data_dependence_dir.
-*/
-static const enum data_dependence_direction reverse_dep[] =
- {
- dir_negative,
- dir_positive,
- dir_equal,
- dir_positive_or_negative,
- dir_negative_or_equal,
- dir_positive_or_equal,
- dir_star,
- dir_independent
- };
-
-/* Multiply a dependence pair DEP by CONSTANT, return the new
- dependence pair. */
-
-static dd_pair
-lambda_dep_mult_constant (dd_pair dep, int constant)
-{
- dd_pair ret;
- ret.dist = dep.dist * constant;
-
- /* If the distance is now 0, the direction is now equal.
- Otherwise, the direction only changes if the constant is < 0. */
-
- if (ret.dist == 0)
- {
- ret.dir = dir_equal;
- }
- else if (constant < 0)
- {
- ret.dir = reverse_dep[dep.dir];
- }
- else
- {
- ret.dir = dep.dir;
- }
- return ret;
-}
-
-/* Add two dependence pairs, FIRST and SECOND, and return the new
- dependence pair. */
-static dd_pair
-lambda_dep_add (dd_pair first, dd_pair second)
-{
- dd_pair ret;
- ret.dist = first.dist + second.dist;
- switch (first.dir)
- {
- case dir_equal:
- {
- ret.dir = second.dir;
- ret.dist = second.dist;
- break;
- }
- case dir_positive_or_equal:
- case dir_positive:
- {
- switch (second.dir)
- {
- case dir_negative:
- case dir_negative_or_equal:
- case dir_star:
- ret.dir = dir_star;
- ret.dist = 0;
- break;
- default:
- ret.dir = first.dir;
- break;
- }
- break;
- }
- case dir_negative_or_equal:
- case dir_negative:
- {
- switch (second.dir)
- {
- case dir_positive:
- case dir_positive_or_equal:
- case dir_star:
- ret.dir = dir_star;
- ret.dist = 0;
- break;
- default:
- ret.dir = first.dir;
- break;
- }
- break;
- }
- case dir_star:
- {
- ret.dir = dir_star;
- ret.dist = 0;
- break;
- }
- default:
- abort ();
- }
- return ret;
-}
-/* Compute the dot product of an integer vector VECTOR,
- a vector containing dependence distance DISTANCE, and a vector containing
- dependence direction DIRECTION. All vectors are of dimension SIZE.
- Return the resulting distance/direction pair. */
-
-static dd_pair
-lambda_vec_distdirvec_mult (lambda_vector vector,
- lambda_vector distance,
- lambda_vector direction,
- int size)
-{
- int i;
- dd_pair ret;
- ret.dir = dir_equal;
- ret.dist = 0;
- for (i = 0; i < size; i++)
- {
- dd_pair elem;
- elem.dist = distance[i];
- elem.dir = direction[i];
- elem = lambda_dep_mult_constant (elem, vector[i]);
- ret = lambda_dep_add (ret, elem);
- }
- return ret;
-}
-
-/* Compute the dot product of an integer vector VECTOR, and a
- dependence matrix represented by varrays of distance and direction
- vectors, DISTS and DIRS.
- All vectors are of dimension DIM. */
-
-static void
-lambda_vec_distdirmat_mult (lambda_vector vector,
- int dim,
- varray_type dirs,
- varray_type dists,
- lambda_vector dirres,
- lambda_vector distres)
-{
- size_t i;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (dists); i++)
- {
- dd_pair result;
- lambda_vector distance = VARRAY_GENERIC_PTR (dists, i);
- lambda_vector direction = VARRAY_GENERIC_PTR (dirs, i);
- result = lambda_vec_distdirvec_mult (vector, distance, direction, dim);
- distres[i] = result.dist;
- dirres[i] = result.dir;
- }
-
-}
+/* Returns true when the vector V is lexicographically positive, in
+ other words, when the first non zero element is positive. */
-/* Return true if the direction vector DIR is all positive or equal
- elements. */
static bool
-lambda_deps_positive (lambda_vector dir, int dirsize)
+lambda_vector_lexico_pos (lambda_vector v,
+ unsigned n)
{
- int i;
- for (i = 0; i < dirsize; i++)
+ unsigned i;
+ for (i = 0; i < n; i++)
{
- switch (dir[i])
- {
- case dir_negative:
- case dir_negative_or_equal:
- case dir_star:
+ if (v[i] == 0)
+ continue;
+ if (v[i] < 0)
return false;
- break;
- }
+ if (v[i] > 0)
+ return true;
}
return true;
}
-
-
/* Return true if TRANS is a legal transformation matrix that respects
- the dependence vectors in DISTS and DIRS.
+ the dependence vectors in DISTS and DIRS. The conservative answer
+ is false.
"Wolfe proves that a unimodular transformation represented by the
matrix T is legal when applied to a loop nest with a set of
@@ -1961,22 +1797,52 @@ lambda_deps_positive (lambda_vector dir,
bool
lambda_transform_legal_p (lambda_trans_matrix trans,
int nb_loops,
- varray_type dirs,
- varray_type dists)
+ varray_type dependence_relations)
{
- int i;
- int distsize = VARRAY_ACTIVE_SIZE (dists);
- int dirsize = VARRAY_ACTIVE_SIZE (dirs);
+ unsigned int i;
lambda_vector distres;
- lambda_vector dirres;
- distres = lambda_vector_new (distsize);
- dirres = lambda_vector_new (dirsize);
- for (i = 0; i < LTM_ROWSIZE (trans); i++)
+ struct data_dependence_relation *ddr;
+
+#if defined ENABLE_CHECKING
+ if (LTM_COLSIZE (trans) != nb_loops
+ || LTM_ROWSIZE (trans) != nb_loops)
+ abort ();
+#endif
+
+ /* When there is an unknown relation in the dependence_relations, we
+ know that it is no worth looking at this loop nest: give up. */
+ ddr = (struct data_dependence_relation *)
+ VARRAY_GENERIC_PTR (dependence_relations, 0);
+ if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+ return false;
+
+
+ distres = lambda_vector_new (nb_loops);
+
+ /* For each distance vector in the dependence graph. */
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
{
- lambda_vec_distdirmat_mult (LTM_MATRIX (trans)[i], nb_loops,
- dirs, dists, dirres, distres);
- if (!lambda_deps_positive (dirres, dirsize))
+ ddr = (struct data_dependence_relation *)
+ VARRAY_GENERIC_PTR (dependence_relations, i);
+
+ /* Conservatively answer: "this transformation is not valid". */
+ if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+ return false;
+
+ /* Don't care about relations for which we know that there is no
+ dependence, nor about read-read (aka. output-dependences):
+ these data accesses can happen in any order. */
+ if (DDR_ARE_DEPENDENT (ddr) == chrec_known
+ || (DR_IS_READ (DDR_A (ddr)) && DR_IS_READ (DDR_B (ddr))))
+ continue;
+
+ /* Compute trans.dist_vect */
+ lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops,
+ DDR_DIST_VECT (ddr), distres);
+
+ if (!lambda_vector_lexico_pos (distres, nb_loops))
return false;
}
+
return true;
}
Index: lambda.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/lambda.h,v
retrieving revision 1.1.2.4
diff -d -u -p -r1.1.2.4 lambda.h
--- lambda.h 12 Jul 2004 21:18:07 -0000 1.1.2.4
+++ lambda.h 26 Jul 2004 05:02:09 -0000
@@ -22,6 +22,8 @@ Software Foundation, 59 Temple Place - S
#ifndef LAMBDA_H
#define LAMBDA_H
+#include "ggc.h"
+
typedef int *lambda_vector;
typedef lambda_vector *lambda_matrix;
@@ -97,7 +99,7 @@ typedef struct
lambda_loopnest lambda_loopnest_new (int, int);
lambda_loopnest lambda_loopnest_transform (lambda_loopnest, lambda_trans_matrix);
-bool lambda_transform_legal_p (lambda_trans_matrix, int, varray_type, varray_type);
+bool lambda_transform_legal_p (lambda_trans_matrix, int, varray_type);
void print_lambda_loopnest (FILE *, lambda_loopnest, char);
#define lambda_loop_new() (lambda_loop) ggc_alloc_cleared (sizeof (struct lambda_loop_s))
Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.c,v
retrieving revision 1.1.2.29
diff -d -u -p -r1.1.2.29 tree-data-ref.c
--- tree-data-ref.c 22 Jul 2004 12:00:46 -0000 1.1.2.29
+++ tree-data-ref.c 26 Jul 2004 05:02:09 -0000
@@ -94,11 +94,7 @@ Software Foundation, 59 Temple Place - S
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
-#include "lambda.h"
-
-static unsigned int data_ref_id = 0;
-\f
/* This is the simplest data dependence test: determines whether the
data references A and B access the same array/region. If can't determine -
return false; Otherwise, return true, and DIFFER_P will record
@@ -549,7 +545,6 @@ analyze_array (tree stmt, tree ref, bool
res = ggc_alloc (sizeof (struct data_reference));
- DR_ID (res) = data_ref_id++;
DR_STMT (res) = stmt;
DR_REF (res) = ref;
VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 3, "access_fns");
@@ -585,7 +580,6 @@ init_data_ref (tree stmt,
res = ggc_alloc (sizeof (struct data_reference));
- DR_ID (res) = data_ref_id++;
DR_STMT (res) = stmt;
DR_REF (res) = ref;
VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 5, "access_fns");
@@ -1429,14 +1423,12 @@ subscript_dependence_tester (struct data
/* Compute the classic per loop distance vector.
- RES is the data dependence relation to build a vector from.
- CLASSIC_DIST is the varray to place the vector in.
+ 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. */
static void
-build_classic_dist_vector (struct data_dependence_relation *res,
- varray_type *classic_dist,
+build_classic_dist_vector (struct data_dependence_relation *ddr,
int nb_loops, unsigned int first_loop)
{
unsigned i;
@@ -1447,12 +1439,12 @@ build_classic_dist_vector (struct data_d
lambda_vector_clear (dist_v, nb_loops);
lambda_vector_clear (init_v, nb_loops);
- if (DDR_ARE_DEPENDENT (res) != NULL_TREE)
+ if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
return;
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (res); i++)
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
- struct subscript *subscript = DDR_SUBSCRIPT (res, i);
+ struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
return;
@@ -1479,7 +1471,7 @@ build_classic_dist_vector (struct data_d
if (init_v[loop_nb] != 0
&& dist_v[loop_nb] != dist)
{
- finalize_ddr_dependent (res, chrec_known);
+ finalize_ddr_dependent (ddr, chrec_known);
return;
}
@@ -1497,8 +1489,8 @@ build_classic_dist_vector (struct data_d
*/
{
struct loop *lca, *loop_a, *loop_b;
- struct data_reference *a = DDR_A (res);
- struct data_reference *b = DDR_B (res);
+ struct data_reference *a = DDR_A (ddr);
+ struct data_reference *b = DDR_B (ddr);
int lca_nb;
loop_a = loop_containing_stmt (DR_STMT (a));
loop_b = loop_containing_stmt (DR_STMT (b));
@@ -1535,19 +1527,17 @@ build_classic_dist_vector (struct data_d
}
}
- VARRAY_PUSH_GENERIC_PTR (*classic_dist, dist_v);
+ DDR_DIST_VECT (ddr) = dist_v;
}
/* Compute the classic per loop direction vector.
- RES is the data dependence relation to build a vector from.
- CLASSIC_DIR is the varray to place the vector in.
+ 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. */
static void
-build_classic_dir_vector (struct data_dependence_relation *res,
- varray_type *classic_dir,
+build_classic_dir_vector (struct data_dependence_relation *ddr,
int nb_loops, unsigned int first_loop)
{
unsigned i;
@@ -1558,12 +1548,12 @@ build_classic_dir_vector (struct data_de
lambda_vector_clear (dir_v, nb_loops);
lambda_vector_clear (init_v, nb_loops);
- if (DDR_ARE_DEPENDENT (res) != NULL_TREE)
+ if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
return;
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (res); i++)
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
- struct subscript *subscript = DDR_SUBSCRIPT (res, i);
+ struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC
&& TREE_CODE (SUB_CONFLICTS_IN_B (subscript)) == POLYNOMIAL_CHREC)
@@ -1606,7 +1596,7 @@ build_classic_dir_vector (struct data_de
&& (enum data_dependence_direction) dir_v[loop_nb] != dir
&& (enum data_dependence_direction) dir_v[loop_nb] != dir_star)
{
- finalize_ddr_dependent (res, chrec_known);
+ finalize_ddr_dependent (ddr, chrec_known);
return;
}
@@ -1624,8 +1614,8 @@ build_classic_dir_vector (struct data_de
*/
{
struct loop *lca, *loop_a, *loop_b;
- struct data_reference *a = DDR_A (res);
- struct data_reference *b = DDR_B (res);
+ struct data_reference *a = DDR_A (ddr);
+ struct data_reference *b = DDR_B (ddr);
int lca_nb;
loop_a = loop_containing_stmt (DR_STMT (a));
loop_b = loop_containing_stmt (DR_STMT (b));
@@ -1660,7 +1650,7 @@ build_classic_dir_vector (struct data_de
}
}
- VARRAY_PUSH_GENERIC_PTR (*classic_dir, dir_v);
+ DDR_DIR_VECT (ddr) = dir_v;
}
/* Returns true when all the access functions of A are affine or
@@ -1731,8 +1721,8 @@ compute_affine_dependence (struct data_d
in DEPENDENCE_RELATIONS. */
static void
-compute_rw_wr_ww_dependences (varray_type datarefs,
- varray_type *dependence_relations)
+compute_all_dependences (varray_type datarefs,
+ varray_type *dependence_relations)
{
unsigned int i, j, N;
@@ -1747,10 +1737,6 @@ compute_rw_wr_ww_dependences (varray_typ
a = VARRAY_GENERIC_PTR (datarefs, i);
b = VARRAY_GENERIC_PTR (datarefs, j);
- /* Don't compute the "read-read" relations. */
- if (DR_IS_READ (a) && DR_IS_READ (b))
- continue;
-
ddr = initialize_data_dependence_relation (a, b);
VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
@@ -1818,17 +1804,13 @@ find_data_references_in_loop (struct loo
/* Given a loop nest LOOP, the following vectors are returned:
*DATAREFS is initialized to all the array elements contained in this loop,
- *DEPENDENCE_RELATIONS contains the relations between the data references,
- *CLASSIC_DIST contains the set of distance vectors,
- *CLASSIC_DIR contains the set of direction vectors. */
+ *DEPENDENCE_RELATIONS contains the relations between the data references. */
void
compute_data_dependences_for_loop (unsigned nb_loops,
struct loop *loop,
varray_type *datarefs,
- varray_type *dependence_relations,
- varray_type *classic_dist,
- varray_type *classic_dir)
+ varray_type *dependence_relations)
{
unsigned int i;
@@ -1842,19 +1824,19 @@ 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, classic_dist, nb_loops, loop->num);
- build_classic_dir_vector (ddr, classic_dir, nb_loops, loop->num);
+ build_classic_dist_vector (ddr, nb_loops, loop->num);
+ build_classic_dir_vector (ddr, nb_loops, loop->num);
return;
}
- compute_rw_wr_ww_dependences (*datarefs, dependence_relations);
+ compute_all_dependences (*datarefs, dependence_relations);
for (i = 0; i < VARRAY_ACTIVE_SIZE (*dependence_relations); i++)
{
struct data_dependence_relation *ddr;
ddr = VARRAY_GENERIC_PTR (*dependence_relations, i);
- build_classic_dist_vector (ddr, classic_dist, nb_loops, loop->num);
- build_classic_dir_vector (ddr, classic_dir, nb_loops, loop->num);
+ build_classic_dist_vector (ddr, nb_loops, loop->num);
+ build_classic_dir_vector (ddr, nb_loops, loop->num);
}
}
@@ -1886,11 +1868,8 @@ analyze_all_data_dependences (struct loo
unsigned int i;
varray_type datarefs;
varray_type dependence_relations;
- varray_type classic_dist, classic_dir;
int nb_data_refs = 10;
- VARRAY_GENERIC_PTR_INIT (classic_dist, 10, "classic_dist");
- VARRAY_GENERIC_PTR_INIT (classic_dir, 10, "classic_dir");
VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
VARRAY_GENERIC_PTR_INIT (dependence_relations,
nb_data_refs * nb_data_refs,
@@ -1898,8 +1877,7 @@ analyze_all_data_dependences (struct loo
/* Compute DDs on the whole function. */
compute_data_dependences_for_loop (loops->num, loops->parray[0],
- &datarefs, &dependence_relations,
- &classic_dist, &classic_dir);
+ &datarefs, &dependence_relations);
if (dump_file)
{
@@ -1911,20 +1889,16 @@ analyze_all_data_dependences (struct loo
testsuite. */
if (dump_file && (dump_flags & TDF_DETAILS))
{
- for (i = 0; i < VARRAY_ACTIVE_SIZE (classic_dist); i++)
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
{
+ struct data_dependence_relation *ddr =
+ (struct data_dependence_relation *)
+ VARRAY_GENERIC_PTR (dependence_relations, i);
fprintf (dump_file, "DISTANCE_V (");
- print_lambda_vector (dump_file,
- VARRAY_GENERIC_PTR (classic_dist, i),
- loops->num);
+ print_lambda_vector (dump_file, DDR_DIST_VECT (ddr), loops->num);
fprintf (dump_file, ")\n");
- }
- for (i = 0; i < VARRAY_ACTIVE_SIZE (classic_dir); i++)
- {
fprintf (dump_file, "DIRECTION_V (");
- print_lambda_vector (dump_file,
- VARRAY_GENERIC_PTR (classic_dir, i),
- loops->num);
+ print_lambda_vector (dump_file, DDR_DIR_VECT (ddr), loops->num);
fprintf (dump_file, ")\n");
}
fprintf (dump_file, "\n\n");
@@ -1962,21 +1936,11 @@ analyze_all_data_dependences (struct loo
nb_chrec_relations++;
}
- fprintf (dump_file, "\n(\n");
- fprintf (dump_file, "%d\tnb_top_relations\n", nb_top_relations);
- fprintf (dump_file, "%d\tnb_bot_relations\n", nb_bot_relations);
- fprintf (dump_file, "%d\tnb_basename_differ\n", nb_basename_differ);
- fprintf (dump_file, "%d\tnb_distance_relations\n", (int) VARRAY_ACTIVE_SIZE (classic_dist));
- fprintf (dump_file, "%d\tnb_chrec_relations\n", nb_chrec_relations);
- fprintf (dump_file, "\n)\n");
-
gather_stats_on_scev_database ();
}
varray_clear (dependence_relations);
varray_clear (datarefs);
- varray_clear (classic_dist);
- varray_clear (classic_dir);
}
Index: tree-data-ref.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.h,v
retrieving revision 1.1.2.16
diff -d -u -p -r1.1.2.16 tree-data-ref.h
--- tree-data-ref.h 20 Jul 2004 15:11:05 -0000 1.1.2.16
+++ tree-data-ref.h 26 Jul 2004 05:02:09 -0000
@@ -22,7 +22,9 @@ Software Foundation, 59 Temple Place - S
#ifndef GCC_TREE_DATA_REF_H
#define GCC_TREE_DATA_REF_H
-struct data_reference GTY(())
+#include "lambda.h"
+
+struct data_reference
{
/* An identifier. */
unsigned int id;
@@ -74,7 +76,7 @@ enum data_dependence_direction {
are stored in the data_dependence_relation structure under the form
of an array of subscripts. */
-struct subscript GTY(())
+struct subscript
{
/* A description of the iterations for which the elements are
accessed twice. */
@@ -108,7 +110,7 @@ struct subscript GTY(())
/* A data_dependence_relation represents a relation between two
data_references A and B. */
-struct data_dependence_relation GTY(())
+struct data_dependence_relation
{
struct data_reference *a;
@@ -131,6 +133,12 @@ struct data_dependence_relation GTY(())
this array. This is the attribute that labels the edge A->B of
the data_dependence_relation. */
varray_type subscripts;
+
+ /* The classic direction vector. */
+ lambda_vector dir_vect;
+
+ /* The classic distance vector. */
+ lambda_vector dist_vect;
};
#define DDR_A(DDR) DDR->a
@@ -141,6 +149,8 @@ struct data_dependence_relation GTY(())
VARRAY_GENERIC_PTR_INIT (DDR_SUBSCRIPTS (DDR), N, "subscripts_vector");
#define DDR_SUBSCRIPT(DDR, I) VARRAY_GENERIC_PTR (DDR_SUBSCRIPTS (DDR), I)
#define DDR_NUM_SUBSCRIPTS(DDR) VARRAY_ACTIVE_SIZE (DDR_SUBSCRIPTS (DDR))
+#define DDR_DIR_VECT(DDR) DDR->dir_vect
+#define DDR_DIST_VECT(DDR) DDR->dist_vect
\f
@@ -149,7 +159,6 @@ struct data_dependence_relation *initial
void compute_affine_dependence (struct data_dependence_relation *);
extern void analyze_all_data_dependences (struct loops *);
extern void compute_data_dependences_for_loop (unsigned, struct loop *,
- varray_type *, varray_type *,
varray_type *, varray_type *);
extern struct data_reference * init_data_ref (tree, tree, tree, tree, bool);
extern struct data_reference *analyze_array (tree, tree, bool);
Index: tree-loop-linear.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-loop-linear.c,v
retrieving revision 1.1.2.9
diff -d -u -p -r1.1.2.9 tree-loop-linear.c
--- tree-loop-linear.c 24 Jul 2004 18:07:40 -0000 1.1.2.9
+++ tree-loop-linear.c 26 Jul 2004 05:02:09 -0000
@@ -55,23 +55,55 @@ Software Foundation, 59 Temple Place - S
transform matrix for locality purposes.
TODO: Completion of partial transforms. */
-/* Returns the sum of all the data dependence distances carried by
- loop COL. */
+/* Gather statistics for loop interchange. Initializes SUM the sum of
+ all the data dependence distances carried by loop LOOP_NUMBER.
+ NB_DEPS_NOT_CARRIED_BY_LOOP is initialized to the number of
+ dependence relations for which the loop LOOP_NUMBER is not carrying
+ any dependence. */
-static int
-sum_distances_on_loop (varray_type dists,
- unsigned int loop_number)
+static void
+gather_interchange_stats (varray_type dependence_relations,
+ unsigned int loop_number,
+ unsigned int *sum,
+ unsigned int *nb_deps_not_carried_by_loop)
{
- int res = 0;
unsigned int i;
-
- for (i = 0; i < VARRAY_ACTIVE_SIZE (dists); i++)
+
+ *sum = 0;
+ *nb_deps_not_carried_by_loop = 0;
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
{
- lambda_vector distance = VARRAY_GENERIC_PTR (dists, i);
- res += distance[loop_number];
- }
+ int dist;
+ struct data_dependence_relation *ddr =
+ (struct data_dependence_relation *)
+ VARRAY_GENERIC_PTR (dependence_relations, i);
- return res;
+ if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+ {
+ /* FIXME: Some constants to tweak... maybe this could go as
+ a param for fast experimentations? */
+ *sum += 100;
+ continue;
+ }
+
+ /* When we know that there is no dependence, we know that there
+ is no reuse of the data. */
+ if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
+ {
+ /* FIXME: Some constants to tweak... maybe this could go as
+ a param for fast experimentations? */
+ *sum += 1000;
+ continue;
+ }
+
+ dist = DDR_DIST_VECT (ddr)[loop_number];
+ if (dist == 0)
+ *nb_deps_not_carried_by_loop++;
+ else if (dist < 0)
+ *sum += -dist;
+ else
+ *sum += dist;
+ }
}
/* Apply to TRANS any loop interchange that minimize inner loop steps.
@@ -81,40 +113,47 @@ sum_distances_on_loop (varray_type dists
static lambda_trans_matrix
try_interchange_loops (lambda_trans_matrix trans,
unsigned int depth,
- varray_type classic_dir,
- varray_type classic_dist)
+ varray_type dependence_relations)
{
unsigned int loop_i, loop_j;
- int sum_i, sum_j;
+ unsigned int steps_i, steps_j;
+ unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
+ struct data_dependence_relation *ddr;
- for (loop_i = 0; loop_i < depth; loop_i++)
- for (loop_j = 0; loop_j < depth; loop_j++)
+ /* When there is an unknown relation in the dependence_relations, we
+ know that it is no worth looking at this loop nest: give up. */
+ ddr = (struct data_dependence_relation *)
+ VARRAY_GENERIC_PTR (dependence_relations, 0);
+ if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+ return trans;
+
+ /* LOOP_I is always the outer loop. */
+ for (loop_j = 0; loop_j < depth; loop_j++)
+ for (loop_i = 0; loop_i < loop_j; loop_i++)
{
- if (loop_i != loop_j)
- {
- /* Try to permute rows LOOP_I and LOOP_J. The basic
- profitability model is the minimization of the steps in
- the inner loops. */
- sum_i = sum_distances_on_loop (classic_dist, loop_i);
- sum_j = sum_distances_on_loop (classic_dist, loop_j);
-
- /* When LOOP_I contains smaller steps than LOOP_J, and
- LOOP_I is outer than LOOP_J, then interchange
- loops. */
- if (sum_i < sum_j
- && loop_i < loop_j)
- lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
-
- /* Validate the resulting matrix. When the transformation
- is not valid, reverse to the previous matrix.
-
- FIXME: In this case of transformation it could be
- faster to verify the validity of the interchange
- without applying the transform to the matrix. But for
- the moment do it cleanly: this is just a prototype. */
- if (!lambda_transform_legal_p (trans, depth, classic_dir, classic_dist))
- lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
- }
+ gather_interchange_stats (dependence_relations, loop_i, &steps_i,
+ &nb_deps_not_carried_by_i);
+ gather_interchange_stats (dependence_relations, loop_j, &steps_j,
+ &nb_deps_not_carried_by_j);
+
+ /* Heuristics for loop interchange profitability:
+ 1. Inner loops should have smallest steps.
+ 2. Inner loops should contain more dependence relations not
+ carried by the loop.
+ */
+ if (steps_i < steps_j
+ || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j)
+ lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
+
+ /* Validate the resulting matrix. When the transformation
+ is not valid, reverse to the previous matrix.
+
+ FIXME: In this case of transformation it could be
+ faster to verify the validity of the interchange
+ without applying the transform to the matrix. But for
+ the moment do it cleanly: this is just a prototype. */
+ if (!lambda_transform_legal_p (trans, depth, dependence_relations))
+ lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
}
return trans;
@@ -127,9 +166,6 @@ linear_transform_loops (struct loops *lo
{
unsigned int i;
unsigned int depth = 0;
- unsigned int j;
- varray_type classic_dist;
- varray_type classic_dir;
varray_type datarefs;
varray_type dependence_relations;
@@ -174,32 +210,25 @@ linear_transform_loops (struct loops *lo
/* Analyze data references and dependence relations using scev. */
- VARRAY_GENERIC_PTR_INIT (classic_dist, 10, "classic_dist");
- VARRAY_GENERIC_PTR_INIT (classic_dir, 10, "classic_dir");
VARRAY_GENERIC_PTR_INIT (datarefs, 10, "datarefs");
VARRAY_GENERIC_PTR_INIT (dependence_relations, 10,
"dependence_relations");
compute_data_dependences_for_loop (depth, loop_nest,
- &datarefs, &dependence_relations,
- &classic_dist, &classic_dir);
+ &datarefs, &dependence_relations);
if (dump_file && (dump_flags & TDF_DETAILS))
{
- for (j = 0; j < VARRAY_ACTIVE_SIZE (classic_dist); j++)
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
{
+ struct data_dependence_relation *ddr =
+ (struct data_dependence_relation *)
+ VARRAY_GENERIC_PTR (dependence_relations, i);
fprintf (dump_file, "DISTANCE_V (");
- print_lambda_vector (dump_file,
- VARRAY_GENERIC_PTR (classic_dist, j),
- depth);
+ print_lambda_vector (dump_file, DDR_DIST_VECT (ddr), loops->num);
fprintf (dump_file, ")\n");
- }
- for (j = 0; j < VARRAY_ACTIVE_SIZE (classic_dir); j++)
- {
fprintf (dump_file, "DIRECTION_V (");
- print_lambda_vector (dump_file,
- VARRAY_GENERIC_PTR (classic_dir, j),
- depth);
+ print_lambda_vector (dump_file, DDR_DIR_VECT (ddr), loops->num);
fprintf (dump_file, ")\n");
}
fprintf (dump_file, "\n\n");
@@ -208,7 +237,7 @@ linear_transform_loops (struct loops *lo
trans = lambda_trans_matrix_new (depth, depth);
#if 1
lambda_matrix_id (LTM_MATRIX (trans), depth);
- trans = try_interchange_loops (trans, depth, classic_dir, classic_dist);
+ trans = try_interchange_loops (trans, depth, dependence_relations);
#else
/* This is a 2x2 interchange matrix. */
LTM_MATRIX (trans)[0][0] = 0;
@@ -217,7 +246,7 @@ linear_transform_loops (struct loops *lo
LTM_MATRIX (trans)[1][1] = 0;
#endif
/* Check whether the transformation is legal. */
- if (!lambda_transform_legal_p (trans, depth, classic_dir, classic_dist))
+ if (!lambda_transform_legal_p (trans, depth, dependence_relations))
{
if (dump_file)
fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [lno] Simple heuristics for loop interchange (call for twiddling)
2004-07-26 19:14 ` Sebastian Pop
@ 2004-07-26 22:35 ` Daniel Berlin
0 siblings, 0 replies; 4+ messages in thread
From: Daniel Berlin @ 2004-07-26 22:35 UTC (permalink / raw)
To: Sebastian Pop; +Cc: gcc-patches
On Jul 25, 2004, at 11:58 PM, Sebastian Pop wrote:
> Hi,
>
> This patch slightly cleans the code for computing the data dependence
> graph. Now we build as some months ago the whole graph including
> read-read relations, because these relations are used by the heuristic
> for loop interchange.
>
> This patch also cleans the validation of a linear transform matrix.
> Dan could you verify that I have it right? Thanks.
>
Looks right to me.
:)
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2004-07-26 15:30 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-07-25 13:26 [lno] Simple heuristics for loop interchange (call for twiddling) Sebastian Pop
2004-07-25 14:52 ` Daniel Berlin
2004-07-26 19:14 ` Sebastian Pop
2004-07-26 22:35 ` Daniel Berlin
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).