This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] for PR19401
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Cc: rguenth at tat dot physik dot uni-tuebingen dot de
- Date: Fri, 14 Jan 2005 10:03:31 +0100
- Subject: [patch] for PR19401
Hello,
following the discussions on the gcc mailing list, there is another
proposal for the fix for this PR:
1) Always unroll loop completely if it does not cause code growth
(of course this is heuristics only, so it may be possible to
construct examples where the code size is increased, but it should
not be common).
2) Enables complete unrolling of all loops at -O3 and with -fpeel-loops.
Bootstrapped & regtested on ia64 and i686.
Zdenek
PR tree-optimization/19401
* tree-flow.h (tree_unroll_loops_completely): Declaration changed.
* tree-ssa-loop-ivcanon.c (enum unroll_level): New.
(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.
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.75
diff -c -3 -p -r2.75 tree-flow.h
*** tree-flow.h 10 Dec 2004 21:54:41 -0000 2.75
--- tree-flow.h 13 Jan 2005 23:55:03 -0000
*************** bool empty_block_p (basic_block);
*** 655,661 ****
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_ssa_iv_optimize (struct loops *);
void number_of_iterations_cond (tree, tree, tree, enum tree_code, tree, tree,
--- 655,661 ----
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 *, bool);
void tree_ssa_iv_optimize (struct loops *);
void number_of_iterations_cond (tree, tree, tree, enum tree_code, tree, tree,
Index: tree-ssa-loop-ivcanon.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivcanon.c,v
retrieving revision 2.5
diff -c -3 -p -r2.5 tree-ssa-loop-ivcanon.c
*** tree-ssa-loop-ivcanon.c 1 Oct 2004 18:26:31 -0000 2.5
--- tree-ssa-loop-ivcanon.c 13 Jan 2005 23:55:03 -0000
*************** Software Foundation, 59 Temple Place - S
*** 55,60 ****
--- 55,71 ----
#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. */
*************** tree_num_loop_insns (struct loop *loop)
*** 118,134 ****
}
/* 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. */
static bool
try_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED,
struct loop *loop,
edge exit, tree niter,
! bool completely_unroll)
{
unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll;
tree old_cond, cond, dont_exit, do_exit;
if (loop->inner)
--- 129,145 ----
}
/* 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;
+ HOST_WIDE_INT unr_insns;
tree old_cond, cond, dont_exit, do_exit;
if (loop->inner)
*************** try_unroll_loop_completely (struct loops
*** 144,150 ****
if (n_unroll)
{
! if (!completely_unroll)
return false;
ninsns = tree_num_loop_insns (loop);
--- 155,161 ----
if (n_unroll)
{
! if (ul == UL_SINGLE_ITER)
return false;
ninsns = tree_num_loop_insns (loop);
*************** try_unroll_loop_completely (struct loops
*** 152,157 ****
--- 163,200 ----
if (n_unroll * ninsns
> (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
return false;
+
+ if (ul == UL_NO_GROWTH)
+ {
+ /* Estimate number of insns of the 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. */
+ unr_insns = 2 * ((HOST_WIDE_INT) ninsns - 4) / 3;
+ if (unr_insns <= 0)
+ unr_insns = 1;
+ unr_insns *= (n_unroll + 1);
+
+ 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 ((unsigned HOST_WIDE_INT) 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)
*************** try_unroll_loop_completely (struct loops
*** 168,176 ****
if (n_unroll)
{
- if (!flag_unroll_loops)
- return false;
-
old_cond = COND_EXPR_COND (cond);
COND_EXPR_COND (cond) = dont_exit;
modify_stmt (cond);
--- 211,216 ----
*************** try_unroll_loop_completely (struct loops
*** 194,207 ****
}
/* 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. */
static bool
canonicalize_loop_induction_variables (struct loops *loops, struct loop *loop,
! bool create_iv, bool completely_unroll,
bool try_eval)
{
edge exit = NULL;
--- 234,247 ----
}
/* 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 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, enum unroll_level ul,
bool try_eval)
{
edge exit = NULL;
*************** canonicalize_loop_induction_variables (s
*** 234,240 ****
fprintf (dump_file, " times.\n");
}
! if (try_unroll_loop_completely (loops, loop, exit, niter, completely_unroll))
return true;
if (create_iv)
--- 274,280 ----
fprintf (dump_file, " times.\n");
}
! if (try_unroll_loop_completely (loops, loop, exit, niter, ul))
return true;
if (create_iv)
*************** canonicalize_induction_variables (struct
*** 257,263 ****
loop = loops->parray[i];
if (loop)
! canonicalize_loop_induction_variables (loops, loop, true, false, true);
}
/* Clean up the information about numbers of iterations, since brute force
--- 297,304 ----
loop = loops->parray[i];
if (loop)
! canonicalize_loop_induction_variables (loops, loop,
! true, UL_SINGLE_ITER, true);
}
/* Clean up the information about numbers of iterations, since brute force
*************** canonicalize_induction_variables (struct
*** 271,284 ****
#endif
}
! /* Unroll LOOPS completely if they iterate just few times. */
void
! tree_unroll_loops_completely (struct loops *loops)
{
unsigned i;
struct loop *loop;
bool changed = false;
for (i = 1; i < loops->num; i++)
{
--- 312,328 ----
#endif
}
! /* 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, 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++)
{
*************** tree_unroll_loops_completely (struct loo
*** 288,294 ****
continue;
changed |= canonicalize_loop_induction_variables (loops, loop,
! false, true,
!flag_tree_loop_ivcanon);
}
--- 332,338 ----
continue;
changed |= canonicalize_loop_induction_variables (loops, loop,
! false, ul,
!flag_tree_loop_ivcanon);
}
Index: tree-ssa-loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop.c,v
retrieving revision 2.23
diff -c -3 -p -r2.23 tree-ssa-loop.c
*** tree-ssa-loop.c 26 Nov 2004 06:42:25 -0000 2.23
--- tree-ssa-loop.c 13 Jan 2005 23:55:03 -0000
*************** tree_complete_unroll (void)
*** 334,346 ****
if (!current_loops)
return;
! tree_unroll_loops_completely (current_loops);
}
static bool
gate_tree_complete_unroll (void)
{
! return flag_unroll_loops != 0;
}
struct tree_opt_pass pass_complete_unroll =
--- 334,349 ----
if (!current_loops)
return;
! tree_unroll_loops_completely (current_loops,
! flag_unroll_loops
! || flag_peel_loops
! || optimize >= 3);
}
static bool
gate_tree_complete_unroll (void)
{
! return true;
}
struct tree_opt_pass pass_complete_unroll =