X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Ftree-ssa-loop-ivcanon.c;h=2b0988d1e52a827bcdf160d8192017b670eebb47;hp=67af0b374d6f7197085146f258ba24d1b5753f11;hb=578fcce9dee02ac2ac2a7f76634d8befccc51ef3;hpb=b2a225bac5d8cb3609d271a19b262114c97593d5 diff --git a/gcc/tree-ssa-loop-ivcanon.c b/gcc/tree-ssa-loop-ivcanon.c index 67af0b374d6..2b0988d1e52 100644 --- a/gcc/tree-ssa-loop-ivcanon.c +++ b/gcc/tree-ssa-loop-ivcanon.c @@ -1,24 +1,25 @@ /* Induction variable canonicalization. - Copyright (C) 2004, 2005, 2007 Free Software Foundation, Inc. - + Copyright (C) 2004, 2005, 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 . */ /* This pass detects the loops that iterate a constant number of times, - adds a canonical induction variable (step -1, tested against 0) + adds a canonical induction variable (step -1, tested against 0) and replaces the exit test. This enables the less powerful rtl level analysis to use this information. @@ -53,6 +54,7 @@ along with GCC; see the file COPYING3. If not see #include "params.h" #include "flags.h" #include "tree-inline.h" +#include "target.h" /* Specifies types of loops that may be unrolled. */ @@ -72,8 +74,9 @@ static void create_canonical_iv (struct loop *loop, edge exit, tree niter) { edge in; - tree cond, type, var; - block_stmt_iterator incr_at; + tree type, var; + gimple cond; + gimple_stmt_iterator incr_at; enum tree_code cmp; if (dump_file && (dump_flags & TDF_DETAILS)) @@ -97,16 +100,16 @@ create_canonical_iv (struct loop *loop, edge exit, tree niter) niter = fold_build2 (PLUS_EXPR, type, niter, build_int_cst (type, 1)); - incr_at = bsi_last (in->src); + incr_at = gsi_last_bb (in->src); create_iv (niter, build_int_cst (type, -1), NULL_TREE, loop, &incr_at, false, NULL, &var); cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR; - COND_EXPR_COND (cond) = build2 (cmp, boolean_type_node, - var, - build_int_cst (type, 0)); + gimple_cond_set_code (cond, cmp); + gimple_cond_set_lhs (cond, var); + gimple_cond_set_rhs (cond, build_int_cst (type, 0)); update_stmt (cond); } @@ -116,45 +119,212 @@ unsigned tree_num_loop_insns (struct loop *loop, eni_weights *weights) { basic_block *body = get_loop_body (loop); - block_stmt_iterator bsi; - unsigned size = 1, i; + gimple_stmt_iterator gsi; + unsigned size = 0, i; for (i = 0; i < loop->num_nodes; i++) - for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi)) - size += estimate_num_insns (bsi_stmt (bsi), weights); + for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi)) + size += estimate_num_insns (gsi_stmt (gsi), weights); free (body); return size; } -/* Estimate number of insns of completely unrolled loop. We assume - that the size of the unrolled loop is decreased in the - following way (the numbers of insns are based on what - estimate_num_insns returns for appropriate statements): +/* Describe size of loop as detected by tree_estimate_loop_size. */ +struct loop_size +{ + /* Number of instructions in the loop. */ + int overall; + + /* Number of instructions that will be likely optimized out in + peeled iterations of loop (i.e. computation based on induction + variable where induction variable starts at known constant.) */ + int eliminated_by_peeling; + + /* Same statistics for last iteration of loop: it is smaller because + instructions after exit are not executed. */ + int last_iteration; + int last_iteration_eliminated_by_peeling; +}; + +/* Return true if OP in STMT will be constant after peeling LOOP. */ + +static bool +constant_after_peeling (tree op, gimple stmt, struct loop *loop) +{ + affine_iv iv; - 1) exit condition gets removed (2 insns) - 2) increment of the control variable gets removed (2 insns) - 3) All remaining statements are likely to get simplified - due to constant propagation. Hard to estimate; just - as a heuristics we decrease the rest by 1/3. + if (is_gimple_min_invariant (op)) + return true; - NINSNS is the number of insns in the loop before unrolling. - NUNROLL is the number of times the loop is unrolled. */ + /* We can still fold accesses to constant arrays when index is known. */ + if (TREE_CODE (op) != SSA_NAME) + { + tree base = op; + + /* First make fast look if we see constant array inside. */ + while (handled_component_p (base)) + base = TREE_OPERAND (base, 0); + if ((DECL_P (base) + && TREE_STATIC (base) + && TREE_READONLY (base) + && (DECL_INITIAL (base) + || (!DECL_EXTERNAL (base) + && targetm.binds_local_p (base)))) + || CONSTANT_CLASS_P (base)) + { + /* If so, see if we understand all the indices. */ + base = op; + while (handled_component_p (base)) + { + if (TREE_CODE (base) == ARRAY_REF + && !constant_after_peeling (TREE_OPERAND (base, 1), stmt, loop)) + return false; + base = TREE_OPERAND (base, 0); + } + return true; + } + return false; + } + + /* Induction variables are constants. */ + if (!simple_iv (loop, loop_containing_stmt (stmt), op, &iv, false)) + return false; + if (!is_gimple_min_invariant (iv.base)) + return false; + if (!is_gimple_min_invariant (iv.step)) + return false; + return true; +} + +/* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. + Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT. */ + +static void +tree_estimate_loop_size (struct loop *loop, edge exit, struct loop_size *size) +{ + basic_block *body = get_loop_body (loop); + gimple_stmt_iterator gsi; + unsigned int i; + bool after_exit; + + size->overall = 0; + size->eliminated_by_peeling = 0; + size->last_iteration = 0; + size->last_iteration_eliminated_by_peeling = 0; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Estimating sizes for loop %i\n", loop->num); + for (i = 0; i < loop->num_nodes; i++) + { + if (exit && body[i] != exit->src + && dominated_by_p (CDI_DOMINATORS, body[i], exit->src)) + after_exit = true; + else + after_exit = false; + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " BB: %i, after_exit: %i\n", body[i]->index, after_exit); + + for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple stmt = gsi_stmt (gsi); + int num = estimate_num_insns (stmt, &eni_size_weights); + bool likely_eliminated = false; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " size: %3i ", num); + print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, 0); + } + + /* Look for reasons why we might optimize this stmt away. */ + + /* Exit conditional. */ + if (body[i] == exit->src && stmt == last_stmt (exit->src)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Exit condition will be eliminated.\n"); + likely_eliminated = true; + } + /* Sets of IV variables */ + else if (gimple_code (stmt) == GIMPLE_ASSIGN + && constant_after_peeling (gimple_assign_lhs (stmt), stmt, loop)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Induction variable computation will" + " be folded away.\n"); + likely_eliminated = true; + } + /* Assignments of IV variables. */ + else if (gimple_code (stmt) == GIMPLE_ASSIGN + && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME + && constant_after_peeling (gimple_assign_rhs1 (stmt), stmt,loop) + && (gimple_assign_rhs_class (stmt) != GIMPLE_BINARY_RHS + || constant_after_peeling (gimple_assign_rhs2 (stmt), + stmt, loop))) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Constant expression will be folded away.\n"); + likely_eliminated = true; + } + /* Conditionals. */ + else if (gimple_code (stmt) == GIMPLE_COND + && constant_after_peeling (gimple_cond_lhs (stmt), stmt, loop) + && constant_after_peeling (gimple_cond_rhs (stmt), stmt, loop)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Constant conditional.\n"); + likely_eliminated = true; + } + + size->overall += num; + if (likely_eliminated) + size->eliminated_by_peeling += num; + if (!after_exit) + { + size->last_iteration += num; + if (likely_eliminated) + size->last_iteration_eliminated_by_peeling += num; + } + } + } + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "size: %i-%i, last_iteration: %i-%i\n", size->overall, + size->eliminated_by_peeling, size->last_iteration, + size->last_iteration_eliminated_by_peeling); + + free (body); +} + +/* Estimate number of insns of completely unrolled loop. + It is (NUNROLL + 1) * size of loop body with taking into account + the fact that in last copy everything after exit conditional + is dead and that some instructions will be eliminated after + peeling. + + Loop body is likely going to simplify futher, this is difficult + to guess, we just decrease the result by 1/3. */ static unsigned HOST_WIDE_INT -estimated_unrolled_size (unsigned HOST_WIDE_INT ninsns, +estimated_unrolled_size (struct loop_size *size, unsigned HOST_WIDE_INT nunroll) { - HOST_WIDE_INT unr_insns = 2 * ((HOST_WIDE_INT) ninsns - 4) / 3; + HOST_WIDE_INT unr_insns = ((nunroll) + * (HOST_WIDE_INT) (size->overall + - size->eliminated_by_peeling)); + if (!nunroll) + unr_insns = 0; + unr_insns += size->last_iteration - size->last_iteration_eliminated_by_peeling; + + unr_insns = unr_insns * 2 / 3; if (unr_insns <= 0) unr_insns = 1; - unr_insns *= (nunroll + 1); return unr_insns; } /* Tries to unroll LOOP completely, i.e. NITER times. - UL determines which loops we are allowed to unroll. + UL determines which loops we are allowed to unroll. EXIT is the exit of the loop that should be eliminated. */ static bool @@ -163,7 +333,8 @@ try_unroll_loop_completely (struct loop *loop, enum unroll_level ul) { unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns; - tree cond; + gimple cond; + struct loop_size size; if (loop->inner) return false; @@ -181,13 +352,10 @@ try_unroll_loop_completely (struct loop *loop, if (ul == UL_SINGLE_ITER) return false; - ninsns = tree_num_loop_insns (loop, &eni_size_weights); + tree_estimate_loop_size (loop, exit, &size); + ninsns = size.overall; - if (n_unroll * ninsns - > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS)) - return false; - - unr_insns = estimated_unrolled_size (ninsns, n_unroll); + unr_insns = estimated_unrolled_size (&size, n_unroll); if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, " Loop size: %d\n", (int) ninsns); @@ -195,6 +363,17 @@ try_unroll_loop_completely (struct loop *loop, (int) unr_insns); } + if (unr_insns > ninsns + && (unr_insns + > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Not unrolling loop %d " + "(--param max-completely-peeled-insns limit reached).\n", + loop->num); + return false; + } + if (ul == UL_NO_GROWTH && unr_insns > ninsns) { @@ -216,11 +395,11 @@ try_unroll_loop_completely (struct loop *loop, sbitmap_ones (wont_exit); RESET_BIT (wont_exit, 0); - if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), - n_unroll, wont_exit, - exit, &to_remove, - DLTHE_FLAG_UPDATE_FREQ - | DLTHE_FLAG_COMPLETTE_PEEL)) + if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), + n_unroll, wont_exit, + exit, &to_remove, + DLTHE_FLAG_UPDATE_FREQ + | DLTHE_FLAG_COMPLETTE_PEEL)) { free_original_copy_tables (); free (wont_exit); @@ -239,8 +418,10 @@ try_unroll_loop_completely (struct loop *loop, } cond = last_stmt (exit->src); - COND_EXPR_COND (cond) = (exit->flags & EDGE_TRUE_VALUE) ? boolean_true_node - : boolean_false_node; + if (exit->flags & EDGE_TRUE_VALUE) + gimple_cond_make_true (cond); + else + gimple_cond_make_false (cond); update_stmt (cond); update_ssa (TODO_update_ssa); @@ -251,9 +432,9 @@ try_unroll_loop_completely (struct loop *loop, } /* Adds a canonical induction variable to LOOP if suitable. - CREATE_IV is true if we may create a new iv. UL determines + CREATE_IV is true if we may create a new iv. UL determines which loops we are allowed to completely unroll. If TRY_EVAL is true, we try - to determine the number of iterations of a loop by direct evaluation. + to determine the number of iterations of a loop by direct evaluation. Returns true if cfg is changed. */ static bool @@ -314,7 +495,7 @@ canonicalize_induction_variables (void) loop_iterator li; struct loop *loop; bool changed = false; - + FOR_EACH_LOOP (li, loop, 0) { changed |= canonicalize_loop_induction_variables (loop, @@ -342,6 +523,7 @@ tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer) struct loop *loop; bool changed; enum unroll_level ul; + int iteration = 0; do { @@ -349,7 +531,7 @@ tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer) FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST) { - if (may_increase_size && maybe_hot_bb_p (loop->header) + if (may_increase_size && optimize_loop_for_speed_p (loop) /* Unroll outermost loops only if asked to do so or they do not cause code growth. */ && (unroll_outer @@ -374,198 +556,8 @@ tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer) scev_reset (); } } - while (changed); - - return 0; -} - -/* Checks whether LOOP is empty. */ - -static bool -empty_loop_p (struct loop *loop) -{ - edge exit; - struct tree_niter_desc niter; - tree phi, def; - basic_block *body; - block_stmt_iterator bsi; - unsigned i; - tree stmt; - - /* If the loop has multiple exits, it is too hard for us to handle. - Similarly, if the exit is not dominating, we cannot determine - whether the loop is not infinite. */ - exit = single_dom_exit (loop); - if (!exit) - return false; - - /* The loop must be finite. */ - if (!number_of_iterations_exit (loop, exit, &niter, false)) - return false; - - /* Values of all loop exit phi nodes must be invariants. */ - for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi)) - { - if (!is_gimple_reg (PHI_RESULT (phi))) - continue; - - def = PHI_ARG_DEF_FROM_EDGE (phi, exit); - - if (!expr_invariant_in_loop_p (loop, def)) - return false; - } - - /* And there should be no memory modifying or from other reasons - unremovable statements. */ - body = get_loop_body (loop); - for (i = 0; i < loop->num_nodes; i++) - { - /* Irreducible region might be infinite. */ - if (body[i]->flags & BB_IRREDUCIBLE_LOOP) - { - free (body); - return false; - } - - for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi)) - { - stmt = bsi_stmt (bsi); - if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS) - || stmt_ann (stmt)->has_volatile_ops) - { - free (body); - return false; - } - - /* Also, asm statements and calls may have side effects and we - cannot change the number of times they are executed. */ - switch (TREE_CODE (stmt)) - { - case RETURN_EXPR: - case GIMPLE_MODIFY_STMT: - stmt = get_call_expr_in (stmt); - if (!stmt) - break; - - case CALL_EXPR: - if (TREE_SIDE_EFFECTS (stmt)) - { - free (body); - return false; - } - break; - - case ASM_EXPR: - /* We cannot remove volatile assembler. */ - if (ASM_VOLATILE_P (stmt)) - { - free (body); - return false; - } - break; - - default: - break; - } - } - } - free (body); - - return true; -} - -/* Remove LOOP by making it exit in the first iteration. */ - -static void -remove_empty_loop (struct loop *loop) -{ - edge exit = single_dom_exit (loop), non_exit; - tree cond_stmt = last_stmt (exit->src); - tree do_exit; - basic_block *body; - unsigned n_before, freq_in, freq_h; - gcov_type exit_count = exit->count; - - if (dump_file) - fprintf (dump_file, "Removing empty loop %d\n", loop->num); - - non_exit = EDGE_SUCC (exit->src, 0); - if (non_exit == exit) - non_exit = EDGE_SUCC (exit->src, 1); - - if (exit->flags & EDGE_TRUE_VALUE) - do_exit = boolean_true_node; - else - do_exit = boolean_false_node; - - COND_EXPR_COND (cond_stmt) = do_exit; - update_stmt (cond_stmt); - - /* Let us set the probabilities of the edges coming from the exit block. */ - exit->probability = REG_BR_PROB_BASE; - non_exit->probability = 0; - non_exit->count = 0; - - /* Update frequencies and counts. Everything before - the exit needs to be scaled FREQ_IN/FREQ_H times, - where FREQ_IN is the frequency of the entry edge - and FREQ_H is the frequency of the loop header. - Everything after the exit has zero frequency. */ - freq_h = loop->header->frequency; - freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop)); - if (freq_h != 0) - { - body = get_loop_body_in_dom_order (loop); - for (n_before = 1; n_before <= loop->num_nodes; n_before++) - if (body[n_before - 1] == exit->src) - break; - scale_bbs_frequencies_int (body, n_before, freq_in, freq_h); - scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before, - 0, 1); - free (body); - } - - /* Number of executions of exit is not changed, thus we need to restore - the original value. */ - exit->count = exit_count; -} - -/* Removes LOOP if it is empty. Returns true if LOOP is removed. CHANGED - is set to true if LOOP or any of its subloops is removed. */ - -static bool -try_remove_empty_loop (struct loop *loop, bool *changed) -{ - bool nonempty_subloop = false; - struct loop *sub; - - /* First, all subloops must be removed. */ - for (sub = loop->inner; sub; sub = sub->next) - nonempty_subloop |= !try_remove_empty_loop (sub, changed); + while (changed + && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS)); - if (nonempty_subloop || !empty_loop_p (loop)) - return false; - - remove_empty_loop (loop); - *changed = true; - return true; -} - -/* Remove the empty loops. */ - -unsigned int -remove_empty_loops (void) -{ - bool changed = false; - struct loop *loop; - - for (loop = current_loops->tree_root->inner; loop; loop = loop->next) - try_remove_empty_loop (loop, &changed); - - if (changed) - { - scev_reset (); - return TODO_cleanup_cfg; - } return 0; }