diff options
author | Daniel Berlin <dberlin@dberlin.org> | 2004-11-01 18:08:02 +0000 |
---|---|---|
committer | Daniel Berlin <dberlin@gcc.gnu.org> | 2004-11-01 18:08:02 +0000 |
commit | 464f49d80df8a5232a956a1ccc8ef78bd25b0110 (patch) | |
tree | 13c080b6513fecb915f215d79235d8f610719b6a | |
parent | d68e653fae9b7747fcbdcd4b0722bf62aee2214e (diff) | |
download | gcc-464f49d80df8a5232a956a1ccc8ef78bd25b0110.zip gcc-464f49d80df8a5232a956a1ccc8ef78bd25b0110.tar.gz gcc-464f49d80df8a5232a956a1ccc8ef78bd25b0110.tar.bz2 |
Fix PR tree-optimization/17672 Fix PR tree-optimization/18168
2004-10-16 Daniel Berlin <dberlin@dberlin.org>
Fix PR tree-optimization/17672
Fix PR tree-optimization/18168
* lambda-code.c (lambda_lattice_compute_base): Fix reversed
assert test.
(gcc_tree_to_linear_expression): Add extra to existing constant.
(depth_of_nest): Factor out function used in various places.
(gcc_loop_to_lambda_loop): Clean up code a little bit. No
functional changes.
(find_induction_var_from_exit_cond): Stop guessing, and just
get the right answer :).
(gcc_loopnest_to_lambda_loopnest): Remove useless pre-allocation.
Print out message about result of attempt to create perfect nest.
(lbv_to_gcc_expression): Add type argument, use it to do math
and induction variable creation.
(lle_to_gcc_expression): Ditto.
(lambda_loopnest_to_gcc_loopnest): Create new iv with same type as
oldiv. Pass type argument to lle_to_gcc_expression and
lbv_to_gcc_expression.
Reset number of iterations after transformation.
(perfect_nestify): Remove useless pre-allocation, and cleanup
a small amount.
* tree-data-ref.c (build_classic_dist_vector): Return false for
dependences completely outside of the loop nest we asked about.
(build_classic_dir_vector): Ditto.
(compute_data_dependences_for_loop): Only add dependence relations
inside the loop we asked about.
* tree-loop-linear.c (linear_transform_loops): Use DDR_SIZE_VECT.
Compute immediate uses.
* tree-optimize.c: Move linear_transform_loops to before ivcanon.
From-SVN: r89945
-rw-r--r-- | gcc/ChangeLog | 36 | ||||
-rw-r--r-- | gcc/lambda-code.c | 323 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ltrans-1.c | 22 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ltrans-2.c | 24 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ltrans-3.c | 19 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ltrans-4.c | 18 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ltrans-5.c | 18 | ||||
-rw-r--r-- | gcc/tree-data-ref.c | 78 | ||||
-rw-r--r-- | gcc/tree-loop-linear.c | 19 | ||||
-rw-r--r-- | gcc/tree-optimize.c | 4 |
10 files changed, 380 insertions, 181 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index d35a73c..bfae47a 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,39 @@ +2004-10-16 Daniel Berlin <dberlin@dberlin.org> + + Fix PR tree-optimization/17672 + Fix PR tree-optimization/18168 + + * lambda-code.c (lambda_lattice_compute_base): Fix reversed + assert test. + (gcc_tree_to_linear_expression): Add extra to existing constant. + (depth_of_nest): Factor out function used in various places. + (gcc_loop_to_lambda_loop): Clean up code a little bit. No + functional changes. + (find_induction_var_from_exit_cond): Stop guessing, and just + get the right answer :). + (gcc_loopnest_to_lambda_loopnest): Remove useless pre-allocation. + Print out message about result of attempt to create perfect nest. + (lbv_to_gcc_expression): Add type argument, use it to do math + and induction variable creation. + (lle_to_gcc_expression): Ditto. + (lambda_loopnest_to_gcc_loopnest): Create new iv with same type as + oldiv. Pass type argument to lle_to_gcc_expression and + lbv_to_gcc_expression. + Reset number of iterations after transformation. + (perfect_nestify): Remove useless pre-allocation, and cleanup + a small amount. + + * tree-data-ref.c (build_classic_dist_vector): Return false for + dependences completely outside of the loop nest we asked about. + (build_classic_dir_vector): Ditto. + (compute_data_dependences_for_loop): Only add dependence relations + inside the loop we asked about. + + * tree-loop-linear.c (linear_transform_loops): Use DDR_SIZE_VECT. + Compute immediate uses. + + * tree-optimize.c: Move linear_transform_loops to before ivcanon. + 2004-11-01 Kazu Hirata <kazu@cs.umass.edu> * tree-cfg.c (thread_jumps): Fix a comment typo. diff --git a/gcc/lambda-code.c b/gcc/lambda-code.c index 38c1fd1..d564f43 100644 --- a/gcc/lambda-code.c +++ b/gcc/lambda-code.c @@ -51,7 +51,7 @@ Keshav Pingali for formal proofs that the various statements below are correct. - A loop iteration space are the points traversed by the loop. A point in the + A loop iteration space represents the points traversed by the loop. A point in the iteration space can be represented by a vector of size <loop depth>. You can therefore represent the iteration space as a integral combinations of a set of basis vectors. @@ -116,7 +116,6 @@ of the lattice. */ - DEF_VEC_GC_P(int); static bool perfect_nestify (struct loops *, @@ -416,7 +415,7 @@ lambda_lattice_compute_base (lambda_loopnest nest) /* Otherwise, we need the lower bound expression (which must be an affine function) to determine the base. */ expression = LL_LOWER_BOUND (loop); - gcc_assert (expression && LLE_NEXT (expression) + gcc_assert (expression && !LLE_NEXT (expression) && LLE_DENOMINATOR (expression) == 1); /* The lower triangular portion of the base is going to be the @@ -491,7 +490,7 @@ lcm (int a, int b) /* Perform Fourier-Motzkin elimination to calculate the bounds of the auxillary nest. - Fourier-Motzkin is a way of reducing systems of linear inequality so that + Fourier-Motzkin is a way of reducing systems of linear inequalities so that it is easy to calculate the answer and bounds. A sketch of how it works: Given a system of linear inequalities, ai * xj >= bk, you can always @@ -1150,7 +1149,7 @@ gcc_tree_to_linear_expression (int depth, tree expr, lle = lambda_linear_expression_new (depth, 2 * depth); LLE_CONSTANT (lle) = TREE_INT_CST_LOW (expr); if (extra != 0) - LLE_CONSTANT (lle) = extra; + LLE_CONSTANT (lle) += extra; LLE_DENOMINATOR (lle) = 1; } @@ -1193,6 +1192,21 @@ gcc_tree_to_linear_expression (int depth, tree expr, return lle; } +/* Return the depth of the loopnest NEST */ + +static int +depth_of_nest (struct loop *nest) +{ + size_t depth = 0; + while (nest) + { + depth++; + nest = nest->inner; + } + return depth; +} + + /* Return true if OP is invariant in LOOP and all outer loops. */ static bool @@ -1236,7 +1250,7 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth, tree test; int stepint; int extra = 0; - tree lboundvar, uboundvar; + tree lboundvar, uboundvar, uboundresult; use_optype uses; /* Find out induction var and exit condition. */ @@ -1291,16 +1305,17 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth, } } + /* The induction variable name/version we want to put in the array is the result of the induction variable phi node. */ *ourinductionvar = PHI_RESULT (phi); access_fn = instantiate_parameters (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi))); - if (!access_fn) + if (access_fn == chrec_dont_know) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, - "Unable to convert loop: Access function for induction variable phi is NULL\n"); + "Unable to convert loop: Access function for induction variable phi is unknown\n"); return NULL; } @@ -1402,19 +1417,19 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth, extra = -1 * stepint; else if (TREE_CODE (test) == GT_EXPR) extra = -1 * stepint; - - ubound = gcc_tree_to_linear_expression (depth, - uboundvar, + else if (TREE_CODE (test) == EQ_EXPR) + extra = 1 * stepint; + + ubound = gcc_tree_to_linear_expression (depth, uboundvar, outerinductionvars, *invariants, extra); - VEC_safe_push (tree, *uboundvars, build (PLUS_EXPR, integer_type_node, - uboundvar, - build_int_cst (integer_type_node, extra))); + uboundresult = build (PLUS_EXPR, TREE_TYPE (uboundvar), uboundvar, + build_int_cst (TREE_TYPE (uboundvar), extra)); + VEC_safe_push (tree, *uboundvars, uboundresult); VEC_safe_push (tree, *lboundvars, lboundvar); VEC_safe_push (int, *steps, stepint); if (!ubound) { - if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "Unable to convert loop: Cannot convert upper bound to linear expression\n"); @@ -1444,26 +1459,17 @@ find_induction_var_from_exit_cond (struct loop *loop) test = TREE_OPERAND (expr, 0); if (!COMPARISON_CLASS_P (test)) return NULL_TREE; - /* This is a guess. We say that for a <,!=,<= b, a is the induction - variable. - For >, >=, we guess b is the induction variable. - If we are wrong, it'll fail the rest of the induction variable tests, and - everything will be fine anyway. */ - switch (TREE_CODE (test)) - { - case LT_EXPR: - case LE_EXPR: - case NE_EXPR: - ivarop = TREE_OPERAND (test, 0); - break; - case GT_EXPR: - case GE_EXPR: - case EQ_EXPR: + + /* Find the side that is invariant in this loop. The ivar must be the other + side. */ + + if (expr_invariant_in_loop_p (loop, TREE_OPERAND (test, 0))) ivarop = TREE_OPERAND (test, 1); - break; - default: - gcc_unreachable(); - } + else if (expr_invariant_in_loop_p (loop, TREE_OPERAND (test, 1))) + ivarop = TREE_OPERAND (test, 0); + else + return NULL_TREE; + if (TREE_CODE (ivarop) != SSA_NAME) return NULL_TREE; return ivarop; @@ -1488,25 +1494,14 @@ gcc_loopnest_to_lambda_loopnest (struct loops *currloops, struct loop *temp; int depth = 0; size_t i; - VEC (lambda_loop) *loops; - VEC (tree) *uboundvars; - VEC (tree) *lboundvars; - VEC (int) *steps; + VEC (lambda_loop) *loops = NULL; + VEC (tree) *uboundvars = NULL; + VEC (tree) *lboundvars = NULL; + VEC (int) *steps = NULL; lambda_loop newloop; tree inductionvar = NULL; - - temp = loop_nest; - while (temp) - { - depth++; - temp = temp->inner; - } - loops = VEC_alloc (lambda_loop, 1); - *inductionvars = VEC_alloc (tree, 1); - *invariants = VEC_alloc (tree, 1); - lboundvars = VEC_alloc (tree, 1); - uboundvars = VEC_alloc (tree, 1); - steps = VEC_alloc (int, 1); + + depth = depth_of_nest (loop_nest); temp = loop_nest; while (temp) { @@ -1520,13 +1515,19 @@ gcc_loopnest_to_lambda_loopnest (struct loops *currloops, VEC_safe_push (lambda_loop, loops, newloop); temp = temp->inner; } - if (need_perfect_nest - && !perfect_nestify (currloops, loop_nest, - lboundvars, uboundvars, steps, *inductionvars)) + if (need_perfect_nest) { - if (dump_file) - fprintf (dump_file, "Not a perfect nest and couldn't convert to one.\n"); - return NULL; + if (!perfect_nestify (currloops, loop_nest, + lboundvars, uboundvars, steps, *inductionvars)) + { + if (dump_file) + fprintf (dump_file, "Not a perfect loop 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++) @@ -1536,22 +1537,26 @@ gcc_loopnest_to_lambda_loopnest (struct loops *currloops, } + /* Convert a lambda body vector LBV to a gcc tree, and return the new tree. STMTS_TO_INSERT is a pointer to a tree where the statements we need to be inserted for us are stored. INDUCTION_VARS is the array of induction - variables for the loop this LBV is from. */ + variables for the loop this LBV is from. TYPE is the tree type to use for + the variables and trees involved. */ static tree -lbv_to_gcc_expression (lambda_body_vector lbv, - VEC (tree) *induction_vars, tree * stmts_to_insert) +lbv_to_gcc_expression (lambda_body_vector lbv, + tree type, VEC (tree) *induction_vars, + tree * stmts_to_insert) { tree stmts, stmt, resvar, name; + tree iv; size_t i; tree_stmt_iterator tsi; /* 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. */ @@ -1561,41 +1566,45 @@ lbv_to_gcc_expression (lambda_body_vector lbv, tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); - for (i = 0; i < VEC_length (tree ,induction_vars) ; i++) + for (i = 0; VEC_iterate (tree, induction_vars, i, iv); i++) { if (LBV_COEFFICIENTS (lbv)[i] != 0) { tree newname; - + tree coeffmult; + /* newname = coefficient * induction_variable */ + coeffmult = build_int_cst (type, LBV_COEFFICIENTS (lbv)[i]); stmt = build (MODIFY_EXPR, void_type_node, resvar, - fold (build (MULT_EXPR, integer_type_node, - VEC_index (tree, induction_vars, i), - build_int_cst (integer_type_node, - LBV_COEFFICIENTS (lbv)[i])))); + fold (build (MULT_EXPR, type, iv, coeffmult))); + newname = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = newname; + fold_stmt (&stmt); tsi = tsi_last (stmts); 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; + fold_stmt (&stmt); tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); + } } /* Handle any denominator that occurs. */ if (LBV_DENOMINATOR (lbv) != 1) { + tree denominator = build_int_cst (type, LBV_DENOMINATOR (lbv)); stmt = build (MODIFY_EXPR, void_type_node, resvar, - build (CEIL_DIV_EXPR, integer_type_node, - name, build_int_cst (integer_type_node, - LBV_DENOMINATOR (lbv)))); + build (CEIL_DIV_EXPR, type, name, denominator)); name = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = name; + fold_stmt (&stmt); tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); } @@ -1608,6 +1617,7 @@ lbv_to_gcc_expression (lambda_body_vector lbv, Return the tree that represents the final value of the expression. LLE is the linear expression to convert. OFFSET is the linear offset to apply to the expression. + TYPE is the tree type to use for the variables and math. INDUCTION_VARS is a vector of induction variables for the loops. INVARIANTS is a vector of the loop nest invariants. WRAP specifies what tree code to wrap the results in, if there is more than @@ -1618,6 +1628,7 @@ lbv_to_gcc_expression (lambda_body_vector lbv, 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) @@ -1625,14 +1636,14 @@ lle_to_gcc_expression (lambda_linear_expression lle, tree stmts, stmt, resvar, name; size_t i; tree_stmt_iterator tsi; - VEC(tree) *results; + tree iv, invar; + VEC(tree) *results = NULL; 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); /* Build up the linear expressions, and put the variable representing the result in the results array. */ @@ -1642,13 +1653,14 @@ lle_to_gcc_expression (lambda_linear_expression lle, stmt = build (MODIFY_EXPR, void_type_node, resvar, integer_zero_node); name = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = name; + fold_stmt (&stmt); tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); /* First do the induction variables. at the end, name = name + all the induction variables added together. */ - for (i = 0; i < VEC_length (tree ,induction_vars); i++) + for (i = 0; VEC_iterate (tree, induction_vars, i, iv); i++) { if (LLE_COEFFICIENTS (lle)[i] != 0) { @@ -1663,26 +1675,25 @@ lle_to_gcc_expression (lambda_linear_expression lle, } 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, - VEC_index (tree, induction_vars, i), - coeff)); + mult = fold (build (MULT_EXPR, type, iv, coeff)); } /* newname = mult */ stmt = build (MODIFY_EXPR, void_type_node, resvar, mult); newname = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = newname; + fold_stmt (&stmt); tsi = tsi_last (stmts); 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; + fold_stmt (&stmt); tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); } @@ -1691,41 +1702,39 @@ lle_to_gcc_expression (lambda_linear_expression lle, /* Handle our invariants. At the end, we have name = name + result of adding all multiplied invariants. */ - for (i = 0; i < VEC_length (tree, invariants); i++) + for (i = 0; VEC_iterate (tree, invariants, i, invar); i++) { if (LLE_INVARIANT_COEFFICIENTS (lle)[i] != 0) { tree newname; tree mult; tree coeff; - + int invcoeff = LLE_INVARIANT_COEFFICIENTS (lle)[i]; /* mult = invariant * coefficient */ - if (LLE_INVARIANT_COEFFICIENTS (lle)[i] == 1) + if (invcoeff == 1) { - mult = VEC_index (tree, invariants, i); + mult = invar; } else { - coeff = build_int_cst (integer_type_node, - LLE_INVARIANT_COEFFICIENTS (lle)[i]); - mult = fold (build (MULT_EXPR, integer_type_node, - VEC_index (tree, invariants, i), - coeff)); + coeff = build_int_cst (type, invcoeff); + mult = fold (build (MULT_EXPR, type, invar, coeff)); } /* newname = mult */ stmt = build (MODIFY_EXPR, void_type_node, resvar, mult); newname = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = newname; + fold_stmt (&stmt); tsi = tsi_last (stmts); 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; + fold_stmt (&stmt); tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); } @@ -1736,11 +1745,11 @@ lle_to_gcc_expression (lambda_linear_expression lle, 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, - LLE_CONSTANT (lle)))); + build (PLUS_EXPR, type, name, + build_int_cst (type, LLE_CONSTANT (lle)))); name = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = name; + fold_stmt (&stmt); tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); } @@ -1750,11 +1759,11 @@ lle_to_gcc_expression (lambda_linear_expression lle, if (LLE_CONSTANT (offset) != 0) { stmt = build (MODIFY_EXPR, void_type_node, resvar, - build (PLUS_EXPR, integer_type_node, - name, build_int_cst (integer_type_node, - LLE_CONSTANT (offset)))); + build (PLUS_EXPR, type, name, + build_int_cst (type, LLE_CONSTANT (offset)))); name = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = name; + fold_stmt (&stmt); tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); } @@ -1764,14 +1773,12 @@ lle_to_gcc_expression (lambda_linear_expression lle, { if (wrap == MAX_EXPR) stmt = build (MODIFY_EXPR, void_type_node, resvar, - build (CEIL_DIV_EXPR, integer_type_node, - name, build_int_cst (integer_type_node, - LLE_DENOMINATOR (lle)))); + build (CEIL_DIV_EXPR, type, name, + build_int_cst (type, LLE_DENOMINATOR (lle)))); else if (wrap == MIN_EXPR) stmt = build (MODIFY_EXPR, void_type_node, resvar, - build (FLOOR_DIV_EXPR, integer_type_node, - name, build_int_cst (integer_type_node, - LLE_DENOMINATOR (lle)))); + build (FLOOR_DIV_EXPR, type, name, + build_int_cst (type, LLE_DENOMINATOR (lle)))); else gcc_unreachable(); @@ -1794,7 +1801,7 @@ lle_to_gcc_expression (lambda_linear_expression lle, tree op1 = VEC_index (tree, results, 0); tree op2 = VEC_index (tree, results, 1); stmt = build (MODIFY_EXPR, void_type_node, resvar, - build (wrap, integer_type_node, op1, op2)); + build (wrap, type, op1, op2)); name = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = name; tsi = tsi_last (stmts); @@ -1816,6 +1823,7 @@ lle_to_gcc_expression (lambda_linear_expression lle, NEW_LOOPNEST is the new lambda loopnest to replace OLD_LOOPNEST with. TRANSFORM is the matrix transform that was applied to OLD_LOOPNEST to get NEW_LOOPNEST. */ + void lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest, VEC(tree) *old_ivs, @@ -1827,7 +1835,9 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest, struct loop *temp; size_t i = 0; size_t depth = 0; - VEC(tree) *new_ivs; + VEC(tree) *new_ivs = NULL; + tree oldiv; + block_stmt_iterator bsi; if (dump_file) @@ -1836,13 +1846,7 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest, fprintf (dump_file, "Inverse of transformation matrix:\n"); print_lambda_trans_matrix (dump_file, transform); } - temp = old_loopnest; - new_ivs = VEC_alloc (tree, 1); - while (temp) - { - temp = temp->inner; - depth++; - } + depth = depth_of_nest (old_loopnest); temp = old_loopnest; while (temp) @@ -1853,9 +1857,14 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest, enum tree_code testtype; tree newupperbound, newlowerbound; lambda_linear_expression offset; + tree type; + + oldiv = VEC_index (tree, old_ivs, i); + type = TREE_TYPE (oldiv); + /* First, build the new induction variable temporary */ - ivvar = create_tmp_var (integer_type_node, "lnivtmp"); + ivvar = create_tmp_var (type, "lnivtmp"); add_referenced_tmp_var (ivvar); VEC_safe_push (tree, new_ivs, ivvar); @@ -1865,14 +1874,15 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest, /* Linear offset is a bit tricky to handle. Punt on the unhandled cases for now. */ offset = LL_LINEAR_OFFSET (newloop); - + gcc_assert (LLE_DENOMINATOR (offset) == 1 && lambda_vector_zerop (LLE_COEFFICIENTS (offset), depth)); - + /* Now build the new lower bounds, and insert the statements 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 +1891,7 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest, 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); @@ -1894,49 +1905,62 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest, bb = EDGE_PRED (temp->latch, 0)->src; bsi = bsi_last (bb); create_iv (newlowerbound, - build_int_cst (integer_type_node, LL_STEP (newloop)), + build_int_cst (type, LL_STEP (newloop)), ivvar, temp, &bsi, false, &ivvar, &ivvarinced); /* Replace the exit condition with the new upper bound comparison. */ + testtype = LL_STEP (newloop) >= 0 ? LE_EXPR : GE_EXPR; + + /* Since we don't know which cond_expr part currently points to each + edge, check which one is invariant and make sure we reverse the + comparison if we are trying to replace a <= 50 with 50 >= newiv. + This ensures that we still canonicalize to <invariant> <test> + <induction variable>. */ + if (!expr_invariant_in_loop_p (temp, TREE_OPERAND (exitcond, 0))) + testtype = swap_tree_comparison (testtype); + COND_EXPR_COND (exitcond) = build (testtype, boolean_type_node, - ivvarinced, newupperbound); + newupperbound, ivvarinced); modify_stmt (exitcond); VEC_replace (tree, new_ivs, i, ivvar); i++; temp = temp->inner; } - + /* Rewrite uses of the old ivs so that they are now specified in terms of the new ivs. */ - temp = old_loopnest; - for (i = 0; i < VEC_length (tree, old_ivs); i++) + + for (i = 0; VEC_iterate (tree, old_ivs, i, oldiv); i++) { int j; - tree oldiv = VEC_index (tree, old_ivs, i); dataflow_t imm = get_immediate_uses (SSA_NAME_DEF_STMT (oldiv)); for (j = 0; j < num_immediate_uses (imm); j++) { tree stmt = immediate_use (imm, j); use_operand_p use_p; ssa_op_iter iter; + gcc_assert (TREE_CODE (stmt) != PHI_NODE); FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) { if (USE_FROM_PTR (use_p) == oldiv) { tree newiv, stmts; - lambda_body_vector lbv; + lambda_body_vector lbv, newlbv; /* Compute the new expression for the induction variable. */ depth = VEC_length (tree, new_ivs); 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); + + newlbv = lambda_body_vector_compute_new (transform, lbv); + + newiv = lbv_to_gcc_expression (newlbv, TREE_TYPE (oldiv), + new_ivs, &stmts); bsi = bsi_for_stmt (stmt); /* Insert the statements to build that expression. */ @@ -2048,6 +2072,8 @@ stmt_is_bumper_for_loop (struct loop *loop, tree stmt) } return false; } + + /* Return true if LOOP is a perfect loop nest. Perfect loop nests are those loop nests where all code occurs in the innermost loop body. @@ -2250,14 +2276,12 @@ perfect_nestify (struct loops *loops, tree phi; tree uboundvar; tree stmt; - tree ivvar, ivvarinced; - VEC (tree) *phis; + tree oldivvar, ivvar, ivvarinced; + VEC (tree) *phis = NULL; if (!can_convert_to_perfect_nest (loop, loopivs)) return false; - phis = VEC_alloc (tree, 1); - /* Create the new loop */ olddest = loop->single_exit->dest; @@ -2278,21 +2302,24 @@ perfect_nestify (struct loops *loops, mark_for_rewrite (PHI_RESULT (phi)); } e = redirect_edge_and_branch (EDGE_SUCC (preheaderbb, 0), headerbb); - unmark_all_for_rewrite (); - bb_ann (olddest)->phi_nodes = NULL; - /* Add back the old exit phis. */ + + /* Remove the exit phis from the old basic block. */ + while (phi_nodes (olddest) != NULL) + remove_phi_node (phi_nodes (olddest), NULL, olddest); + + /* and add them to the new basic block. */ while (VEC_length (tree, phis) != 0) { tree def; tree phiname; def = VEC_pop (tree, phis); - phiname = VEC_pop (tree, phis); - + phiname = VEC_pop (tree, phis); phi = create_phi_node (phiname, preheaderbb); add_phi_arg (&phi, def, EDGE_PRED (preheaderbb, 0)); - } - + } flush_pending_stmts (e); + unmark_all_for_rewrite (); + bodybb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb); latchbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb); make_edge (headerbb, bodybb, EDGE_FALLTHRU); @@ -2329,8 +2356,7 @@ perfect_nestify (struct loops *loops, add_referenced_tmp_var (ivvar); bsi = bsi_last (EDGE_PRED (newloop->latch, 0)->src); create_iv (VEC_index (tree, lbounds, 0), - build_int_cst (integer_type_node, - VEC_index (int, steps, 0)), + build_int_cst (integer_type_node, VEC_index (int, steps, 0)), ivvar, newloop, &bsi, false, &ivvar, &ivvarinced); /* Create the new upper bound. This may be not just a variable, so we copy @@ -2344,14 +2370,15 @@ perfect_nestify (struct loops *loops, uboundvar = make_ssa_name (uboundvar, stmt); TREE_OPERAND (stmt, 0) = uboundvar; bsi_insert_before (&bsi, stmt, BSI_SAME_STMT); - COND_EXPR_COND (exit_condition) = build (LE_EXPR, + COND_EXPR_COND (exit_condition) = build (GE_EXPR, boolean_type_node, - ivvarinced, - uboundvar); + uboundvar, + ivvarinced); bbs = get_loop_body (loop); /* Now replace the induction variable in the moved statements with the correct loop induction variable. */ + oldivvar = VEC_index (tree, loopivs, 0); for (i = 0; i < loop->num_nodes; i++) { block_stmt_iterator tobsi = bsi_last (bodybb); @@ -2370,9 +2397,7 @@ perfect_nestify (struct loops *loops, bsi_next (&bsi); continue; } - replace_uses_of_x_with_y (stmt, - VEC_index (tree, loopivs, 0), - ivvar); + replace_uses_of_x_with_y (stmt, oldivvar, ivvar); bsi_move_before (&bsi, &tobsi); } } @@ -2425,9 +2450,7 @@ lambda_transform_legal_p (lambda_trans_matrix trans, for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++) { ddr = (struct data_dependence_relation *) - VARRAY_GENERIC_PTR (dependence_relations, i); - - + VARRAY_GENERIC_PTR (dependence_relations, i); /* Don't care about relations for which we know that there is no dependence, nor about read-read (aka. output-dependences): @@ -2435,9 +2458,15 @@ lambda_transform_legal_p (lambda_trans_matrix trans, if (DDR_ARE_DEPENDENT (ddr) == chrec_known || (DR_IS_READ (DDR_A (ddr)) && DR_IS_READ (DDR_B (ddr)))) continue; + /* Conservatively answer: "this transformation is not valid". */ if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) return false; + + /* If the dependence could not be captured by a distance vector, + conservatively answer that the transform is not valid. */ + if (DDR_DIST_VECT (ddr) == NULL) + return false; /* Compute trans.dist_vect */ lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops, diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ltrans-1.c b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-1.c new file mode 100644 index 0000000..bbeef87 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-1.c @@ -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"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ltrans-2.c b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-2.c new file mode 100644 index 0000000..7ab3e6c --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-2.c @@ -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 *-*-*} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ltrans-3.c b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-3.c new file mode 100644 index 0000000..81c347c --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-3.c @@ -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"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ltrans-4.c b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-4.c new file mode 100644 index 0000000..5f43da1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-4.c @@ -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"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ltrans-5.c b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-5.c new file mode 100644 index 0000000..43a2011 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-5.c @@ -0,0 +1,18 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -ftree-loop-linear -fdump-tree-ltrans-all" } */ +typedef struct rtx_ +{ +} *rtx; +static rtx regno_save_mem[53][16 / 4 + 1]; +extern set_mem_alias_set (rtx, rtx); +int main(void) +{ + int i, j; + for (i = 0; i < 53; i++) + for (j = (16 / (0 ? 8 : 4)); j > 0; j--) + if (regno_save_mem[i][j] != 0) + set_mem_alias_set (regno_save_mem[i][j], 0); +} + +/* { dg-final { scan-tree-dump-times "Linear expression: constant: 1 invariants: denominator: 1" 1 "ltrans" } } */ +/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} } */ diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index c34ae7f..9a0126c 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -1772,9 +1772,12 @@ subscript_dependence_tester (struct data_dependence_relation *ddr) 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 - loop nest. */ + loop nest. + Return FALSE if the dependence relation is outside of the loop nest + starting with FIRST_LOOP. + Return TRUE otherwise. */ -static void +static bool build_classic_dist_vector (struct data_dependence_relation *ddr, int nb_loops, unsigned int first_loop) { @@ -1787,7 +1790,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr, lambda_vector_clear (init_v, nb_loops); if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE) - return; + return true; for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) { @@ -1797,7 +1800,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr, if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) { non_affine_dependence_relation (ddr); - return; + return true; } access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i); @@ -1811,6 +1814,15 @@ build_classic_dist_vector (struct data_dependence_relation *ddr, 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 loops for both variables are at a lower depth than + the first_loop's depth, then they 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) + return false; if (loop_nb_a != loop_nb_b && !flow_loop_nested_p (loop_a, loop_b) @@ -1828,7 +1840,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr, the dependence relation cannot be captured by the distance abstraction. */ non_affine_dependence_relation (ddr); - return; + return true; } /* The dependence is carried by the outermost loop. Example: @@ -1850,7 +1862,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr, if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) { non_affine_dependence_relation (ddr); - return; + return true; } dist = int_cst_value (SUB_DISTANCE (subscript)); @@ -1865,7 +1877,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr, && dist_v[loop_nb] != dist) { finalize_ddr_dependent (ddr, chrec_known); - return; + return true; } dist_v[loop_nb] = dist; @@ -1928,6 +1940,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr, DDR_DIST_VECT (ddr) = dist_v; DDR_SIZE_VECT (ddr) = nb_loops; + return true; } /* Compute the classic per loop direction vector. @@ -1935,9 +1948,12 @@ build_classic_dist_vector (struct data_dependence_relation *ddr, 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 - loop nest. */ + loop nest. + Return FALSE if the dependence relation is outside of the loop nest + starting with FIRST_LOOP. + Return TRUE otherwise. */ -static void +static bool build_classic_dir_vector (struct data_dependence_relation *ddr, int nb_loops, unsigned int first_loop) { @@ -1950,7 +1966,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr, lambda_vector_clear (init_v, nb_loops); if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE) - return; + return true; for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) { @@ -1960,7 +1976,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr, if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) { non_affine_dependence_relation (ddr); - return; + return true; } access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i); @@ -1974,6 +1990,14 @@ build_classic_dir_vector (struct data_dependence_relation *ddr, 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 loops for both variables are at a lower depth than + the first_loop's depth, then they can't possibly matter */ + + if (loop_a->depth < loop_first->depth + && loop_b->depth < loop_first->depth) + return false; if (loop_nb_a != loop_nb_b && !flow_loop_nested_p (loop_a, loop_b) @@ -1991,7 +2015,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr, the dependence relation cannot be captured by the distance abstraction. */ non_affine_dependence_relation (ddr); - return; + return true; } /* The dependence is carried by the outermost loop. Example: @@ -2014,7 +2038,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr, if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) { non_affine_dependence_relation (ddr); - return; + return true; } dist = int_cst_value (SUB_DISTANCE (subscript)); @@ -2038,7 +2062,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr, && (enum data_dependence_direction) dir_v[loop_nb] != dir_star) { finalize_ddr_dependent (ddr, chrec_known); - return; + return true; } dir_v[loop_nb] = dir; @@ -2099,6 +2123,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr, DDR_DIR_VECT (ddr) = dir_v; DDR_SIZE_VECT (ddr) = nb_loops; + return true; } /* Returns true when all the access functions of A are affine or @@ -2195,10 +2220,8 @@ compute_all_dependences (varray_type datarefs, DATAREFS. Returns chrec_dont_know when failing to analyze a difficult case, returns NULL_TREE otherwise. - FIXME: This is a "dumb" walker over all the trees in the loop body. - Find another technique that avoids this costly walk. This is - acceptable for the moment, since this function is used only for - debugging purposes. */ + TODO: This function should be made smarter so that it can handle address + arithmetic as if they were array accesses, etc. */ tree find_data_references_in_loop (struct loop *loop, varray_type *datarefs) @@ -2226,7 +2249,7 @@ find_data_references_in_loop (struct loop *loop, varray_type *datarefs) && !V_MUST_DEF_OPS (ann) && !V_MAY_DEF_OPS (ann)) continue; - + /* In the GIMPLE representation, a modify expression contains a single load or store to memory. */ if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF) @@ -2238,7 +2261,6 @@ find_data_references_in_loop (struct loop *loop, varray_type *datarefs) VARRAY_PUSH_GENERIC_PTR (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 1), true)); - else { if (dont_know_node_not_inserted) @@ -2251,7 +2273,6 @@ find_data_references_in_loop (struct loop *loop, varray_type *datarefs) DR_BASE_NAME (res) = NULL; DR_IS_READ (res) = false; VARRAY_PUSH_GENERIC_PTR (*datarefs, res); - dont_know_node_not_inserted = false; } } @@ -2286,6 +2307,7 @@ compute_data_dependences_for_loop (unsigned nb_loops, varray_type *dependence_relations) { unsigned int i; + varray_type allrelations; /* If one of the data references is not computable, give up without spending time to compute other dependences. */ @@ -2302,14 +2324,18 @@ compute_data_dependences_for_loop (unsigned nb_loops, return; } - compute_all_dependences (*datarefs, dependence_relations); + VARRAY_GENERIC_PTR_INIT (allrelations, 1, "Data dependence relations"); + compute_all_dependences (*datarefs, &allrelations); - for (i = 0; i < VARRAY_ACTIVE_SIZE (*dependence_relations); i++) + for (i = 0; i < VARRAY_ACTIVE_SIZE (allrelations); i++) { struct data_dependence_relation *ddr; - ddr = VARRAY_GENERIC_PTR (*dependence_relations, i); - build_classic_dist_vector (ddr, nb_loops, loop->num); - build_classic_dir_vector (ddr, nb_loops, loop->num); + ddr = VARRAY_GENERIC_PTR (allrelations, i); + if (build_classic_dist_vector (ddr, nb_loops, loop->num)) + { + VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr); + build_classic_dir_vector (ddr, nb_loops, loop->num); + } } } diff --git a/gcc/tree-loop-linear.c b/gcc/tree-loop-linear.c index de16a1e..07afe5d 100644 --- a/gcc/tree-loop-linear.c +++ b/gcc/tree-loop-linear.c @@ -127,7 +127,6 @@ gather_interchange_stats (varray_type dependence_relations, (*dependence_steps) += 0; continue; } - dist = DDR_DIST_VECT (ddr)[loop_number]; if (dist == 0) (*nb_deps_not_carried_by_loop) += 1; @@ -240,6 +239,7 @@ linear_transform_loops (struct loops *loops) { unsigned int i; + compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL); for (i = 1; i < loops->num; i++) { unsigned int depth = 0; @@ -247,8 +247,8 @@ linear_transform_loops (struct loops *loops) varray_type dependence_relations; struct loop *loop_nest = loops->parray[i]; struct loop *temp; - VEC (tree) *oldivs; - VEC (tree) *invariants; + VEC (tree) *oldivs = NULL; + VEC (tree) *invariants = NULL; lambda_loopnest before, after; lambda_trans_matrix trans; bool problem = false; @@ -306,11 +306,11 @@ linear_transform_loops (struct loops *loops) { fprintf (dump_file, "DISTANCE_V ("); print_lambda_vector (dump_file, DDR_DIST_VECT (ddr), - loops->num); + DDR_SIZE_VECT (ddr)); fprintf (dump_file, ")\n"); fprintf (dump_file, "DIRECTION_V ("); print_lambda_vector (dump_file, DDR_DIR_VECT (ddr), - loops->num); + DDR_SIZE_VECT (ddr)); fprintf (dump_file, ")\n"); } } @@ -319,6 +319,7 @@ linear_transform_loops (struct loops *loops) /* Build the transformation matrix. */ trans = lambda_trans_matrix_new (depth, depth); lambda_matrix_id (LTM_MATRIX (trans), depth); + trans = try_interchange_loops (trans, depth, dependence_relations, datarefs, loop_nest->num); @@ -359,11 +360,17 @@ linear_transform_loops (struct loops *loops) } lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants, after, trans); + if (dump_file) + fprintf (dump_file, "Successfully transformed loop.\n"); oldivs = NULL; invariants = NULL; free_dependence_relations (dependence_relations); free_data_refs (datarefs); } - rewrite_into_loop_closed_ssa (); free_df (); + scev_reset (); + rewrite_into_loop_closed_ssa (); +#ifdef ENABLE_CHECKING + verify_loop_closed_ssa (); +#endif } diff --git a/gcc/tree-optimize.c b/gcc/tree-optimize.c index e2eb881..7089c27 100644 --- a/gcc/tree-optimize.c +++ b/gcc/tree-optimize.c @@ -392,11 +392,11 @@ init_tree_optimization_passes (void) NEXT_PASS (pass_loop_init); NEXT_PASS (pass_lim); NEXT_PASS (pass_unswitch); - NEXT_PASS (pass_iv_canon); NEXT_PASS (pass_record_bounds); + NEXT_PASS (pass_linear_transform); + NEXT_PASS (pass_iv_canon); NEXT_PASS (pass_if_conversion); NEXT_PASS (pass_vectorize); - NEXT_PASS (pass_linear_transform); NEXT_PASS (pass_complete_unroll); NEXT_PASS (pass_iv_optimize); NEXT_PASS (pass_loop_done); |