This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[lno] Make doloop work after unrolling
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 10 Feb 2004 21:12:41 +0100
- Subject: [lno] Make doloop work after unrolling
Hello,
this patch makes the unroller update the records about number of
iterations, which is important if doloop optimization is run afterwards
-- the simple loop analysis was clever enough to recognize the loops
anyway, but often the unrolling obfuscated the code enough so that the
analysis was unable to prove for example that the control variable does
not overflow (and of course it is also faster this way).
Zdenek
Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.49
diff -c -3 -p -r1.1.2.49 ChangeLog.lno
*** ChangeLog.lno 8 Feb 2004 23:18:03 -0000 1.1.2.49
--- ChangeLog.lno 10 Feb 2004 20:08:28 -0000
***************
*** 1,3 ****
--- 1,18 ----
+ 2004-02-10 Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz>
+
+ * loop-doloop.c (doloop_optimize): Use get_simple_loop_desc.
+ * loop-init.c (loop_optimizer_finalize): Free the simple loop
+ descriptions.
+ * loop-unroll.c (unroll_and_peel_loops): Do not free the simple loop
+ descriptions.
+ (decide_peel_once_rolling, decide_peel_completely,
+ decide_unroll_stupid): Test assumptions.
+ decide_unroll_constant_iterations, decide_unroll_runtime_iterations,
+ decide_peel_simple, peel_loop_simple, unroll_loop_stupid): Update
+ number of iterations info.
+ (unroll_loop_constant_iterations, unroll_loop_runtime_iterations,
+ (loop_exit_at_end_p): Use get_simple_loop_desc.
+
2004-02-08 Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz>
* cfgloop.h (struct niter_desc): Add first_special, extend,
Index: loop-doloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/loop-doloop.c,v
retrieving revision 1.1.2.2
diff -c -3 -p -r1.1.2.2 loop-doloop.c
*** loop-doloop.c 8 Feb 2004 23:18:04 -0000 1.1.2.2
--- loop-doloop.c 10 Feb 2004 20:08:28 -0000
*************** doloop_optimize (struct loop *loop)
*** 374,381 ****
rtx iterations_max;
rtx start_label;
rtx condition;
! unsigned level;
! struct niter_desc desc;
if (rtl_dump_file)
fprintf (rtl_dump_file, "Doloop: Processing loop %d.\n", loop->num);
--- 374,381 ----
rtx iterations_max;
rtx start_label;
rtx condition;
! unsigned level, est_niter;
! struct niter_desc *desc;
if (rtl_dump_file)
fprintf (rtl_dump_file, "Doloop: Processing loop %d.\n", loop->num);
*************** doloop_optimize (struct loop *loop)
*** 392,426 ****
iv_analysis_loop_init (loop);
/* Find the simple exit of a LOOP. */
! find_simple_exit (loop, &desc);
/* Check that loop is a candidate for a low-overhead looping insn. */
! if (!doloop_valid_p (loop, &desc))
{
if (rtl_dump_file)
fprintf (rtl_dump_file,
"Doloop: The loop is not suitable.\n");
return false;
}
! mode = desc.mode;
! if (desc.const_iter && desc.niter < 3)
{
if (rtl_dump_file)
fprintf (rtl_dump_file,
! "Doloop: Too few iterations (%ld) to be profitable.\n",
! (long int) desc.niter);
return false;
}
! iterations = desc.const_iter ? desc.niter_expr : const0_rtx;
! iterations_max = GEN_INT (desc.niter_max);
level = get_loop_level (loop) + 1;
/* Generate looping insn. If the pattern FAILs then give up trying
to modify the loop since there is some aspect the back-end does
not like. */
! start_label = block_label (desc.in_edge->dest);
doloop_reg = gen_reg_rtx (mode);
doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
GEN_INT (level), start_label);
--- 392,435 ----
iv_analysis_loop_init (loop);
/* Find the simple exit of a LOOP. */
! desc = get_simple_loop_desc (loop);
/* Check that loop is a candidate for a low-overhead looping insn. */
! if (!doloop_valid_p (loop, desc))
{
if (rtl_dump_file)
fprintf (rtl_dump_file,
"Doloop: The loop is not suitable.\n");
return false;
}
! mode = desc->mode;
! est_niter = 3;
! if (desc->const_iter)
! est_niter = desc->niter;
! /* If the estimate on number of iterations is reliable (comes from profile
! feedback), use it. Do not use it normally, since the expected number
! of iterations of unrolled loop is 2. */
! if (loop->header->count)
! est_niter = expected_loop_iterations (loop);
!
! if (est_niter < 3)
{
if (rtl_dump_file)
fprintf (rtl_dump_file,
! "Doloop: Too few iterations (%u) to be profitable.\n",
! est_niter);
return false;
}
! iterations = desc->const_iter ? desc->niter_expr : const0_rtx;
! iterations_max = GEN_INT (desc->niter_max);
level = get_loop_level (loop) + 1;
/* Generate looping insn. If the pattern FAILs then give up trying
to modify the loop since there is some aspect the back-end does
not like. */
! start_label = block_label (desc->in_edge->dest);
doloop_reg = gen_reg_rtx (mode);
doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
GEN_INT (level), start_label);
*************** doloop_optimize (struct loop *loop)
*** 461,467 ****
return false;
}
! doloop_modify (loop, &desc, doloop_seq, condition);
return true;
}
--- 470,476 ----
return false;
}
! doloop_modify (loop, desc, doloop_seq, condition);
return true;
}
Index: loop-init.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop-init.c,v
retrieving revision 1.2.2.7.2.1
diff -c -3 -p -r1.2.2.7.2.1 loop-init.c
*** loop-init.c 21 Jan 2004 01:10:35 -0000 1.2.2.7.2.1
--- loop-init.c 10 Feb 2004 20:08:28 -0000
*************** loop_optimizer_init (FILE *dumpfile)
*** 84,91 ****
--- 84,97 ----
void
loop_optimizer_finalize (struct loops *loops, FILE *dumpfile)
{
+ unsigned i;
+
if (!loops)
return;
+
+ for (i = 1; i < loops->num; i++)
+ if (loops->parray[i])
+ free_simple_loop_desc (loops->parray[i]);
/* Another dump. */
flow_loops_dump (loops, dumpfile, NULL, 1);
Index: loop-unroll.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop-unroll.c,v
retrieving revision 1.2.2.6.2.2
diff -c -3 -p -r1.2.2.6.2.2 loop-unroll.c
*** loop-unroll.c 30 Jan 2004 08:32:05 -0000 1.2.2.6.2.2
--- loop-unroll.c 10 Feb 2004 20:08:28 -0000
*************** unroll_and_peel_loops (struct loops *loo
*** 86,92 ****
{
struct loop *loop, *next;
bool check;
- unsigned i;
/* First perform complete loop peeling (it is almost surely a win,
and affects parameters for further decision a lot). */
--- 86,91 ----
*************** unroll_and_peel_loops (struct loops *loo
*** 146,155 ****
loop = next;
}
- for (i = 1; i < loops->num; i++)
- if (loops->parray[i])
- free_simple_loop_desc (loops->parray[i]);
-
iv_analysis_done ();
}
--- 145,150 ----
*************** unroll_and_peel_loops (struct loops *loo
*** 158,164 ****
static bool
loop_exit_at_end_p (struct loop *loop)
{
! struct niter_desc *desc = simple_loop_desc (loop);
rtx insn;
if (desc->in_edge->dest != loop->latch)
--- 153,159 ----
static bool
loop_exit_at_end_p (struct loop *loop)
{
! struct niter_desc *desc = get_simple_loop_desc (loop);
rtx insn;
if (desc->in_edge->dest != loop->latch)
*************** decide_peel_once_rolling (struct loop *l
*** 314,319 ****
--- 309,315 ----
/* Check number of iterations. */
if (!desc->simple_p
+ || desc->assumptions
|| !desc->const_iter
|| desc->niter != 0)
{
*************** decide_peel_completely (struct loop *loo
*** 381,386 ****
--- 377,383 ----
/* Check number of iterations. */
if (!desc->simple_p
+ || desc->assumptions
|| !desc->const_iter)
{
if (rtl_dump_file)
*************** peel_loop_completely (struct loops *loop
*** 426,432 ****
unsigned HOST_WIDE_INT npeel;
unsigned n_remove_edges, i;
edge *remove_edges, ei;
! struct niter_desc *desc = simple_loop_desc (loop);
npeel = desc->niter;
--- 423,429 ----
unsigned HOST_WIDE_INT npeel;
unsigned n_remove_edges, i;
edge *remove_edges, ei;
! struct niter_desc *desc = get_simple_loop_desc (loop);
npeel = desc->niter;
*************** decide_unroll_constant_iterations (struc
*** 505,511 ****
desc = get_simple_loop_desc (loop);
/* Check number of iterations. */
! if (!desc->simple_p || !desc->const_iter)
{
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Unable to prove that the loop iterates constant times\n");
--- 502,508 ----
desc = get_simple_loop_desc (loop);
/* Check number of iterations. */
! if (!desc->simple_p || !desc->const_iter || desc->assumptions)
{
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Unable to prove that the loop iterates constant times\n");
*************** unroll_loop_constant_iterations (struct
*** 590,596 ****
unsigned n_remove_edges, i;
edge *remove_edges;
unsigned max_unroll = loop->lpt_decision.times;
! struct niter_desc *desc = simple_loop_desc (loop);
niter = desc->niter;
--- 587,594 ----
unsigned n_remove_edges, i;
edge *remove_edges;
unsigned max_unroll = loop->lpt_decision.times;
! struct niter_desc *desc = get_simple_loop_desc (loop);
! bool exit_at_end = loop_exit_at_end_p (loop);
niter = desc->niter;
*************** unroll_loop_constant_iterations (struct
*** 605,611 ****
remove_edges = xcalloc (max_unroll + exit_mod + 1, sizeof (edge));
n_remove_edges = 0;
! if (!loop_exit_at_end_p (loop))
{
/* The exit is not at the end of the loop; leave exit test
in the first copy, so that the loops that start with test
--- 603,609 ----
remove_edges = xcalloc (max_unroll + exit_mod + 1, sizeof (edge));
n_remove_edges = 0;
! if (!exit_at_end)
{
/* The exit is not at the end of the loop; leave exit test
in the first copy, so that the loops that start with test
*************** unroll_loop_constant_iterations (struct
*** 619,630 ****
if (desc->noloop_assumptions)
RESET_BIT (wont_exit, 1);
! if (exit_mod
! && !duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
! loops, exit_mod,
! wont_exit, desc->out_edge, remove_edges, &n_remove_edges,
! DLTHE_FLAG_UPDATE_FREQ))
! abort ();
SET_BIT (wont_exit, 1);
}
--- 617,635 ----
if (desc->noloop_assumptions)
RESET_BIT (wont_exit, 1);
! if (exit_mod)
! {
! if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
! loops, exit_mod,
! wont_exit, desc->out_edge,
! remove_edges, &n_remove_edges,
! DLTHE_FLAG_UPDATE_FREQ))
! abort ();
!
! desc->noloop_assumptions = NULL_RTX;
! desc->niter -= exit_mod;
! desc->niter_max -= exit_mod;
! }
SET_BIT (wont_exit, 1);
}
*************** unroll_loop_constant_iterations (struct
*** 652,657 ****
--- 657,666 ----
DLTHE_FLAG_UPDATE_FREQ))
abort ();
+ desc->niter -= exit_mod + 1;
+ desc->niter_max -= exit_mod + 1;
+ desc->noloop_assumptions = NULL_RTX;
+
SET_BIT (wont_exit, 0);
SET_BIT (wont_exit, 1);
}
*************** unroll_loop_constant_iterations (struct
*** 668,673 ****
--- 677,703 ----
free (wont_exit);
+ if (exit_at_end)
+ {
+ basic_block exit_block = desc->in_edge->src->rbi->copy;
+ /* Find a new in and out edge; they are in the last copy we have made. */
+
+ if (exit_block->succ->dest == desc->out_edge->dest)
+ {
+ desc->out_edge = exit_block->succ;
+ desc->in_edge = exit_block->succ->succ_next;
+ }
+ else
+ {
+ desc->out_edge = exit_block->succ->succ_next;
+ desc->in_edge = exit_block->succ;
+ }
+ }
+
+ desc->niter /= max_unroll + 1;
+ desc->niter_max /= max_unroll + 1;
+ desc->niter_expr = GEN_INT (desc->niter);
+
/* Remove the edges. */
for (i = 0; i < n_remove_edges; i++)
remove_path (loops, remove_edges[i]);
*************** decide_unroll_runtime_iterations (struct
*** 716,722 ****
desc = get_simple_loop_desc (loop);
/* Check simpleness. */
! if (!desc->simple_p)
{
if (rtl_dump_file)
fprintf (rtl_dump_file,
--- 746,752 ----
desc = get_simple_loop_desc (loop);
/* Check simpleness. */
! if (!desc->simple_p || desc->assumptions)
{
if (rtl_dump_file)
fprintf (rtl_dump_file,
*************** decide_unroll_runtime_iterations (struct
*** 787,793 ****
static void
unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
{
! rtx niter, init_code, branch_code;
unsigned i, j, p;
basic_block preheader, *body, *dom_bbs, swtch, ezc_swtch;
unsigned n_dom_bbs;
--- 817,823 ----
static void
unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
{
! rtx old_niter, niter, init_code, branch_code, tmp;
unsigned i, j, p;
basic_block preheader, *body, *dom_bbs, swtch, ezc_swtch;
unsigned n_dom_bbs;
*************** unroll_loop_runtime_iterations (struct l
*** 797,803 ****
edge *remove_edges, e;
bool extra_zero_check, last_may_exit;
unsigned max_unroll = loop->lpt_decision.times;
! struct niter_desc *desc = simple_loop_desc (loop);
/* Remember blocks whose dominators will have to be updated. */
dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
--- 827,834 ----
edge *remove_edges, e;
bool extra_zero_check, last_may_exit;
unsigned max_unroll = loop->lpt_decision.times;
! struct niter_desc *desc = get_simple_loop_desc (loop);
! bool exit_at_end = loop_exit_at_end_p (loop);
/* Remember blocks whose dominators will have to be updated. */
dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
*************** unroll_loop_runtime_iterations (struct l
*** 818,824 ****
}
free (body);
! if (!loop_exit_at_end_p (loop))
{
/* Leave exit in first copy (for explanation why see comment in
unroll_loop_constant_iterations). */
--- 849,855 ----
}
free (body);
! if (!exit_at_end)
{
/* Leave exit in first copy (for explanation why see comment in
unroll_loop_constant_iterations). */
*************** unroll_loop_runtime_iterations (struct l
*** 839,848 ****
/* Get expression for number of iterations. */
start_sequence ();
! niter = copy_rtx (desc->niter_expr);
! if (!niter)
! abort ();
! niter = force_operand (niter, NULL);
/* Count modulo by ANDing it with max_unroll; we use the fact that
the number of unrollings is a power of two, and thus this is correct
--- 870,879 ----
/* Get expression for number of iterations. */
start_sequence ();
! old_niter = niter = gen_reg_rtx (desc->mode);
! tmp = force_operand (copy_rtx (desc->niter_expr), niter);
! if (tmp != niter)
! emit_move_insn (niter, tmp);
/* Count modulo by ANDing it with max_unroll; we use the fact that
the number of unrollings is a power of two, and thus this is correct
*************** unroll_loop_runtime_iterations (struct l
*** 943,953 ****
--- 974,1018 ----
free (wont_exit);
+ if (exit_at_end)
+ {
+ basic_block exit_block = desc->in_edge->src->rbi->copy;
+ /* Find a new in and out edge; they are in the last copy we have made. */
+
+ if (exit_block->succ->dest == desc->out_edge->dest)
+ {
+ desc->out_edge = exit_block->succ;
+ desc->in_edge = exit_block->succ->succ_next;
+ }
+ else
+ {
+ desc->out_edge = exit_block->succ->succ_next;
+ desc->in_edge = exit_block->succ;
+ }
+ }
+
/* Remove the edges. */
for (i = 0; i < n_remove_edges; i++)
remove_path (loops, remove_edges[i]);
free (remove_edges);
+ /* We must be careful when updating the number of iterations due to
+ preconditioning and the fact that the value must be valid at entry
+ of the loop. After passing through the above code, we see that
+ the correct new number of iterations is this: */
+ if (desc->const_iter)
+ abort ();
+ desc->niter_expr =
+ simplify_gen_binary (UDIV, desc->mode, old_niter, GEN_INT (max_unroll + 1));
+ desc->niter_max /= max_unroll + 1;
+ if (exit_at_end)
+ {
+ desc->niter_expr =
+ simplify_gen_binary (MINUS, desc->mode, desc->niter_expr, const1_rtx);
+ desc->noloop_assumptions = NULL_RTX;
+ desc->niter_max--;
+ }
+
if (rtl_dump_file)
fprintf (rtl_dump_file,
";; Unrolled loop %d times, counting # of iterations in runtime, %i insns\n",
*************** decide_peel_simple (struct loop *loop, i
*** 987,993 ****
desc = get_simple_loop_desc (loop);
/* Check number of iterations. */
! if (desc->simple_p && desc->const_iter)
{
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Loop iterates constant times\n");
--- 1052,1058 ----
desc = get_simple_loop_desc (loop);
/* Check number of iterations. */
! if (desc->simple_p && !desc->assumptions && desc->const_iter)
{
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Loop iterates constant times\n");
*************** peel_loop_simple (struct loops *loops, s
*** 1056,1061 ****
--- 1121,1127 ----
{
sbitmap wont_exit;
unsigned npeel = loop->lpt_decision.times;
+ struct niter_desc *desc = get_simple_loop_desc (loop);
wont_exit = sbitmap_alloc (npeel + 1);
sbitmap_zero (wont_exit);
*************** peel_loop_simple (struct loops *loops, s
*** 1067,1072 ****
--- 1133,1155 ----
free (wont_exit);
+ if (desc->simple_p)
+ {
+ if (desc->const_iter)
+ {
+ desc->niter -= npeel;
+ desc->niter_expr = GEN_INT (desc->niter);
+ desc->noloop_assumptions = NULL_RTX;
+ }
+ else
+ {
+ /* We cannot just update niter_expr, as its value might be clobbered
+ inside loop. We could handle this by counting the number into
+ temporary just like we do in runtime unrolling, but it does not
+ seem worthwhile. */
+ free_simple_loop_desc (loop);
+ }
+ }
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Peeling loop %d times\n", npeel);
}
*************** decide_unroll_stupid (struct loop *loop,
*** 1108,1114 ****
desc = get_simple_loop_desc (loop);
/* Check simpleness. */
! if (desc->simple_p)
{
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; The loop is simple\n");
--- 1191,1197 ----
desc = get_simple_loop_desc (loop);
/* Check simpleness. */
! if (desc->simple_p && !desc->assumptions)
{
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; The loop is simple\n");
*************** unroll_loop_stupid (struct loops *loops,
*** 1170,1175 ****
--- 1253,1259 ----
{
sbitmap wont_exit;
unsigned nunroll = loop->lpt_decision.times;
+ struct niter_desc *desc = get_simple_loop_desc (loop);
wont_exit = sbitmap_alloc (nunroll + 1);
sbitmap_zero (wont_exit);
*************** unroll_loop_stupid (struct loops *loops,
*** 1180,1185 ****
--- 1264,1280 ----
abort ();
free (wont_exit);
+
+ if (desc->simple_p)
+ {
+ /* We indeed may get here provided that there are nontrivial assumptions
+ for a loop to be really simple. We could update the counts, but the
+ problem is that we are unable to decide which exit will be taken
+ (not really true in case the number of iterations is constant,
+ but noone will do anything with this information, so we do not
+ worry about it). */
+ desc->simple_p = false;
+ }
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Unrolled loop %d times, %i insns\n",