From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 6903 invoked by alias); 12 Oct 2004 19:59:45 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 6887 invoked from network); 12 Oct 2004 19:59:44 -0000 Received: from unknown (HELO dberlin.org) (68.164.203.246) by sourceware.org with SMTP; 12 Oct 2004 19:59:44 -0000 Received: from [129.34.20.23] (HELO [9.2.217.169]) by dberlin.org (CommuniGate Pro SMTP 4.2.1) with ESMTP id 7391058 for gcc-patches@gcc.gnu.org; Tue, 12 Oct 2004 15:59:43 -0400 Mime-Version: 1.0 (Apple Message framework v619) To: gcc-patches@gcc.gnu.org Patches Message-Id: <428D46C6-1C89-11D9-B44B-000D93B1B044@dberlin.org> Content-Type: multipart/mixed; boundary=Apple-Mail-4--955100552 From: Daniel Berlin Subject: [PATCH]: Add interchange tests, fix bugs noticed by them Date: Tue, 12 Oct 2004 20:05:00 -0000 X-SW-Source: 2004-10/txt/msg01041.txt.bz2 --Apple-Mail-4--955100552 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; format=flowed Content-length: 851 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 * 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. --Apple-Mail-4--955100552 Content-Transfer-Encoding: 7bit Content-Type: application/octet-stream; x-unix-mode=0664; name="fixesandtests.diff" Content-Disposition: attachment; filename=fixesandtests.diff Content-length: 12346 2004-10-12 Daniel Belin * 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"} } */ --Apple-Mail-4--955100552--