diff options
Diffstat (limited to 'gcc-4.2.1-5666.3/gcc/tree-ssa-loop-ivcanon.c')
| -rw-r--r-- | gcc-4.2.1-5666.3/gcc/tree-ssa-loop-ivcanon.c | 582 |
1 files changed, 582 insertions, 0 deletions
diff --git a/gcc-4.2.1-5666.3/gcc/tree-ssa-loop-ivcanon.c b/gcc-4.2.1-5666.3/gcc/tree-ssa-loop-ivcanon.c new file mode 100644 index 000000000..a56679d32 --- /dev/null +++ b/gcc-4.2.1-5666.3/gcc/tree-ssa-loop-ivcanon.c @@ -0,0 +1,582 @@ +/* Induction variable canonicalization. + Copyright (C) 2004, 2005 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 2, 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 COPYING. If not, write to the Free +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ + +/* This pass detects the loops that iterate a constant number of times, + 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. + + This might spoil the code in some cases (by increasing register pressure). + Note that in the case the new variable is not needed, ivopts will get rid + of it, so it might only be a problem when there are no other linear induction + variables. In that case the created optimization possibilities are likely + to pay up. + + Additionally in case we detect that it is beneficial to unroll the + loop completely, we do it right here to expose the optimization + possibilities to the following passes. */ + +#include "config.h" +#include "system.h" +#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 "cfgloop.h" +#include "tree-pass.h" +#include "ggc.h" +#include "tree-chrec.h" +#include "tree-scalar-evolution.h" +#include "params.h" +#include "flags.h" +#include "tree-inline.h" + +/* Specifies types of loops that may be unrolled. */ + +enum unroll_level +{ + UL_SINGLE_ITER, /* Only loops that exit immediately in the first + iteration. */ + UL_NO_GROWTH, /* Only loops whose unrolling will not cause increase + of code size. */ + UL_ALL /* All suitable loops. */ +}; + +/* Adds a canonical induction variable to LOOP iterating NITER times. EXIT + is the exit edge whose condition is replaced. */ + +static void +create_canonical_iv (struct loop *loop, edge exit, tree niter) +{ + edge in; + tree cond, type, var; + block_stmt_iterator incr_at; + enum tree_code cmp; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num); + print_generic_expr (dump_file, niter, TDF_SLIM); + fprintf (dump_file, " iterations.\n"); + } + + cond = last_stmt (exit->src); + in = EDGE_SUCC (exit->src, 0); + if (in == exit) + in = EDGE_SUCC (exit->src, 1); + + /* Note that we do not need to worry about overflows, since + type of niter is always unsigned and all comparisons are + just for equality/nonequality -- i.e. everything works + with a modulo arithmetics. */ + + type = TREE_TYPE (niter); + niter = fold_build2 (PLUS_EXPR, type, + niter, + build_int_cst (type, 1)); + incr_at = bsi_last (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)); + update_stmt (cond); +} + +/* Computes an estimated number of insns in LOOP. */ + +unsigned +tree_num_loop_insns (struct loop *loop) +{ + basic_block *body = get_loop_body (loop); + block_stmt_iterator bsi; + unsigned size = 1, 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)); + 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): + + 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. + + NINSNS is the number of insns in the loop before unrolling. + NUNROLL is the number of times the loop is unrolled. */ + +static unsigned HOST_WIDE_INT +estimated_unrolled_size (unsigned HOST_WIDE_INT ninsns, + unsigned HOST_WIDE_INT nunroll) +{ + HOST_WIDE_INT unr_insns = 2 * ((HOST_WIDE_INT) ninsns - 4) / 3; + if (unr_insns <= 0) + unr_insns = 1; + unr_insns *= (nunroll + 1); + + return unr_insns; +} + +/* Tries to unroll LOOP completely, i.e. NITER times. LOOPS is the + loop tree. UL determines which loops we are allowed to unroll. + EXIT is the exit of the loop that should be eliminated. */ + +static bool +try_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED, + struct loop *loop, + edge exit, tree niter, + enum unroll_level ul) +{ + unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns; + tree old_cond, cond, dont_exit, do_exit; + + if (loop->inner) + return false; + + if (!host_integerp (niter, 1)) + return false; + n_unroll = tree_low_cst (niter, 1); + + max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES); + if (n_unroll > max_unroll) + return false; + + if (n_unroll) + { + if (ul == UL_SINGLE_ITER) + return false; + + ninsns = tree_num_loop_insns (loop); + + if (n_unroll * ninsns + > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS)) + return false; + + if (ul == UL_NO_GROWTH) + { + unr_insns = estimated_unrolled_size (ninsns, n_unroll); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " Loop size: %d\n", (int) ninsns); + fprintf (dump_file, " Estimated size after unrolling: %d\n", + (int) unr_insns); + } + + if (unr_insns > ninsns) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Not unrolling loop %d:\n", loop->num); + return false; + } + } + } + + if (exit->flags & EDGE_TRUE_VALUE) + { + dont_exit = boolean_false_node; + do_exit = boolean_true_node; + } + else + { + dont_exit = boolean_true_node; + do_exit = boolean_false_node; + } + cond = last_stmt (exit->src); + + if (n_unroll) + { + sbitmap wont_exit; + edge *edges_to_remove = XNEWVEC (edge, n_unroll); + unsigned int n_to_remove = 0; + + old_cond = COND_EXPR_COND (cond); + COND_EXPR_COND (cond) = dont_exit; + update_stmt (cond); + initialize_original_copy_tables (); + + wont_exit = sbitmap_alloc (n_unroll + 1); + sbitmap_ones (wont_exit); + RESET_BIT (wont_exit, 0); + + if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), + loops, n_unroll, wont_exit, + exit, edges_to_remove, + &n_to_remove, + DLTHE_FLAG_UPDATE_FREQ + | DLTHE_FLAG_COMPLETTE_PEEL)) + { + COND_EXPR_COND (cond) = old_cond; + update_stmt (cond); + free_original_copy_tables (); + free (wont_exit); + free (edges_to_remove); + return false; + } + free (wont_exit); + free (edges_to_remove); + free_original_copy_tables (); + } + + COND_EXPR_COND (cond) = do_exit; + update_stmt (cond); + + update_ssa (TODO_update_ssa); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num); + + return true; +} + +/* Adds a canonical induction variable to LOOP if suitable. LOOPS is the loops + tree. 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. + Returns true if cfg is changed. */ + +static bool +canonicalize_loop_induction_variables (struct loops *loops, struct loop *loop, + bool create_iv, enum unroll_level ul, + bool try_eval) +{ + edge exit = NULL; + tree niter; + + niter = number_of_iterations_in_loop (loop); + if (TREE_CODE (niter) == INTEGER_CST) + { + exit = loop->single_exit; + if (!just_once_each_iteration_p (loop, exit->src)) + return false; + + /* The result of number_of_iterations_in_loop is by one higher than + we expect (i.e. it returns number of executions of the exit + condition, not of the loop latch edge). */ + niter = fold_build2 (MINUS_EXPR, TREE_TYPE (niter), niter, + build_int_cst (TREE_TYPE (niter), 1)); + } + else + { + /* If the loop has more than one exit, try checking all of them + for # of iterations determinable through scev. */ + if (!loop->single_exit) + niter = find_loop_niter (loop, &exit); + + /* Finally if everything else fails, try brute force evaluation. */ + if (try_eval + && (chrec_contains_undetermined (niter) + || TREE_CODE (niter) != INTEGER_CST)) + niter = find_loop_niter_by_eval (loop, &exit); + + if (chrec_contains_undetermined (niter) + || TREE_CODE (niter) != INTEGER_CST) + return false; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Loop %d iterates ", loop->num); + print_generic_expr (dump_file, niter, TDF_SLIM); + fprintf (dump_file, " times.\n"); + } + + if (try_unroll_loop_completely (loops, loop, exit, niter, ul)) + return true; + + if (create_iv) + create_canonical_iv (loop, exit, niter); + + return false; +} + +/* The main entry point of the pass. Adds canonical induction variables + to the suitable LOOPS. */ + +unsigned int +canonicalize_induction_variables (struct loops *loops) +{ + unsigned i; + struct loop *loop; + bool changed = false; + + for (i = 1; i < loops->num; i++) + { + loop = loops->parray[i]; + + if (loop) + changed |= canonicalize_loop_induction_variables (loops, loop, + true, UL_SINGLE_ITER, + true); + } + + /* Clean up the information about numbers of iterations, since brute force + evaluation could reveal new information. */ + scev_reset (); + + if (changed) + return TODO_cleanup_cfg; + return 0; +} + +/* Unroll LOOPS completely if they iterate just few times. Unless + MAY_INCREASE_SIZE is true, perform the unrolling only if the + size of the code does not increase. */ + +unsigned int +tree_unroll_loops_completely (struct loops *loops, bool may_increase_size) +{ + unsigned i; + struct loop *loop; + bool changed = false; + enum unroll_level ul; + + for (i = 1; i < loops->num; i++) + { + loop = loops->parray[i]; + + if (!loop) + continue; + + if (may_increase_size && maybe_hot_bb_p (loop->header)) + ul = UL_ALL; + else + ul = UL_NO_GROWTH; + changed |= canonicalize_loop_induction_variables (loops, loop, + false, ul, + !flag_tree_loop_ivcanon); + } + + /* Clean up the information about numbers of iterations, since complete + unrolling might have invalidated it. */ + scev_reset (); + + if (changed) + return TODO_cleanup_cfg; + 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 MODIFY_EXPR: + 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; + + 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); + + 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 (struct loops *loops) +{ + bool changed = false; + struct loop *loop; + + for (loop = loops->tree_root->inner; loop; loop = loop->next) + try_remove_empty_loop (loop, &changed); + + if (changed) + { + scev_reset (); + return TODO_cleanup_cfg; + } + return 0; +} |