X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Flambda-code.c;h=cf995a3f9f41df4131b00acb2837c07e2b4576d2;hp=5b23d6d5fa136995210c9e245ed8ba4c35168270;hb=b294c6f63918c7566f2acd6cd2b4f62cae80cba8;hpb=b6f9596b0858327c4e0a32ef83f1589d4c8394d1 diff --git a/gcc/lambda-code.c b/gcc/lambda-code.c index 5b23d6d5fa1..cf995a3f9f4 100644 --- a/gcc/lambda-code.c +++ b/gcc/lambda-code.c @@ -16,14 +16,13 @@ You should have received a copy of the GNU General Public License along with GCC; see the file COPYING. If not, write to the Free - Software Foundation, 59 Temple Place - Suite 330, Boston, MA - 02111-1307, USA. */ + Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA + 02110-1301, USA. */ #include "config.h" #include "system.h" #include "coretypes.h" #include "tm.h" -#include "errors.h" #include "ggc.h" #include "tree.h" #include "target.h" @@ -115,12 +114,13 @@ Fourier-Motzkin elimination is used to compute the bounds of the base space of the lattice. */ - -DEF_VEC_GC_P(int); +DEF_VEC_I(int); +DEF_VEC_ALLOC_I(int,heap); static bool perfect_nestify (struct loops *, - struct loop *, VEC (tree) *, - VEC (tree) *, VEC (int) *, VEC (tree) *); + struct loop *, VEC(tree,heap) *, + VEC(tree,heap) *, VEC(int,heap) *, + VEC(tree,heap) *); /* Lattice stuff that is internal to the code generation algorithm. */ typedef struct @@ -683,7 +683,7 @@ lambda_compute_auxillary_space (lambda_loopnest nest, /* Unfortunately, we can't know the number of constraints we'll have ahead of time, but this should be enough even in ridiculous loop nest - cases. We abort if we go over this limit. */ + cases. We must not go over this limit. */ A = lambda_matrix_new (128, depth); B = lambda_matrix_new (128, invariants); a = lambda_vector_new (128); @@ -1152,8 +1152,8 @@ lambda_loopnest_transform (lambda_loopnest nest, lambda_trans_matrix trans) static lambda_linear_expression gcc_tree_to_linear_expression (int depth, tree expr, - VEC(tree) *outerinductionvars, - VEC(tree) *invariants, int extra) + VEC(tree,heap) *outerinductionvars, + VEC(tree,heap) *invariants, int extra) { lambda_linear_expression lle = NULL; switch (TREE_CODE (expr)) @@ -1248,12 +1248,12 @@ invariant_in_loop_and_outer_loops (struct loop *loop, tree op) static lambda_loop gcc_loop_to_lambda_loop (struct loop *loop, int depth, - VEC (tree) ** invariants, + VEC(tree,heap) ** invariants, tree * ourinductionvar, - VEC (tree) * outerinductionvars, - VEC (tree) ** lboundvars, - VEC (tree) ** uboundvars, - VEC (int) ** steps) + VEC(tree,heap) * outerinductionvars, + VEC(tree,heap) ** lboundvars, + VEC(tree,heap) ** uboundvars, + VEC(int,heap) ** steps) { tree phi; tree exit_cond; @@ -1265,7 +1265,6 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth, int stepint; int extra = 0; tree lboundvar, uboundvar, uboundresult; - use_optype uses; /* Find out induction var and exit condition. */ inductionvar = find_induction_var_from_exit_cond (loop); @@ -1294,10 +1293,8 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth, phi = SSA_NAME_DEF_STMT (inductionvar); if (TREE_CODE (phi) != PHI_NODE) { - get_stmt_operands (phi); - uses = STMT_USE_OPS (phi); - - if (!uses) + phi = SINGLE_SSA_TREE_OPERAND (phi, SSA_OP_USE); + if (!phi) { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -1307,7 +1304,6 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth, return NULL; } - phi = USE_OP (uses, 0); phi = SSA_NAME_DEF_STMT (phi); if (TREE_CODE (phi) != PHI_NODE) { @@ -1402,12 +1398,13 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth, return NULL; } /* One part of the test may be a loop invariant tree. */ + VEC_reserve (tree, heap, *invariants, 1); if (TREE_CODE (TREE_OPERAND (test, 1)) == SSA_NAME && invariant_in_loop_and_outer_loops (loop, TREE_OPERAND (test, 1))) - VEC_safe_push (tree, *invariants, TREE_OPERAND (test, 1)); + VEC_quick_push (tree, *invariants, TREE_OPERAND (test, 1)); else if (TREE_CODE (TREE_OPERAND (test, 0)) == SSA_NAME && invariant_in_loop_and_outer_loops (loop, TREE_OPERAND (test, 0))) - VEC_safe_push (tree, *invariants, TREE_OPERAND (test, 0)); + VEC_quick_push (tree, *invariants, TREE_OPERAND (test, 0)); /* The non-induction variable part of the test is the upper bound variable. */ @@ -1439,9 +1436,9 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth, *invariants, 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); + VEC_safe_push (tree, heap, *uboundvars, uboundresult); + VEC_safe_push (tree, heap, *lboundvars, lboundvar); + VEC_safe_push (int, heap, *steps, stepint); if (!ubound) { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -1489,7 +1486,9 @@ find_induction_var_from_exit_cond (struct loop *loop) return ivarop; } -DEF_VEC_GC_P(lambda_loop); +DEF_VEC_P(lambda_loop); +DEF_VEC_ALLOC_P(lambda_loop,heap); + /* Generate a lambda loopnest from a gcc loopnest LOOP_NEST. Return the new loop nest. INDUCTIONVARS is a pointer to an array of induction variables for the @@ -1500,18 +1499,18 @@ DEF_VEC_GC_P(lambda_loop); lambda_loopnest gcc_loopnest_to_lambda_loopnest (struct loops *currloops, struct loop * loop_nest, - VEC (tree) **inductionvars, - VEC (tree) **invariants, + VEC(tree,heap) **inductionvars, + VEC(tree,heap) **invariants, bool need_perfect_nest) { - lambda_loopnest ret; + lambda_loopnest ret = NULL; struct loop *temp; int depth = 0; size_t i; - VEC (lambda_loop) *loops = NULL; - VEC (tree) *uboundvars = NULL; - VEC (tree) *lboundvars = NULL; - VEC (int) *steps = NULL; + VEC(lambda_loop,heap) *loops = NULL; + VEC(tree,heap) *uboundvars = NULL; + VEC(tree,heap) *lboundvars = NULL; + VEC(int,heap) *steps = NULL; lambda_loop newloop; tree inductionvar = NULL; @@ -1525,8 +1524,8 @@ gcc_loopnest_to_lambda_loopnest (struct loops *currloops, &steps); if (!newloop) return NULL; - VEC_safe_push (tree, *inductionvars, inductionvar); - VEC_safe_push (lambda_loop, loops, newloop); + VEC_safe_push (tree, heap, *inductionvars, inductionvar); + VEC_safe_push (lambda_loop, heap, loops, newloop); temp = temp->inner; } if (need_perfect_nest) @@ -1535,23 +1534,26 @@ gcc_loopnest_to_lambda_loopnest (struct loops *currloops, lboundvars, uboundvars, steps, *inductionvars)) { if (dump_file) - fprintf (dump_file, "Not a perfect loop nest and couldn't convert to one.\n"); - return NULL; + fprintf (dump_file, + "Not a perfect loop nest and couldn't convert to one.\n"); + goto fail; } else if (dump_file) - fprintf (dump_file, "Successfully converted loop nest to perfect loop nest.\n"); - - + 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++) LN_LOOPS (ret)[i] = newloop; - + fail: + VEC_free (lambda_loop, heap, loops); + VEC_free (tree, heap, uboundvars); + VEC_free (tree, heap, lboundvars); + VEC_free (int, heap, steps); + return ret; - } - /* 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 @@ -1560,8 +1562,8 @@ gcc_loopnest_to_lambda_loopnest (struct loops *currloops, static tree lbv_to_gcc_expression (lambda_body_vector lbv, - tree type, VEC (tree) *induction_vars, - tree * stmts_to_insert) + tree type, VEC(tree,heap) *induction_vars, + tree *stmts_to_insert) { tree stmts, stmt, resvar, name; tree iv; @@ -1590,7 +1592,7 @@ lbv_to_gcc_expression (lambda_body_vector lbv, /* 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, type, iv, coeffmult))); + fold_build2 (MULT_EXPR, type, iv, coeffmult)); newname = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = newname; @@ -1643,16 +1645,17 @@ 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) + VEC(tree,heap) *induction_vars, + VEC(tree,heap) *invariants, + enum tree_code wrap, tree *stmts_to_insert) { tree stmts, stmt, resvar, name; size_t i; tree_stmt_iterator tsi; tree iv, invar; - VEC(tree) *results = NULL; + VEC(tree,heap) *results = NULL; + gcc_assert (wrap == MAX_EXPR || wrap == MIN_EXPR); name = NULL_TREE; /* Create a statement list and a linear expression temporary. */ stmts = alloc_stmt_list (); @@ -1691,7 +1694,7 @@ lle_to_gcc_expression (lambda_linear_expression lle, { coeff = build_int_cst (type, LLE_COEFFICIENTS (lle)[i]); - mult = fold (build (MULT_EXPR, type, iv, coeff)); + mult = fold_build2 (MULT_EXPR, type, iv, coeff); } /* newname = mult */ @@ -1732,7 +1735,7 @@ lle_to_gcc_expression (lambda_linear_expression lle, else { coeff = build_int_cst (type, invcoeff); - mult = fold (build (MULT_EXPR, type, invar, coeff)); + mult = fold_build2 (MULT_EXPR, type, invar, coeff); } /* newname = mult */ @@ -1785,16 +1788,10 @@ lle_to_gcc_expression (lambda_linear_expression lle, /* Handle any denominator that occurs. */ if (LLE_DENOMINATOR (lle) != 1) { - if (wrap == MAX_EXPR) - stmt = build (MODIFY_EXPR, void_type_node, resvar, - 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, type, name, - build_int_cst (type, LLE_DENOMINATOR (lle)))); - else - gcc_unreachable(); + stmt = build_int_cst (type, LLE_DENOMINATOR (lle)); + stmt = build (wrap == MAX_EXPR ? CEIL_DIV_EXPR : FLOOR_DIV_EXPR, + type, name, stmt); + stmt = build (MODIFY_EXPR, void_type_node, resvar, stmt); /* name = {ceil, floor}(name/denominator) */ name = make_ssa_name (resvar, stmt); @@ -1802,7 +1799,7 @@ lle_to_gcc_expression (lambda_linear_expression lle, tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); } - VEC_safe_push (tree, results, name); + VEC_safe_push (tree, heap, results, name); } /* Again, out of laziness, we don't handle this case yet. It's not @@ -1822,6 +1819,8 @@ lle_to_gcc_expression (lambda_linear_expression lle, tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); } + VEC_free (tree, heap, results); + *stmts_to_insert = stmts; return name; } @@ -1840,16 +1839,15 @@ lle_to_gcc_expression (lambda_linear_expression lle, void lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest, - VEC(tree) *old_ivs, - VEC(tree) *invariants, + VEC(tree,heap) *old_ivs, + VEC(tree,heap) *invariants, lambda_loopnest new_loopnest, lambda_trans_matrix transform) { - struct loop *temp; size_t i = 0; size_t depth = 0; - VEC(tree) *new_ivs = NULL; + VEC(tree,heap) *new_ivs = NULL; tree oldiv; block_stmt_iterator bsi; @@ -1884,7 +1882,7 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest, ivvar = create_tmp_var (type, "lnivtmp"); add_referenced_tmp_var (ivvar); - VEC_safe_push (tree, new_ivs, ivvar); + VEC_safe_push (tree, heap, new_ivs, ivvar); newloop = LN_LOOPS (new_loopnest)[i]; @@ -1970,12 +1968,11 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest, tree oldiv_def; tree oldiv_stmt = SSA_NAME_DEF_STMT (oldiv); - gcc_assert (TREE_CODE (oldiv_stmt) == PHI_NODE - || NUM_DEFS (STMT_DEF_OPS (oldiv_stmt)) == 1); if (TREE_CODE (oldiv_stmt) == PHI_NODE) - oldiv_def = PHI_RESULT (oldiv_stmt); + oldiv_def = PHI_RESULT (oldiv_stmt); else - oldiv_def = DEF_OP (STMT_DEF_OPS (oldiv_stmt), 0); + oldiv_def = SINGLE_SSA_TREE_OPERAND (oldiv_stmt, SSA_OP_DEF); + gcc_assert (oldiv_def != NULL_TREE); FOR_EACH_IMM_USE_SAFE (imm_use, imm_iter, oldiv_def) { @@ -2010,30 +2007,9 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest, } } } + VEC_free (tree, heap, new_ivs); } - -/* Returns true when the vector V is lexicographically positive, in - other words, when the first nonzero element is positive. */ - -static bool -lambda_vector_lexico_pos (lambda_vector v, - unsigned n) -{ - unsigned i; - for (i = 0; i < n; i++) - { - if (v[i] == 0) - continue; - if (v[i] < 0) - return false; - if (v[i] > 0) - return true; - } - return true; -} - - /* Return TRUE if this is not interesting statement from the perspective of determining if we have a perfect loop nest. */ @@ -2067,16 +2043,11 @@ phi_loop_edge_uses_def (struct loop *loop, tree phi, tree def) static bool stmt_uses_phi_result (tree stmt, tree phi_result) { - use_optype uses = STMT_USE_OPS (stmt); + tree use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE); /* This is conservatively true, because we only want SIMPLE bumpers of the form x +- constant for our pass. */ - if (NUM_USES (uses) != 1) - return false; - if (USE_OP (uses, 0) == phi_result) - return true; - - return false; + return (use == phi_result); } /* STMT is a bumper stmt for LOOP if the version it defines is used in the @@ -2090,13 +2061,13 @@ stmt_is_bumper_for_loop (struct loop *loop, tree stmt) { tree use; tree def; - def_optype defs = STMT_DEF_OPS (stmt); imm_use_iterator iter; use_operand_p use_p; - if (NUM_DEFS (defs) != 1) + def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF); + if (!def) return false; - def = DEF_OP (defs, 0); + FOR_EACH_IMM_USE_FAST (use_p, iter, def) { use = USE_STMT (use_p); @@ -2172,17 +2143,31 @@ perfect_nest_p (struct loop *loop) return true; } -/* Replace the USES of tree X in STMT with tree Y */ +/* Replace the USES of X in STMT, or uses with the same step as X with Y. */ static void -replace_uses_of_x_with_y (tree stmt, tree x, tree y) +replace_uses_equiv_to_x_with_y (struct loop *loop, tree stmt, tree x, + int xstep, tree y) { - use_optype uses = STMT_USE_OPS (stmt); - size_t i; - for (i = 0; i < NUM_USES (uses); i++) + ssa_op_iter iter; + use_operand_p use_p; + + FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) { - if (USE_OP (uses, i) == x) - SET_USE_OP (uses, i, y); + tree use = USE_FROM_PTR (use_p); + tree step = NULL_TREE; + tree access_fn = NULL_TREE; + + + access_fn = instantiate_parameters + (loop, analyze_scalar_evolution (loop, use)); + if (access_fn != NULL_TREE && access_fn != chrec_dont_know) + step = evolution_part_in_loop_num (access_fn, loop->num); + if ((step && step != chrec_dont_know + && TREE_CODE (step) == INTEGER_CST + && int_cst_value (step) == xstep) + || USE_FROM_PTR (use_p) == x) + SET_USE (use_p, y); } } @@ -2191,16 +2176,67 @@ replace_uses_of_x_with_y (tree stmt, tree x, tree y) static bool stmt_uses_op (tree stmt, tree op) { - use_optype uses = STMT_USE_OPS (stmt); - size_t i; - for (i = 0; i < NUM_USES (uses); i++) + ssa_op_iter iter; + tree use; + + FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) { - if (USE_OP (uses, i) == op) + if (use == op) return true; } return false; } +/* Return true if STMT is an exit PHI for LOOP */ + +static bool +exit_phi_for_loop_p (struct loop *loop, tree stmt) +{ + + if (TREE_CODE (stmt) != PHI_NODE + || PHI_NUM_ARGS (stmt) != 1 + || bb_for_stmt (stmt) != loop->single_exit->dest) + return false; + + return true; +} + +/* Return true if STMT can be put back into INNER, a loop by moving it to the + beginning of that loop. */ + +static bool +can_put_in_inner_loop (struct loop *inner, tree stmt) +{ + imm_use_iterator imm_iter; + use_operand_p use_p; + basic_block use_bb = NULL; + + gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR); + if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS) + || !expr_invariant_in_loop_p (inner, TREE_OPERAND (stmt, 1))) + return false; + + /* We require that the basic block of all uses be the same, or the use be an + exit phi. */ + FOR_EACH_IMM_USE_FAST (use_p, imm_iter, TREE_OPERAND (stmt, 0)) + { + if (!exit_phi_for_loop_p (inner, USE_STMT (use_p))) + { + basic_block immbb = bb_for_stmt (USE_STMT (use_p)); + + if (!flow_bb_inside_loop_p (inner, immbb)) + return false; + if (use_bb == NULL) + use_bb = immbb; + else if (immbb != use_bb) + return false; + } + } + return true; + +} + + /* Return TRUE if LOOP is an imperfect nest that we can convert to a perfect one. LOOPIVS is a vector of induction variables, one per loop. ATM, we only handle imperfect nests of depth 2, where all of the statements @@ -2208,7 +2244,7 @@ stmt_uses_op (tree stmt, tree op) static bool can_convert_to_perfect_nest (struct loop *loop, - VEC (tree) *loopivs) + VEC(tree,heap) *loopivs) { basic_block *bbs; tree exit_condition, phi; @@ -2220,8 +2256,6 @@ can_convert_to_perfect_nest (struct loop *loop, if (!loop->inner || loop->inner->inner) return false; - /* We only handle moving the after-inner-body statements right now, so make - sure all the statements we need to move are located in that position. */ bbs = get_loop_body (loop); exit_condition = get_loop_exit_condition (loop); for (i = 0; i < loop->num_nodes; i++) @@ -2232,30 +2266,42 @@ can_convert_to_perfect_nest (struct loop *loop, { size_t j; tree stmt = bsi_stmt (bsi); + tree iv; + if (stmt == exit_condition || not_interesting_stmt (stmt) || stmt_is_bumper_for_loop (loop, stmt)) continue; /* If the statement uses inner loop ivs, we == screwed. */ - for (j = 1; j < VEC_length (tree, loopivs); j++) - if (stmt_uses_op (stmt, VEC_index (tree, loopivs, j))) - { - free (bbs); - return false; - } + for (j = 1; VEC_iterate (tree, loopivs, j, iv); j++) + if (stmt_uses_op (stmt, iv)) + goto fail; - /* If the bb of a statement we care about isn't dominated by - the header of the inner loop, then we are also screwed. */ + /* If this is a simple operation like a cast that is invariant + in the inner loop, only used there, and we can place it + there, then it's not going to hurt us. + This means that we will propagate casts and other cheap + invariant operations *back* + into the inner loop if we can interchange the loop, on the + theory that we are going to gain a lot more by interchanging + the loop than we are by leaving some invariant code there for + some other pass to clean up. */ + if (TREE_CODE (stmt) == MODIFY_EXPR + && is_gimple_cast (TREE_OPERAND (stmt, 1)) + && can_put_in_inner_loop (loop->inner, stmt)) + continue; + + /* Otherwise, if the bb of a statement we care about isn't + dominated by the header of the inner loop, then we can't + handle this case right now. This test ensures that the + statement comes completely *after* the inner loop. */ if (!dominated_by_p (CDI_DOMINATORS, bb_for_stmt (stmt), loop->inner->header)) - { - free (bbs); - return false; - } + goto fail; } } - } + } /* We also need to make sure the loop exit only has simple copy phis in it, otherwise we don't know how to transform it into a perfect nest right @@ -2264,9 +2310,14 @@ can_convert_to_perfect_nest (struct loop *loop, for (phi = phi_nodes (exitdest); phi; phi = PHI_CHAIN (phi)) if (PHI_NUM_ARGS (phi) != 1) - return false; - + goto fail; + + free (bbs); return true; + + fail: + free (bbs); + return false; } /* Transform the loop nest into a perfect nest, if possible. @@ -2305,19 +2356,20 @@ can_convert_to_perfect_nest (struct loop *loop, } Return FALSE if we can't make this loop into a perfect nest. */ + static bool perfect_nestify (struct loops *loops, struct loop *loop, - VEC (tree) *lbounds, - VEC (tree) *ubounds, - VEC (int) *steps, - VEC (tree) *loopivs) + VEC(tree,heap) *lbounds, + VEC(tree,heap) *ubounds, + VEC(int,heap) *steps, + VEC(tree,heap) *loopivs) { basic_block *bbs; tree exit_condition; tree then_label, else_label, cond_stmt; basic_block preheaderbb, headerbb, bodybb, latchbb, olddest; - size_t i; + int i; block_stmt_iterator bsi; bool insert_after; edge e; @@ -2326,7 +2378,7 @@ perfect_nestify (struct loops *loops, tree uboundvar; tree stmt; tree oldivvar, ivvar, ivvarinced; - VEC (tree) *phis = NULL; + VEC(tree,heap) *phis = NULL; if (!can_convert_to_perfect_nest (loop, loopivs)) return false; @@ -2340,8 +2392,9 @@ perfect_nestify (struct loops *loops, /* Push the exit phi nodes that we are moving. */ for (phi = phi_nodes (olddest); phi; phi = PHI_CHAIN (phi)) { - VEC_safe_push (tree, phis, PHI_RESULT (phi)); - VEC_safe_push (tree, phis, PHI_ARG_DEF (phi, 0)); + VEC_reserve (tree, heap, phis, 2); + VEC_quick_push (tree, phis, PHI_RESULT (phi)); + VEC_quick_push (tree, phis, PHI_ARG_DEF (phi, 0)); } e = redirect_edge_and_branch (single_succ_edge (preheaderbb), headerbb); @@ -2362,8 +2415,9 @@ perfect_nestify (struct loops *loops, phiname = VEC_pop (tree, phis); phi = create_phi_node (phiname, preheaderbb); add_phi_arg (phi, def, single_pred_edge (preheaderbb)); - } + } flush_pending_stmts (e); + VEC_free (tree, heap, phis); bodybb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb); latchbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb); @@ -2396,11 +2450,12 @@ perfect_nestify (struct loops *loops, set_immediate_dominator (CDI_DOMINATORS, latchbb, bodybb); set_immediate_dominator (CDI_DOMINATORS, olddest, bodybb); /* Create the new iv. */ - ivvar = create_tmp_var (integer_type_node, "perfectiv"); + oldivvar = VEC_index (tree, loopivs, 0); + ivvar = create_tmp_var (TREE_TYPE (oldivvar), "perfectiv"); add_referenced_tmp_var (ivvar); standard_iv_increment_position (newloop, &bsi, &insert_after); create_iv (VEC_index (tree, lbounds, 0), - build_int_cst (integer_type_node, VEC_index (int, steps, 0)), + build_int_cst (TREE_TYPE (oldivvar), VEC_index (int, steps, 0)), ivvar, newloop, &bsi, insert_after, &ivvar, &ivvarinced); /* Create the new upper bound. This may be not just a variable, so we copy @@ -2418,39 +2473,102 @@ perfect_nestify (struct loops *loops, bsi_insert_after (&bsi, stmt, BSI_SAME_STMT); else bsi_insert_before (&bsi, stmt, BSI_SAME_STMT); - + update_stmt (stmt); COND_EXPR_COND (exit_condition) = build (GE_EXPR, boolean_type_node, uboundvar, ivvarinced); - - bbs = get_loop_body (loop); - /* Now replace the induction variable in the moved statements with the - correct loop induction variable. */ + update_stmt (exit_condition); + bbs = get_loop_body_in_dom_order (loop); + /* Now move the statements, and 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++) + for (i = loop->num_nodes - 1; i >= 0 ; i--) { block_stmt_iterator tobsi = bsi_last (bodybb); if (bbs[i]->loop_father == loop) { - /* Note that the bsi only needs to be explicitly incremented - when we don't move something, since it is automatically - incremented when we do. */ - for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi);) + /* If this is true, we are *before* the inner loop. + If this isn't true, we are *after* it. + + The only time can_convert_to_perfect_nest returns true when we + have statements before the inner loop is if they can be moved + into the inner loop. + + The only time can_convert_to_perfect_nest returns true when we + have statements after the inner loop is if they can be moved into + the new split loop. */ + + if (dominated_by_p (CDI_DOMINATORS, loop->inner->header, bbs[i])) + { + for (bsi = bsi_last (bbs[i]); !bsi_end_p (bsi);) + { + use_operand_p use_p; + imm_use_iterator imm_iter; + tree stmt = bsi_stmt (bsi); + + if (stmt == exit_condition + || not_interesting_stmt (stmt) + || stmt_is_bumper_for_loop (loop, stmt)) + { + if (!bsi_end_p (bsi)) + bsi_prev (&bsi); + continue; + } + /* Move this statement back into the inner loop. + This looks a bit confusing, but we are really just + finding the first non-exit phi use and moving the + statement to the beginning of that use's basic + block. */ + FOR_EACH_IMM_USE_SAFE (use_p, imm_iter, + TREE_OPERAND (stmt, 0)) + { + tree imm_stmt = USE_STMT (use_p); + if (!exit_phi_for_loop_p (loop->inner, imm_stmt)) + { + block_stmt_iterator tobsi = bsi_after_labels (bb_for_stmt (imm_stmt)); + bsi_move_after (&bsi, &tobsi); + update_stmt (stmt); + BREAK_FROM_SAFE_IMM_USE (imm_iter); + } + } + } + } + else { - tree stmt = bsi_stmt (bsi); - if (stmt == exit_condition - || not_interesting_stmt (stmt) - || stmt_is_bumper_for_loop (loop, stmt)) - { - bsi_next (&bsi); - continue; + /* Note that the bsi only needs to be explicitly incremented + when we don't move something, since it is automatically + incremented when we do. */ + for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi);) + { + ssa_op_iter i; + tree n, stmt = bsi_stmt (bsi); + + if (stmt == exit_condition + || not_interesting_stmt (stmt) + || stmt_is_bumper_for_loop (loop, stmt)) + { + bsi_next (&bsi); + continue; + } + + replace_uses_equiv_to_x_with_y (loop, stmt, + oldivvar, + VEC_index (int, steps, 0), + ivvar); + bsi_move_before (&bsi, &tobsi); + + /* If the statement has any virtual operands, they may + need to be rewired because the original loop may + still reference them. */ + FOR_EACH_SSA_TREE_OPERAND (n, stmt, i, SSA_OP_ALL_VIRTUALS) + mark_sym_for_renaming (SSA_NAME_VAR (n)); } - replace_uses_of_x_with_y (stmt, oldivvar, ivvar); - bsi_move_before (&bsi, &tobsi); } + } } + free (bbs); return perfect_nest_p (loop); } @@ -2477,11 +2595,8 @@ lambda_transform_legal_p (lambda_trans_matrix trans, lambda_vector distres; struct data_dependence_relation *ddr; -#if defined ENABLE_CHECKING - if (LTM_COLSIZE (trans) != nb_loops - || LTM_ROWSIZE (trans) != nb_loops) - abort (); -#endif + gcc_assert (LTM_COLSIZE (trans) == nb_loops + && LTM_ROWSIZE (trans) == nb_loops); /* When there is an unknown relation in the dependence_relations, we know that it is no worth looking at this loop nest: give up. */