/* Loop unrolling and peeling.
- Copyright (C) 2002 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2003 Free Software Foundation, Inc.
This file is part of GCC.
#include "expr.h"
/* This pass performs loop unrolling and peeling. We only perform these
- optimalizations on innermost loops (with single exception) because
+ optimizations on innermost loops (with single exception) because
the impact on performance is greatest here, and we want to avoid
unnecessary code size growth. The gain is caused by greater sequentiality
- of code, better code to optimize for futher passes and in some cases
+ of code, better code to optimize for further passes and in some cases
by fewer testings of exit conditions. The main problem is code growth,
that impacts performance negatively due to effect of caches.
showed that this choice may affect performance in order of several %.
*/
-static void decide_unrolling_and_peeling PARAMS ((struct loops *, int));
-static void peel_loops_completely PARAMS ((struct loops *, int));
-static void decide_peel_simple PARAMS ((struct loops *, struct loop *, int));
-static void decide_peel_once_rolling PARAMS ((struct loops *, struct loop *, int));
-static void decide_peel_completely PARAMS ((struct loops *, struct loop *, int));
-static void decide_unroll_stupid PARAMS ((struct loops *, struct loop *, int));
-static void decide_unroll_constant_iterations PARAMS ((struct loops *, struct loop *, int));
-static void decide_unroll_runtime_iterations PARAMS ((struct loops *, struct loop *, int));
-static void peel_loop_simple PARAMS ((struct loops *, struct loop *));
-static void peel_loop_completely PARAMS ((struct loops *, struct loop *));
-static void unroll_loop_stupid PARAMS ((struct loops *, struct loop *));
-static void unroll_loop_constant_iterations PARAMS ((struct loops *,
- struct loop *));
-static void unroll_loop_runtime_iterations PARAMS ((struct loops *,
- struct loop *));
+static void decide_unrolling_and_peeling (struct loops *, int);
+static void peel_loops_completely (struct loops *, int);
+static void decide_peel_simple (struct loop *, int);
+static void decide_peel_once_rolling (struct loop *, int);
+static void decide_peel_completely (struct loop *, int);
+static void decide_unroll_stupid (struct loop *, int);
+static void decide_unroll_constant_iterations (struct loop *, int);
+static void decide_unroll_runtime_iterations (struct loop *, int);
+static void peel_loop_simple (struct loops *, struct loop *);
+static void peel_loop_completely (struct loops *, struct loop *);
+static void unroll_loop_stupid (struct loops *, struct loop *);
+static void unroll_loop_constant_iterations (struct loops *, struct loop *);
+static void unroll_loop_runtime_iterations (struct loops *, struct loop *);
/* Unroll and/or peel (depending on FLAGS) LOOPS. */
void
-unroll_and_peel_loops (loops, flags)
- struct loops *loops;
- int flags;
+unroll_and_peel_loops (struct loops *loops, int flags)
{
struct loop *loop, *next;
int check;
if (check)
{
#ifdef ENABLE_CHECKING
- verify_dominators (loops->cfg.dom);
+ verify_dominators (CDI_DOMINATORS);
verify_loop_structure (loops);
#endif
}
/* Check whether to peel LOOPS (depending on FLAGS) completely and do so. */
static void
-peel_loops_completely (loops, flags)
- struct loops *loops;
- int flags;
+peel_loops_completely (struct loops *loops, int flags)
{
struct loop *loop, *next;
loop->lpt_decision.decision = LPT_NONE;
loop->has_desc = 0;
-
+
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Considering loop %d for complete peeling\n",
loop->num);
loop->ninsns = num_loop_insns (loop);
- decide_peel_once_rolling (loops, loop, flags);
+ decide_peel_once_rolling (loop, flags);
if (loop->lpt_decision.decision == LPT_NONE)
- decide_peel_completely (loops, loop, flags);
+ decide_peel_completely (loop, flags);
if (loop->lpt_decision.decision == LPT_PEEL_COMPLETELY)
{
peel_loop_completely (loops, loop);
#ifdef ENABLE_CHECKING
- verify_dominators (loops->cfg.dom);
+ verify_dominators (CDI_DOMINATORS);
verify_loop_structure (loops);
#endif
}
/* Decide whether unroll or peel LOOPS (depending on FLAGS) and how much. */
static void
-decide_unrolling_and_peeling (loops, flags)
- struct loops *loops;
- int flags;
+decide_unrolling_and_peeling (struct loops *loops, int flags)
{
struct loop *loop = loops->tree_root, *next;
/* Try transformations one by one in decreasing order of
priority. */
- decide_unroll_constant_iterations (loops, loop, flags);
+ decide_unroll_constant_iterations (loop, flags);
if (loop->lpt_decision.decision == LPT_NONE)
- decide_unroll_runtime_iterations (loops, loop, flags);
+ decide_unroll_runtime_iterations (loop, flags);
if (loop->lpt_decision.decision == LPT_NONE)
- decide_unroll_stupid (loops, loop, flags);
+ decide_unroll_stupid (loop, flags);
if (loop->lpt_decision.decision == LPT_NONE)
- decide_peel_simple (loops, loop, flags);
+ decide_peel_simple (loop, flags);
loop = next;
}
/* Decide whether the LOOP is once rolling and suitable for complete
peeling. */
static void
-decide_peel_once_rolling (loops, loop, flags)
- struct loops *loops;
- struct loop *loop;
- int flags ATTRIBUTE_UNUSED;
+decide_peel_once_rolling (struct loop *loop, int flags ATTRIBUTE_UNUSED)
{
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Considering peeling once rolling loop\n");
}
/* Check for simple loops. */
- loop->simple = simple_loop_p (loops, loop, &loop->desc);
+ loop->simple = simple_loop_p (loop, &loop->desc);
loop->has_desc = 1;
/* Check number of iterations. */
- if (!loop->simple || !loop->desc.const_iter || loop->desc.niter !=0)
+ if (!loop->simple || !loop->desc.const_iter || loop->desc.niter != 0)
{
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Unable to prove that the loop rolls exactly once\n");
/* Decide whether the LOOP is suitable for complete peeling. */
static void
-decide_peel_completely (loops, loop, flags)
- struct loops *loops;
- struct loop *loop;
- int flags ATTRIBUTE_UNUSED;
+decide_peel_completely (struct loop *loop, int flags ATTRIBUTE_UNUSED)
{
unsigned npeel;
/* Check for simple loops. */
if (!loop->has_desc)
- loop->simple = simple_loop_p (loops, loop, &loop->desc);
+ {
+ loop->simple = simple_loop_p (loop, &loop->desc);
+ loop->has_desc = 1;
+ }
/* Check number of iterations. */
if (!loop->simple || !loop->desc.const_iter)
if (loop->desc.niter > npeel - 1)
{
if (rtl_dump_file)
- {
+ {
fprintf (rtl_dump_file, ";; Not peeling loop completely, rolls too much (");
fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC,(HOST_WIDEST_INT) loop->desc.niter);
fprintf (rtl_dump_file, " iterations > %d [maximum peelings])\n", npeel);
/* Peel all iterations of LOOP, remove exit edges and cancel the loop
completely. The transformation done:
-
+
for (i = 0; i < 4; i++)
body;
==>
-
- i = 0;
+
+ i = 0;
body; i++;
body; i++;
body; i++;
body; i++;
*/
static void
-peel_loop_completely (loops, loop)
- struct loops *loops;
- struct loop *loop;
+peel_loop_completely (struct loops *loops, struct loop *loop)
{
sbitmap wont_exit;
unsigned HOST_WIDE_INT npeel;
unsigned n_remove_edges, i;
edge *remove_edges;
struct loop_desc *desc = &loop->desc;
-
+
npeel = desc->niter;
if (npeel)
/* Decide whether to unroll LOOP iterating constant number of times and how much. */
static void
-decide_unroll_constant_iterations (loops, loop, flags)
- struct loops *loops;
- struct loop *loop;
- int flags;
+decide_unroll_constant_iterations (struct loop *loop, int flags)
{
unsigned nunroll, nunroll_by_av, best_copies, best_unroll = -1, n_copies, i;
/* Check for simple loops. */
if (!loop->has_desc)
- loop->simple = simple_loop_p (loops, loop, &loop->desc);
+ {
+ loop->simple = simple_loop_p (loop, &loop->desc);
+ loop->has_desc = 1;
+ }
/* Check number of iterations. */
if (!loop->simple || !loop->desc.const_iter)
/* Success; now compute number of iterations to unroll. We alter
nunroll so that as few as possible copies of loop body are
- neccesary, while still not decreasing the number of unrollings
+ necessary, while still not decreasing the number of unrollings
too much (at most by 1). */
best_copies = 2 * nunroll + 10;
}
/* Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES + 1
- times. The transformation does this:
-
+ times. The transformation does this:
+
for (i = 0; i < 102; i++)
body;
-
+
==>
-
+
i = 0;
body; i++;
body; i++;
}
*/
static void
-unroll_loop_constant_iterations (loops, loop)
- struct loops *loops;
- struct loop *loop;
+unroll_loop_constant_iterations (struct loops *loops, struct loop *loop)
{
unsigned HOST_WIDE_INT niter;
unsigned exit_mod;
/* Decide whether to unroll LOOP iterating runtime computable number of times
and how much. */
static void
-decide_unroll_runtime_iterations (loops, loop, flags)
- struct loops *loops;
- struct loop *loop;
- int flags;
+decide_unroll_runtime_iterations (struct loop *loop, int flags)
{
unsigned nunroll, nunroll_by_av, i;
/* Check for simple loops. */
if (!loop->has_desc)
- loop->simple = simple_loop_p (loops, loop, &loop->desc);
+ {
+ loop->simple = simple_loop_p (loop, &loop->desc);
+ loop->has_desc = 1;
+ }
/* Check simpleness. */
if (!loop->simple)
/* Unroll LOOP for that we are able to count number of iterations in runtime
LOOP->LPT_DECISION.TIMES + 1 times. The transformation does this (with some
extra care for case n < 0):
-
+
for (i = 0; i < n; i++)
body;
-
+
==>
-
+
i = 0;
mod = n % 4;
-
+
switch (mod)
{
case 3:
body; i++;
case 0: ;
}
-
+
while (i < n)
{
body; i++;
}
*/
static void
-unroll_loop_runtime_iterations (loops, loop)
- struct loops *loops;
- struct loop *loop;
+unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
{
rtx niter, init_code, branch_code, jump, label;
unsigned i, j, p;
unsigned nldom;
basic_block *ldom;
- nldom = get_dominated_by (loops->cfg.dom, body[i], &ldom);
+ nldom = get_dominated_by (CDI_DOMINATORS, body[i], &ldom);
for (j = 0; j < nldom; j++)
if (!flow_bb_inside_loop_p (loop, ldom[j]))
dom_bbs[n_dom_bbs++] = ldom[j];
end_sequence ();
/* Precondition the loop. */
- loop_split_edge_with (loop_preheader_edge (loop), init_code, loops);
+ loop_split_edge_with (loop_preheader_edge (loop), init_code);
remove_edges = xcalloc (max_unroll + n_peel + 1, sizeof (edge));
n_remove_edges = 0;
/* Record the place where switch will be built for preconditioning. */
swtch = loop_split_edge_with (loop_preheader_edge (loop),
- NULL_RTX, loops);
+ NULL_RTX);
for (i = 0; i < n_peel; i++)
{
loops, 1,
wont_exit, desc->out_edge, remove_edges, &n_remove_edges,
DLTHE_FLAG_UPDATE_FREQ))
- abort ();
+ abort ();
- if (i != n_peel)
- {
- /* Create item for switch. */
- j = n_peel - i - (extra_zero_check ? 0 : 1);
- p = REG_BR_PROB_BASE / (i + 2);
-
- preheader = loop_split_edge_with (loop_preheader_edge (loop),
- NULL_RTX, loops);
- label = block_label (preheader);
- start_sequence ();
- do_compare_rtx_and_jump (copy_rtx (niter), GEN_INT (j), EQ, 0,
- GET_MODE (desc->var), NULL_RTX, NULL_RTX,
- label);
- jump = get_last_insn ();
- JUMP_LABEL (jump) = label;
- REG_NOTES (jump)
- = gen_rtx_EXPR_LIST (REG_BR_PROB,
- GEN_INT (p), REG_NOTES (jump));
-
- LABEL_NUSES (label)++;
- branch_code = get_insns ();
- end_sequence ();
-
- swtch = loop_split_edge_with (swtch->pred, branch_code, loops);
- set_immediate_dominator (loops->cfg.dom, preheader, swtch);
- swtch->succ->probability = REG_BR_PROB_BASE - p;
- e = make_edge (swtch, preheader,
- swtch->succ->flags & EDGE_IRREDUCIBLE_LOOP);
- e->probability = p;
- }
+ /* Create item for switch. */
+ j = n_peel - i - (extra_zero_check ? 0 : 1);
+ p = REG_BR_PROB_BASE / (i + 2);
+
+ preheader = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
+ label = block_label (preheader);
+ start_sequence ();
+ do_compare_rtx_and_jump (copy_rtx (niter), GEN_INT (j), EQ, 0,
+ GET_MODE (desc->var), NULL_RTX, NULL_RTX,
+ label);
+ jump = get_last_insn ();
+ JUMP_LABEL (jump) = label;
+ REG_NOTES (jump)
+ = gen_rtx_EXPR_LIST (REG_BR_PROB,
+ GEN_INT (p), REG_NOTES (jump));
+
+ LABEL_NUSES (label)++;
+ branch_code = get_insns ();
+ end_sequence ();
+
+ swtch = loop_split_edge_with (swtch->pred, branch_code);
+ set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
+ swtch->succ->probability = REG_BR_PROB_BASE - p;
+ e = make_edge (swtch, preheader,
+ swtch->succ->flags & EDGE_IRREDUCIBLE_LOOP);
+ e->probability = p;
}
if (extra_zero_check)
/* Add branch for zero iterations. */
p = REG_BR_PROB_BASE / (max_unroll + 1);
swtch = ezc_swtch;
- preheader = loop_split_edge_with (loop_preheader_edge (loop),
- NULL_RTX, loops);
+ preheader = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
label = block_label (preheader);
start_sequence ();
do_compare_rtx_and_jump (copy_rtx (niter), const0_rtx, EQ, 0,
REG_NOTES (jump)
= gen_rtx_EXPR_LIST (REG_BR_PROB,
GEN_INT (p), REG_NOTES (jump));
-
+
LABEL_NUSES (label)++;
branch_code = get_insns ();
end_sequence ();
- swtch = loop_split_edge_with (swtch->succ, branch_code, loops);
- set_immediate_dominator (loops->cfg.dom, preheader, swtch);
+ swtch = loop_split_edge_with (swtch->succ, branch_code);
+ set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
swtch->succ->probability = REG_BR_PROB_BASE - p;
e = make_edge (swtch, preheader,
swtch->succ->flags & EDGE_IRREDUCIBLE_LOOP);
}
/* Recount dominators for outer blocks. */
- iterate_fix_dominators (loops->cfg.dom, dom_bbs, n_dom_bbs);
+ iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
/* And unroll loop. */
RESET_BIT (wont_exit, may_exit_copy);
if (!duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
- loops, max_unroll,
+ loops, max_unroll,
wont_exit, desc->out_edge, remove_edges, &n_remove_edges,
DLTHE_FLAG_UPDATE_FREQ))
abort ();
";; Unrolled loop %d times, counting # of iterations in runtime, %i insns\n",
max_unroll, num_loop_insns (loop));
}
-
+
/* Decide whether to simply peel LOOP and how much. */
static void
-decide_peel_simple (loops, loop, flags)
- struct loops *loops;
- struct loop *loop;
- int flags;
+decide_peel_simple (struct loop *loop, int flags)
{
unsigned npeel;
/* Check for simple loops. */
if (!loop->has_desc)
- loop->simple = simple_loop_p (loops, loop, &loop->desc);
+ {
+ loop->simple = simple_loop_p (loop, &loop->desc);
+ loop->has_desc = 1;
+ }
/* Check number of iterations. */
if (loop->simple && loop->desc.const_iter)
end: ;
*/
static void
-peel_loop_simple (loops, loop)
- struct loops *loops;
- struct loop *loop;
+peel_loop_simple (struct loops *loops, struct loop *loop)
{
sbitmap wont_exit;
unsigned npeel = loop->lpt_decision.times;
loops, npeel, wont_exit, NULL, NULL, NULL,
DLTHE_FLAG_UPDATE_FREQ))
abort ();
-
+
free (wont_exit);
if (rtl_dump_file)
/* Decide whether to unroll LOOP stupidly and how much. */
static void
-decide_unroll_stupid (loops, loop, flags)
- struct loops *loops;
- struct loop *loop;
- int flags;
+decide_unroll_stupid (struct loop *loop, int flags)
{
unsigned nunroll, nunroll_by_av, i;
/* Check for simple loops. */
if (!loop->has_desc)
- loop->simple = simple_loop_p (loops, loop, &loop->desc);
+ {
+ loop->simple = simple_loop_p (loop, &loop->desc);
+ loop->has_desc = 1;
+ }
/* Check simpleness. */
if (loop->simple)
}
/* Success. Now force nunroll to be power of 2, as it seems that this
- improves results (partially because of better aligments, partially
+ improves results (partially because of better alignments, partially
because of some dark magic). */
for (i = 1; 2 * i <= nunroll; i *= 2);
}
*/
static void
-unroll_loop_stupid (loops, loop)
- struct loops *loops;
- struct loop *loop;
+unroll_loop_stupid (struct loops *loops, struct loop *loop)
{
sbitmap wont_exit;
unsigned nunroll = loop->lpt_decision.times;
abort ();
free (wont_exit);
-
+
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Unrolled loop %d times, %i insns\n",
nunroll, num_loop_insns (loop));
OSDN Git Service
