X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-ssa-loop-manip.c;h=f6e2e9c937f358e412a63a571e3f6a5fdb3b2240;hb=9e229ec708d7e1c812330cd2eb941b6c4f50bb9c;hp=7ebe680871db112b127f0fbdf79c1c2c6c3fad45;hpb=cfaf579ddfaec5cb9bc5d220eadd212786138f3d;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c index 7ebe680871d..f6e2e9c937f 100644 --- a/gcc/tree-ssa-loop-manip.c +++ b/gcc/tree-ssa-loop-manip.c @@ -1,18 +1,19 @@ /* High-level loop manipulation functions. - Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc. - + Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010 + Free Software Foundation, Inc. + This file is part of GCC. - + GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. - + GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. - + You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see . */ @@ -22,12 +23,9 @@ along with GCC; see the file COPYING3. If not see #include "coretypes.h" #include "tm.h" #include "tree.h" -#include "rtl.h" #include "tm_p.h" -#include "hard-reg-set.h" #include "basic-block.h" #include "output.h" -#include "diagnostic.h" #include "tree-flow.h" #include "tree-dump.h" #include "timevar.h" @@ -37,12 +35,13 @@ along with GCC; see the file COPYING3. If not see #include "tree-scalar-evolution.h" #include "params.h" #include "tree-inline.h" +#include "langhooks.h" /* Creates an induction variable with value BASE + STEP * iteration in LOOP. It is expected that neither BASE nor STEP are shared with other expressions (unless the sharing rules allow this). Use VAR as a base var_decl for it (if NULL, a new temporary will be created). The increment will occur at - INCR_POS (after it if AFTER is true, before it otherwise). INCR_POS and + INCR_POS (after it if AFTER is true, before it otherwise). INCR_POS and AFTER can be computed using standard_iv_increment_position. The ssa versions of the variable before and after increment will be stored in VAR_BEFORE and VAR_AFTER (unless they are NULL). */ @@ -99,9 +98,11 @@ create_iv (tree base, tree step, tree var, struct loop *loop, } if (POINTER_TYPE_P (TREE_TYPE (base))) { - step = fold_convert (sizetype, step); + if (TREE_CODE (base) == ADDR_EXPR) + mark_addressable (TREE_OPERAND (base, 0)); + step = convert_to_ptrofftype (step); if (incr_op == MINUS_EXPR) - step = fold_build1 (NEGATE_EXPR, sizetype, step); + step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step); incr_op = POINTER_PLUS_EXPR; } /* Gimplify the step if necessary. We put the computations in front of the @@ -122,8 +123,8 @@ create_iv (tree base, tree step, tree var, struct loop *loop, stmt = create_phi_node (vb, loop->header); SSA_NAME_DEF_STMT (vb) = stmt; - add_phi_arg (stmt, initial, loop_preheader_edge (loop)); - add_phi_arg (stmt, va, loop_latch_edge (loop)); + add_phi_arg (stmt, initial, loop_preheader_edge (loop), UNKNOWN_LOCATION); + add_phi_arg (stmt, va, loop_latch_edge (loop), UNKNOWN_LOCATION); } /* Add exit phis for the USE on EXIT. */ @@ -153,7 +154,7 @@ add_exit_phis_edge (basic_block exit, tree use) create_new_def_for (gimple_phi_result (phi), phi, gimple_phi_result_ptr (phi)); FOR_EACH_EDGE (e, ei, exit->preds) - add_phi_arg (phi, use, e); + add_phi_arg (phi, use, e, UNKNOWN_LOCATION); } /* Add exit phis for VAR that is used in LIVEIN. @@ -276,6 +277,9 @@ find_uses_to_rename_stmt (gimple stmt, bitmap *use_blocks, bitmap need_phis) tree var; basic_block bb = gimple_bb (stmt); + if (is_gimple_debug (stmt)) + return; + FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES) find_uses_to_rename_use (bb, var, use_blocks, need_phis); } @@ -296,11 +300,11 @@ find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis) for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi)) find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e), use_blocks, need_phis); - + for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) find_uses_to_rename_stmt (gsi_stmt (bsi), use_blocks, need_phis); } - + /* Marks names that are used outside of the loop they are defined in for rewrite. Records the set of blocks in that the ssa names are defined to USE_BLOCKS. If CHANGED_BBS is not NULL, @@ -354,7 +358,7 @@ find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis) Looking from the outer loop with the normal SSA form, the first use of k is not well-behaved, while the second one is an induction variable with base 99 and step 1. - + If CHANGED_BBS is not NULL, we look for uses outside loops only in the basic blocks in this set. @@ -408,7 +412,7 @@ check_loop_closed_ssa_use (basic_block bb, tree use) { gimple def; basic_block def_bb; - + if (TREE_CODE (use) != SSA_NAME || !is_gimple_reg (use)) return; @@ -426,14 +430,18 @@ check_loop_closed_ssa_stmt (basic_block bb, gimple stmt) ssa_op_iter iter; tree var; + if (is_gimple_debug (stmt)) + return; + FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES) check_loop_closed_ssa_use (bb, var); } -/* Checks that invariants of the loop closed ssa form are preserved. */ +/* Checks that invariants of the loop closed ssa form are preserved. + Call verify_ssa when VERIFY_SSA_P is true. */ -void -verify_loop_closed_ssa (void) +DEBUG_FUNCTION void +verify_loop_closed_ssa (bool verify_ssa_p) { basic_block bb; gimple_stmt_iterator bsi; @@ -444,7 +452,10 @@ verify_loop_closed_ssa (void) if (number_of_loops () <= 1) return; - verify_ssa (false); + if (verify_ssa_p) + verify_ssa (false); + + timevar_push (TV_VERIFY_LOOP_CLOSED); FOR_EACH_BB (bb) { @@ -459,6 +470,8 @@ verify_loop_closed_ssa (void) for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) check_loop_closed_ssa_stmt (bb, gsi_stmt (bsi)); } + + timevar_pop (TV_VERIFY_LOOP_CLOSED); } /* Split loop exit edge EXIT. The things are a bit complicated by a need to @@ -473,11 +486,13 @@ split_loop_exit_edge (edge exit) tree new_name, name; use_operand_p op_p; gimple_stmt_iterator psi; + source_location locus; for (psi = gsi_start_phis (dest); !gsi_end_p (psi); gsi_next (&psi)) { phi = gsi_stmt (psi); op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb)); + locus = gimple_phi_arg_location_from_edge (phi, single_succ_edge (bb)); name = USE_FROM_PTR (op_p); @@ -491,7 +506,7 @@ split_loop_exit_edge (edge exit) new_name = duplicate_ssa_name (name, NULL); new_phi = create_phi_node (new_name, bb); SSA_NAME_DEF_STMT (new_name) = new_phi; - add_phi_arg (new_phi, name, exit); + add_phi_arg (new_phi, name, exit, locus); SET_USE (op_p, new_name); } @@ -604,7 +619,7 @@ gimple_duplicate_loop_to_header_edge (struct loop *loop, edge e, #ifdef ENABLE_CHECKING if (loops_state_satisfies_p (LOOP_CLOSED_SSA)) - verify_loop_closed_ssa (); + verify_loop_closed_ssa (true); #endif first_new_block = last_basic_block; @@ -690,7 +705,7 @@ determine_exit_conditions (struct loop *loop, struct tree_niter_desc *desc, enum tree_code cmp = desc->cmp; tree cond = boolean_true_node, assum; - /* For pointers, do the arithmetics in the type of step (sizetype). */ + /* For pointers, do the arithmetics in the type of step. */ base = fold_convert (type, base); bound = fold_convert (type, bound); @@ -807,7 +822,7 @@ scale_dominated_blocks_in_loop (struct loop *loop, basic_block bb, If N is number of iterations of the loop and MAY_BE_ZERO is the condition under that loop exits in the first iteration even if N != 0, - + while (1) { x = phi (init, next); @@ -820,7 +835,7 @@ scale_dominated_blocks_in_loop (struct loop *loop, basic_block bb, becomes (with possibly the exit conditions formulated a bit differently, avoiding the need to create a new iv): - + if (MAY_BE_ZERO || N < FACTOR) goto rest; @@ -836,7 +851,7 @@ scale_dominated_blocks_in_loop (struct loop *loop, basic_block bb, pre; post; N -= FACTOR; - + } while (N >= FACTOR); rest: @@ -851,7 +866,7 @@ scale_dominated_blocks_in_loop (struct loop *loop, basic_block bb, break; post; } - + Before the loop is unrolled, TRANSFORM is called for it (only for the unrolled loop, but not for its versioned copy). DATA is passed to TRANSFORM. */ @@ -988,10 +1003,19 @@ tree_transform_and_unroll_loop (struct loop *loop, unsigned factor, /* Prefer using original variable as a base for the new ssa name. This is necessary for virtual ops, and useful in order to avoid losing debug info for real ops. */ - if (TREE_CODE (next) == SSA_NAME) + if (TREE_CODE (next) == SSA_NAME + && useless_type_conversion_p (TREE_TYPE (next), + TREE_TYPE (init))) var = SSA_NAME_VAR (next); - else if (TREE_CODE (init) == SSA_NAME) + else if (TREE_CODE (init) == SSA_NAME + && useless_type_conversion_p (TREE_TYPE (init), + TREE_TYPE (next))) var = SSA_NAME_VAR (init); + else if (useless_type_conversion_p (TREE_TYPE (next), TREE_TYPE (init))) + { + var = create_tmp_var (TREE_TYPE (next), "unrinittmp"); + add_referenced_var (var); + } else { var = create_tmp_var (TREE_TYPE (init), "unrinittmp"); @@ -1002,8 +1026,8 @@ tree_transform_and_unroll_loop (struct loop *loop, unsigned factor, phi_rest = create_phi_node (new_init, rest); SSA_NAME_DEF_STMT (new_init) = phi_rest; - add_phi_arg (phi_rest, init, precond_edge); - add_phi_arg (phi_rest, next, new_exit); + add_phi_arg (phi_rest, init, precond_edge, UNKNOWN_LOCATION); + add_phi_arg (phi_rest, next, new_exit, UNKNOWN_LOCATION); SET_USE (op, new_init); } @@ -1025,7 +1049,7 @@ tree_transform_and_unroll_loop (struct loop *loop, unsigned factor, free (wont_exit); gcc_assert (ok); - for (i = 0; VEC_iterate (edge, to_remove, i, e); i++) + FOR_EACH_VEC_ELT (edge, to_remove, i, e) { ok = remove_path (e); gcc_assert (ok); @@ -1061,7 +1085,7 @@ tree_transform_and_unroll_loop (struct loop *loop, unsigned factor, /* Finally create the new counter for number of iterations and add the new exit instruction. */ - bsi = gsi_last_bb (exit_bb); + bsi = gsi_last_nondebug_bb (exit_bb); exit_if = gsi_stmt (bsi); create_iv (exit_base, exit_step, NULL_TREE, loop, &bsi, false, &ctr_before, &ctr_after); @@ -1074,7 +1098,7 @@ tree_transform_and_unroll_loop (struct loop *loop, unsigned factor, verify_flow_info (); verify_dominators (CDI_DOMINATORS); verify_loop_structure (); - verify_loop_closed_ssa (); + verify_loop_closed_ssa (true); #endif } @@ -1089,3 +1113,155 @@ tree_unroll_loop (struct loop *loop, unsigned factor, tree_transform_and_unroll_loop (loop, factor, exit, desc, NULL, NULL); } + +/* Rewrite the phi node at position PSI in function of the main + induction variable MAIN_IV and insert the generated code at GSI. */ + +static void +rewrite_phi_with_iv (loop_p loop, + gimple_stmt_iterator *psi, + gimple_stmt_iterator *gsi, + tree main_iv) +{ + affine_iv iv; + gimple stmt, phi = gsi_stmt (*psi); + tree atype, mtype, val, res = PHI_RESULT (phi); + + if (!is_gimple_reg (res) || res == main_iv) + { + gsi_next (psi); + return; + } + + if (!simple_iv (loop, loop, res, &iv, true)) + { + gsi_next (psi); + return; + } + + remove_phi_node (psi, false); + + atype = TREE_TYPE (res); + mtype = POINTER_TYPE_P (atype) ? sizetype : atype; + val = fold_build2 (MULT_EXPR, mtype, unshare_expr (iv.step), + fold_convert (mtype, main_iv)); + val = fold_build2 (POINTER_TYPE_P (atype) + ? POINTER_PLUS_EXPR : PLUS_EXPR, + atype, unshare_expr (iv.base), val); + val = force_gimple_operand_gsi (gsi, val, false, NULL_TREE, true, + GSI_SAME_STMT); + stmt = gimple_build_assign (res, val); + gsi_insert_before (gsi, stmt, GSI_SAME_STMT); + SSA_NAME_DEF_STMT (res) = stmt; +} + +/* Rewrite all the phi nodes of LOOP in function of the main induction + variable MAIN_IV. */ + +static void +rewrite_all_phi_nodes_with_iv (loop_p loop, tree main_iv) +{ + unsigned i; + basic_block *bbs = get_loop_body_in_dom_order (loop); + gimple_stmt_iterator psi; + + for (i = 0; i < loop->num_nodes; i++) + { + basic_block bb = bbs[i]; + gimple_stmt_iterator gsi = gsi_after_labels (bb); + + if (bb->loop_father != loop) + continue; + + for (psi = gsi_start_phis (bb); !gsi_end_p (psi); ) + rewrite_phi_with_iv (loop, &psi, &gsi, main_iv); + } + + free (bbs); +} + +/* Bases all the induction variables in LOOP on a single induction + variable (unsigned with base 0 and step 1), whose final value is + compared with *NIT. When the IV type precision has to be larger + than *NIT type precision, *NIT is converted to the larger type, the + conversion code is inserted before the loop, and *NIT is updated to + the new definition. When BUMP_IN_LATCH is true, the induction + variable is incremented in the loop latch, otherwise it is + incremented in the loop header. Return the induction variable that + was created. */ + +tree +canonicalize_loop_ivs (struct loop *loop, tree *nit, bool bump_in_latch) +{ + unsigned precision = TYPE_PRECISION (TREE_TYPE (*nit)); + unsigned original_precision = precision; + tree type, var_before; + gimple_stmt_iterator gsi, psi; + gimple stmt; + edge exit = single_dom_exit (loop); + gimple_seq stmts; + enum machine_mode mode; + bool unsigned_p = false; + + for (psi = gsi_start_phis (loop->header); + !gsi_end_p (psi); gsi_next (&psi)) + { + gimple phi = gsi_stmt (psi); + tree res = PHI_RESULT (phi); + bool uns; + + type = TREE_TYPE (res); + if (!is_gimple_reg (res) + || (!INTEGRAL_TYPE_P (type) + && !POINTER_TYPE_P (type)) + || TYPE_PRECISION (type) < precision) + continue; + + uns = POINTER_TYPE_P (type) | TYPE_UNSIGNED (type); + + if (TYPE_PRECISION (type) > precision) + unsigned_p = uns; + else + unsigned_p |= uns; + + precision = TYPE_PRECISION (type); + } + + mode = smallest_mode_for_size (precision, MODE_INT); + precision = GET_MODE_PRECISION (mode); + type = build_nonstandard_integer_type (precision, unsigned_p); + + if (original_precision != precision) + { + *nit = fold_convert (type, *nit); + *nit = force_gimple_operand (*nit, &stmts, true, NULL_TREE); + if (stmts) + gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts); + } + + if (bump_in_latch) + gsi = gsi_last_bb (loop->latch); + else + gsi = gsi_last_nondebug_bb (loop->header); + create_iv (build_int_cst_type (type, 0), build_int_cst (type, 1), NULL_TREE, + loop, &gsi, bump_in_latch, &var_before, NULL); + + rewrite_all_phi_nodes_with_iv (loop, var_before); + + stmt = last_stmt (exit->src); + /* Make the loop exit if the control condition is not satisfied. */ + if (exit->flags & EDGE_TRUE_VALUE) + { + edge te, fe; + + extract_true_false_edges_from_block (exit->src, &te, &fe); + te->flags = EDGE_FALSE_VALUE; + fe->flags = EDGE_TRUE_VALUE; + } + gimple_cond_set_code (stmt, LT_EXPR); + gimple_cond_set_lhs (stmt, var_before); + gimple_cond_set_rhs (stmt, *nit); + update_stmt (stmt); + + return var_before; +}