Index: gcc/gcc/tree-ssa-loop-ivcanon.c |
diff --git a/gcc/gcc/tree-ssa-loop-ivcanon.c b/gcc/gcc/tree-ssa-loop-ivcanon.c |
index e278c55b08bbd3f0387bf8f03a968f13fd1e9441..2b0988d1e52a827bcdf160d8192017b670eebb47 100644 |
--- a/gcc/gcc/tree-ssa-loop-ivcanon.c |
+++ b/gcc/gcc/tree-ssa-loop-ivcanon.c |
@@ -1,24 +1,25 @@ |
/* Induction variable canonicalization. |
- Copyright (C) 2004, 2005, 2007, 2008 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 |
<http://www.gnu.org/licenses/>. */ |
/* 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. */ |
@@ -118,7 +120,7 @@ tree_num_loop_insns (struct loop *loop, eni_weights *weights) |
{ |
basic_block *body = get_loop_body (loop); |
gimple_stmt_iterator gsi; |
- unsigned size = 1, i; |
+ unsigned size = 0, i; |
for (i = 0; i < loop->num_nodes; i++) |
for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi)) |
@@ -128,34 +130,201 @@ tree_num_loop_insns (struct loop *loop, eni_weights *weights) |
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; |
+ |
+ if (is_gimple_min_invariant (op)) |
+ return true; |
- 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. |
+ /* 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; |
+ } |
- NINSNS is the number of insns in the loop before unrolling. |
- NUNROLL is the number of times the loop is unrolled. */ |
+ /* 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 |
@@ -165,6 +334,7 @@ try_unroll_loop_completely (struct loop *loop, |
{ |
unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns; |
gimple cond; |
+ struct loop_size size; |
if (loop->inner) |
return false; |
@@ -182,9 +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; |
- 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); |
@@ -261,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 |
@@ -324,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, |
@@ -352,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 |
{ |
@@ -384,192 +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; |
- basic_block *body; |
- gimple_stmt_iterator gsi; |
- unsigned i; |
- |
- /* 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 (gsi = gsi_start(phi_nodes (exit->dest)); !gsi_end_p (gsi); gsi_next (&gsi)) |
- { |
- gimple phi = gsi_stmt (gsi); |
- tree def; |
- |
- 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 (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi)) |
- { |
- gimple stmt = gsi_stmt (gsi); |
- |
- if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS) |
- || gimple_has_volatile_ops (stmt)) |
- { |
- 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 (gimple_code (stmt)) |
- { |
- case GIMPLE_CALL: |
- if (gimple_has_side_effects (stmt)) |
- { |
- free (body); |
- return false; |
- } |
- break; |
- |
- case GIMPLE_ASM: |
- /* We cannot remove volatile assembler. */ |
- if (gimple_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; |
- gimple cond_stmt = last_stmt (exit->src); |
- 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) |
- gimple_cond_make_true (cond_stmt); |
- else |
- gimple_cond_make_false (cond_stmt); |
- 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; |
+ while (changed |
+ && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS)); |
- /* 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 (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; |
} |
- |