* [PATCH]: Add interchange tests, fix bugs noticed by them
@ 2004-10-12 20:05 Daniel Berlin
0 siblings, 0 replies; only message in thread
From: Daniel Berlin @ 2004-10-12 20:05 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 851 bytes --]
It turns out i forgot to do the new iv creation/computation in the same
type of the old iv.
This fixes that, and adds the missing compute_immediate_uses.
ltrans-2 still fails to decide it wants to interchange, but the rest
succesfully pass.
Bootstrapped and regtested on powerpc-darwin.
2004-10-12 Daniel Belin <dberlin@dberlin.org>
* lambda-code.c (gcc_loopnest_to_lambda_loopnest):
Print out message to dump_file when we convert to perfect nest.
(lbv_to_gcc_expression): Add type argument, and use it for
type of arithmetic.
(lle_to_gcc_expression): Ditto.
(lambda_loopnest_to_gcc_loopnest): Pass type of old induction
variable to lbv/lle_to_gcc_expression.
* tree-loop-linear.c (linear_transform_loops): Compute immediate
uses.
Print out message when we transform loops.
[-- Attachment #2: fixesandtests.diff --]
[-- Type: application/octet-stream, Size: 12346 bytes --]
2004-10-12 Daniel Belin <dberlin@dberlin.org>
* lambda-code.c (gcc_loopnest_to_lambda_loopnest):
Print out message to dump_file when we convert to perfect nest.
(lbv_to_gcc_expression): Add type argument, and use it for
type of arithmetic.
(lle_to_gcc_expression): Ditto.
(lambda_loopnest_to_gcc_loopnest): Pass type of old induction
variable to lbv/lle_to_gcc_expression.
* tree-loop-linear.c (linear_transform_loops): Compute immediate
uses.
Print out message when we transform loops.
Index: lambda-code.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/lambda-code.c,v
retrieving revision 2.13
diff -u -p -r2.13 lambda-code.c
--- lambda-code.c 6 Oct 2004 19:40:54 -0000 2.13
+++ lambda-code.c 12 Oct 2004 19:31:38 -0000
@@ -1520,13 +1520,20 @@ gcc_loopnest_to_lambda_loopnest (struct
VEC_safe_push (lambda_loop, loops, newloop);
temp = temp->inner;
}
- if (need_perfect_nest
- && !perfect_nestify (currloops, loop_nest,
- lboundvars, uboundvars, steps, *inductionvars))
- {
- if (dump_file)
- fprintf (dump_file, "Not a perfect nest and couldn't convert to one.\n");
- return NULL;
+ if (need_perfect_nest)
+ {
+ if (!perfect_nestify (currloops, loop_nest,
+ lboundvars, uboundvars, steps, *inductionvars))
+ {
+ if (dump_file)
+ fprintf (dump_file, "Not a perfect nest and couldn't convert to one.\n");
+ return NULL;
+ }
+ else
+ {
+ if (dump_file)
+ fprintf (dump_file, "Successfully converted loop nest to perfect loop nest.\n");
+ }
}
ret = lambda_loopnest_new (depth, 2 * depth);
for (i = 0; VEC_iterate (lambda_loop, loops, i, newloop); i++)
@@ -1542,7 +1549,7 @@ gcc_loopnest_to_lambda_loopnest (struct
variables for the loop this LBV is from. */
static tree
-lbv_to_gcc_expression (lambda_body_vector lbv,
+lbv_to_gcc_expression (lambda_body_vector lbv, tree type,
VEC (tree) *induction_vars, tree * stmts_to_insert)
{
tree stmts, stmt, resvar, name;
@@ -1551,7 +1558,7 @@ lbv_to_gcc_expression (lambda_body_vecto
/* Create a statement list and a linear expression temporary. */
stmts = alloc_stmt_list ();
- resvar = create_tmp_var (integer_type_node, "lbvtmp");
+ resvar = create_tmp_var (type, "lbvtmp");
add_referenced_tmp_var (resvar);
/* Start at 0. */
@@ -1569,9 +1576,9 @@ lbv_to_gcc_expression (lambda_body_vecto
/* newname = coefficient * induction_variable */
stmt = build (MODIFY_EXPR, void_type_node, resvar,
- fold (build (MULT_EXPR, integer_type_node,
+ fold (build (MULT_EXPR, type,
VEC_index (tree, induction_vars, i),
- build_int_cst (integer_type_node,
+ build_int_cst (type,
LBV_COEFFICIENTS (lbv)[i]))));
newname = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = newname;
@@ -1579,7 +1586,7 @@ lbv_to_gcc_expression (lambda_body_vecto
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
/* name = name + newname */
stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (PLUS_EXPR, integer_type_node, name, newname));
+ build (PLUS_EXPR, type, name, newname));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
tsi = tsi_last (stmts);
@@ -1591,8 +1598,8 @@ lbv_to_gcc_expression (lambda_body_vecto
if (LBV_DENOMINATOR (lbv) != 1)
{
stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (CEIL_DIV_EXPR, integer_type_node,
- name, build_int_cst (integer_type_node,
+ build (CEIL_DIV_EXPR, type,
+ name, build_int_cst (type,
LBV_DENOMINATOR (lbv))));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
@@ -1618,6 +1625,7 @@ lbv_to_gcc_expression (lambda_body_vecto
static tree
lle_to_gcc_expression (lambda_linear_expression lle,
lambda_linear_expression offset,
+ tree type,
VEC(tree) *induction_vars,
VEC(tree) *invariants,
enum tree_code wrap, tree * stmts_to_insert)
@@ -1630,7 +1638,7 @@ lle_to_gcc_expression (lambda_linear_exp
name = NULL_TREE;
/* Create a statement list and a linear expression temporary. */
stmts = alloc_stmt_list ();
- resvar = create_tmp_var (integer_type_node, "lletmp");
+ resvar = create_tmp_var (type, "lletmp");
add_referenced_tmp_var (resvar);
results = VEC_alloc (tree, 1);
@@ -1663,9 +1671,9 @@ lle_to_gcc_expression (lambda_linear_exp
}
else
{
- coeff = build_int_cst (integer_type_node,
+ coeff = build_int_cst (type,
LLE_COEFFICIENTS (lle)[i]);
- mult = fold (build (MULT_EXPR, integer_type_node,
+ mult = fold (build (MULT_EXPR, type,
VEC_index (tree, induction_vars, i),
coeff));
}
@@ -1679,7 +1687,7 @@ lle_to_gcc_expression (lambda_linear_exp
/* name = name + newname */
stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (PLUS_EXPR, integer_type_node,
+ build (PLUS_EXPR, type,
name, newname));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
@@ -1706,9 +1714,9 @@ lle_to_gcc_expression (lambda_linear_exp
}
else
{
- coeff = build_int_cst (integer_type_node,
+ coeff = build_int_cst (type,
LLE_INVARIANT_COEFFICIENTS (lle)[i]);
- mult = fold (build (MULT_EXPR, integer_type_node,
+ mult = fold (build (MULT_EXPR, type,
VEC_index (tree, invariants, i),
coeff));
}
@@ -1722,7 +1730,7 @@ lle_to_gcc_expression (lambda_linear_exp
/* name = name + newname */
stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (PLUS_EXPR, integer_type_node,
+ build (PLUS_EXPR, type,
name, newname));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
@@ -1736,8 +1744,8 @@ lle_to_gcc_expression (lambda_linear_exp
if (LLE_CONSTANT (lle) != 0)
{
stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (PLUS_EXPR, integer_type_node,
- name, build_int_cst (integer_type_node,
+ build (PLUS_EXPR, type,
+ name, build_int_cst (type,
LLE_CONSTANT (lle))));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
@@ -1853,6 +1861,8 @@ lambda_loopnest_to_gcc_loopnest (struct
enum tree_code testtype;
tree newupperbound, newlowerbound;
lambda_linear_expression offset;
+ tree type;
+
/* First, build the new induction variable temporary */
ivvar = create_tmp_var (integer_type_node, "lnivtmp");
@@ -1861,7 +1871,8 @@ lambda_loopnest_to_gcc_loopnest (struct
VEC_safe_push (tree, new_ivs, ivvar);
newloop = LN_LOOPS (new_loopnest)[i];
-
+ type = TREE_TYPE (VEC_index (tree, old_ivs, i));
+
/* Linear offset is a bit tricky to handle. Punt on the unhandled
cases for now. */
offset = LL_LINEAR_OFFSET (newloop);
@@ -1873,6 +1884,7 @@ lambda_loopnest_to_gcc_loopnest (struct
necessary to generate it on the loop preheader. */
newlowerbound = lle_to_gcc_expression (LL_LOWER_BOUND (newloop),
LL_LINEAR_OFFSET (newloop),
+ type,
new_ivs,
invariants, MAX_EXPR, &stmts);
bsi_insert_on_edge (loop_preheader_edge (temp), stmts);
@@ -1881,6 +1893,7 @@ lambda_loopnest_to_gcc_loopnest (struct
basic block of the exit condition */
newupperbound = lle_to_gcc_expression (LL_UPPER_BOUND (newloop),
LL_LINEAR_OFFSET (newloop),
+ type,
new_ivs,
invariants, MIN_EXPR, &stmts);
exitcond = get_loop_exit_condition (temp);
@@ -1936,7 +1949,8 @@ lambda_loopnest_to_gcc_loopnest (struct
lbv = lambda_body_vector_new (depth);
LBV_COEFFICIENTS (lbv)[i] = 1;
lbv = lambda_body_vector_compute_new (transform, lbv);
- newiv = lbv_to_gcc_expression (lbv, new_ivs, &stmts);
+ newiv = lbv_to_gcc_expression (lbv, TREE_TYPE (oldiv),
+ new_ivs, &stmts);
bsi = stmt_for_bsi (stmt);
/* Insert the statements to build that
expression. */
Index: tree-loop-linear.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-loop-linear.c,v
retrieving revision 2.2
diff -u -p -r2.2 tree-loop-linear.c
--- tree-loop-linear.c 16 Sep 2004 16:16:14 -0000 2.2
+++ tree-loop-linear.c 12 Oct 2004 19:31:38 -0000
@@ -240,6 +240,8 @@ linear_transform_loops (struct loops *lo
{
unsigned int i;
+ compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
+
for (i = 1; i < loops->num; i++)
{
unsigned int depth = 0;
@@ -359,6 +361,8 @@ linear_transform_loops (struct loops *lo
}
lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
after, trans);
+ if (dump_file)
+ fprintf (dump_file, "Successfully transformed loop according to matrix\n");
oldivs = NULL;
invariants = NULL;
free_dependence_relations (dependence_relations);
Index: testsuite/gcc.dg/tree-ssa/ltrans-1.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/ltrans-1.c
diff -N testsuite/gcc.dg/tree-ssa/ltrans-1.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/tree-ssa/ltrans-1.c 12 Oct 2004 19:31:38 -0000
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftree-loop-linear -fdump-tree-ltrans-all" } */
+
+double u[1782225];
+int foo(int N, int *res)
+{
+ int i, j;
+ double sum = 0.0;
+ /* This loop should be converted to a perfect nest and
+ interchanged. */
+ for (i = 0; i < N; i++)
+ {
+ for (j = 0; j < N; j++)
+ sum = sum + u[i + 1335 * j];
+
+ u[1336 * i] *= 2;
+ }
+ *res = sum + N;
+}
+/* { dg-final { scan-tree-dump-times "converted loop nest to perfect
+ loop nest" 1 "ltrans"} } */
+/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} } */
Index: testsuite/gcc.dg/tree-ssa/ltrans-2.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/ltrans-2.c
diff -N testsuite/gcc.dg/tree-ssa/ltrans-2.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/tree-ssa/ltrans-2.c 12 Oct 2004 19:31:38 -0000
@@ -0,0 +1,24 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftree-loop-linear -fdump-tree-ltrans-all" } */
+
+double u[1782225];
+int foo(int N, int *res)
+{
+ unsigned int i, j;
+ double sum = 0;
+
+ /* This loop should be converted to a perfect nest and
+ interchanged. */
+ for (i = 0; i < N; i++)
+ {
+ for (j = 0; j < N; j++)
+ {
+ sum = sum + u[i + 1335 * j];
+ if (j == N - 1)
+ u[1336 * i] *= 2;
+ }
+ }
+ *res = sum + N;
+}
+/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} {
+ xfail *-*-*} } */
Index: testsuite/gcc.dg/tree-ssa/ltrans-3.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/ltrans-3.c
diff -N testsuite/gcc.dg/tree-ssa/ltrans-3.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/tree-ssa/ltrans-3.c 12 Oct 2004 19:31:38 -0000
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftree-loop-linear -fdump-tree-ltrans-all" } */
+
+double u[1782225];
+int foo(int N, int *res)
+{
+ unsigned int i, j;
+ double sum = 0;
+ for (i = 0; i < N; i++)
+ {
+ for (j = 0; j < N; j++)
+ {
+ sum = sum + u[i + 1335 * j];
+ }
+ }
+ *res = sum + N;
+}
+
+/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} } */
Index: testsuite/gcc.dg/tree-ssa/ltrans-4.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/ltrans-4.c
diff -N testsuite/gcc.dg/tree-ssa/ltrans-4.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/tree-ssa/ltrans-4.c 12 Oct 2004 19:31:38 -0000
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O20 -ftree-loop-linear -fdump-tree-ltrans-all" } */
+
+double u[1782225];
+int foo(int N, int *res)
+{
+ int i, j;
+ double sum = 0;
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ sum = sum + u[i + 1335 * j];
+
+ for (i = 0; i < N; i++)
+ u[1336 * i] *= 2;
+ *res = sum + N;
+}
+
+/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} } */
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2004-10-12 19:59 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-10-12 20:05 [PATCH]: Add interchange tests, fix bugs noticed by them 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).