diff options
| -rw-r--r-- | gcc/ChangeLog | 13 | ||||
| -rw-r--r-- | gcc/tree-flow.h | 2 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-ivcanon.c | 91 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop.c | 7 |
4 files changed, 94 insertions, 19 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index e579c1d..9a94371e 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,18 @@ 2005-05-06 Zdenek Dvorak <dvorakz@suse.cz> + PR tree-optimization/19401 + * tree-flow.h (tree_unroll_loops_completely): Declaration changed. + * tree-ssa-loop-ivcanon.c (enum unroll_level): New. + (estimated_unrolled_size): New function. + (try_unroll_loop_completely, canonicalize_loop_induction_variables, + tree_unroll_loops_completely): Always unroll loops if the code size + does not increase. + * tree-ssa-loop.c (tree_complete_unroll): Indicate whether all + loops should be unrolled completely. + (gate_tree_complete_unroll): Run complete unrolling unconditionally. + +2005-05-06 Zdenek Dvorak <dvorakz@suse.cz> + PR rtl-optimization/21254 * loop-iv.c (iv_number_of_iterations): Simplify infiniteness assumptions for loops that otherwise do not roll. diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index d71238c..fc14564 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -693,7 +693,7 @@ bool empty_block_p (basic_block); void tree_ssa_lim (struct loops *); void tree_ssa_unswitch_loops (struct loops *); void canonicalize_induction_variables (struct loops *); -void tree_unroll_loops_completely (struct loops *); +void tree_unroll_loops_completely (struct loops *, bool); void tree_ssa_iv_optimize (struct loops *); bool number_of_iterations_exit (struct loop *, edge, diff --git a/gcc/tree-ssa-loop-ivcanon.c b/gcc/tree-ssa-loop-ivcanon.c index f2898b5..c4e64b2 100644 --- a/gcc/tree-ssa-loop-ivcanon.c +++ b/gcc/tree-ssa-loop-ivcanon.c @@ -55,6 +55,17 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #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 immediatelly 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. */ @@ -117,18 +128,43 @@ tree_num_loop_insns (struct loop *loop) 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. COMPLETELY_UNROLL is true if we should unroll the loop - even if it may cause code growth. EXIT is the exit of the loop - that should be eliminated. */ + 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, - bool completely_unroll) + enum unroll_level ul) { - unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll; + unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns; tree old_cond, cond, dont_exit, do_exit; if (loop->inner) @@ -144,7 +180,7 @@ try_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED, if (n_unroll) { - if (!completely_unroll) + if (ul == UL_SINGLE_ITER) return false; ninsns = tree_num_loop_insns (loop); @@ -152,6 +188,25 @@ try_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED, 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) @@ -194,14 +249,14 @@ try_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED, } /* 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. COMPLETELY_UNROLL is - true if we should do complete unrolling even if it may cause the code - growth. 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. */ + tree. CREATE_IV is true if we may create a new iv. UL determines what + 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, bool completely_unroll, + bool create_iv, enum unroll_level ul, bool try_eval) { edge exit = NULL; @@ -245,7 +300,7 @@ canonicalize_loop_induction_variables (struct loops *loops, struct loop *loop, fprintf (dump_file, " times.\n"); } - if (try_unroll_loop_completely (loops, loop, exit, niter, completely_unroll)) + if (try_unroll_loop_completely (loops, loop, exit, niter, ul)) return true; if (create_iv) @@ -270,7 +325,8 @@ canonicalize_induction_variables (struct loops *loops) if (loop) changed |= canonicalize_loop_induction_variables (loops, loop, - true, false, true); + true, UL_SINGLE_ITER, + true); } /* Clean up the information about numbers of iterations, since brute force @@ -281,14 +337,17 @@ canonicalize_induction_variables (struct loops *loops) cleanup_tree_cfg_loop (); } -/* Unroll LOOPS completely if they iterate just few times. */ +/* 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. */ void -tree_unroll_loops_completely (struct loops *loops) +tree_unroll_loops_completely (struct loops *loops, bool may_increase_size) { unsigned i; struct loop *loop; bool changed = false; + enum unroll_level ul = may_increase_size ? UL_ALL : UL_NO_GROWTH; for (i = 1; i < loops->num; i++) { @@ -298,7 +357,7 @@ tree_unroll_loops_completely (struct loops *loops) continue; changed |= canonicalize_loop_induction_variables (loops, loop, - false, true, + false, ul, !flag_tree_loop_ivcanon); } diff --git a/gcc/tree-ssa-loop.c b/gcc/tree-ssa-loop.c index b86820e..f7a96fb 100644 --- a/gcc/tree-ssa-loop.c +++ b/gcc/tree-ssa-loop.c @@ -323,13 +323,16 @@ tree_complete_unroll (void) if (!current_loops) return; - tree_unroll_loops_completely (current_loops); + tree_unroll_loops_completely (current_loops, + flag_unroll_loops + || flag_peel_loops + || optimize >= 3); } static bool gate_tree_complete_unroll (void) { - return flag_peel_loops || flag_unroll_loops; + return true; } struct tree_opt_pass pass_complete_unroll = |