This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [CFG] handle loop with multiple exits
Hello.
> > ! /* Counts constant number of iterations of the loop described by DESC;
> > ! returns false if impossible. */
> > ! static bool
> > ! constant_iterations (desc, niter)
> > ! struct loop_desc *desc;
> > ! unsigned HOST_WIDE_INT *niter;
> > ! {
> > ! rtx test, expr;
> > !
> > ! test = test_for_iteration (desc, 0);
> > ! if (test && test == const0_rtx)
> > ! {
> > ! *niter = 0;
> > ! return true;
> > ! }
> > !
> > ! if (!(expr = count_loop_iterations (desc, true)))
> > ! abort ();
> > !
> > ! if (GET_CODE (expr) != CONST_INT)
> > ! return false;
> > !
> > ! *niter = INTVAL (expr);
> > ! return true;
> > ! }
>
> Here I guess you need to ensure test to be const_true_rtx as well,
> otherwise we can lose for loops of type
> for (i=a;a<a+10;i++)
> where a+10 wraps around, so the loop never iterates.
Here is the corrected patch.
Zdenek
Index: loop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.h,v
retrieving revision 1.56.2.12
diff -c -3 -p -r1.56.2.12 loop.h
*** loop.h 3 May 2002 22:29:12 -0000 1.56.2.12
--- loop.h 4 May 2002 20:37:19 -0000
*************** struct loop_desc
*** 441,449 ****
int grow; /* 1 if it grows, 0 if it decreases. */
rtx lim; /* Expression var is compared with. */
rtx init; /* Initial value of var. */
! HOST_WIDE_INT lim_n;
! HOST_WIDE_INT init_n; /* And their integer values. */
! bool const_iter; /* True if both limits are integer constants. */
enum rtx_code cond; /* Exit condition. */
int neg; /* Set to 1 if loop ends when condition is satisfied. */
edge out_edge; /* The exit edge. */
--- 441,449 ----
int grow; /* 1 if it grows, 0 if it decreases. */
rtx lim; /* Expression var is compared with. */
rtx init; /* Initial value of var. */
! bool const_iter; /* True if it iterates constant number of times. */
! unsigned HOST_WIDE_INT niter;
! /* Number of iterations if it is constant. */
enum rtx_code cond; /* Exit condition. */
int neg; /* Set to 1 if loop ends when condition is satisfied. */
edge out_edge; /* The exit edge. */
Index: unroll-new.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/unroll-new.c,v
retrieving revision 1.1.2.21
diff -c -3 -p -r1.1.2.21 unroll-new.c
*** unroll-new.c 4 May 2002 19:55:18 -0000 1.1.2.21
--- unroll-new.c 4 May 2002 20:37:21 -0000
*************** Software Foundation, 59 Temple Place - S
*** 42,49 ****
#include "params.h"
#include "output.h"
- static basic_block simple_exit PARAMS ((struct loops *, struct loop *,
- basic_block *, int *));
static bool simple_condition_p PARAMS ((struct loop *, basic_block *,
rtx, struct loop_desc *));
static basic_block simple_increment PARAMS ((struct loops *, struct loop *,
--- 42,47 ----
*************** static basic_block simple_increment PARA
*** 52,57 ****
--- 50,60 ----
static rtx variable_initial_value PARAMS ((struct loop *, rtx));
static bool simple_loop_p PARAMS ((struct loops *, struct loop *,
struct loop_desc *));
+ static bool simple_loop_exit_p PARAMS ((struct loops *, struct loop *,
+ edge, basic_block *,
+ struct loop_desc *));
+ static bool constant_iterations PARAMS ((struct loop_desc *,
+ unsigned HOST_WIDE_INT *));
static rtx count_loop_iterations PARAMS ((struct loop_desc *, bool));
static void unroll_or_peel_loop PARAMS ((struct loops *, struct loop *, int));
static bool peel_loop_simple PARAMS ((struct loops *, struct loop *, int));
*************** unroll_and_peel_loops (loops, flags)
*** 99,145 ****
}
}
- /* Checks whether LOOP (consisting of BODY -- just not to have to find
- it again and again) have simple exit (i.e. exit is in exactly one block
- that is executed in every iteration exactly once). FALLTRHU_OUT
- is set if the exit edge is fallthru. Exit block is returned. */
- static basic_block
- simple_exit (loops, loop, body, fallthru_out)
- struct loops *loops;
- struct loop *loop;
- basic_block *body;
- int *fallthru_out;
- {
- basic_block exit_bb;
- int i;
- edge e;
-
- /* Loop must have single exit only. */
- exit_bb = NULL;
- for (i = 0; i < loop->num_nodes; i++)
- for (e = body[i]->succ; e; e = e->succ_next)
- if (!flow_bb_inside_loop_p (loop, e->dest))
- {
- if (exit_bb)
- return NULL;
- else
- exit_bb = body[i];
- *fallthru_out = (e->flags & EDGE_FALLTHRU);
- }
- if (!exit_bb)
- return NULL;
-
- /* And it must be tested once during any iteration. */
- if (!just_once_each_iteration_p (loops, loop, exit_bb))
- return NULL;
-
- /* It must end in a simple conditional jump. */
- if (!any_condjump_p (exit_bb->end))
- return NULL;
-
- return exit_bb;
- }
-
/* Checks whether CONDITION is a simple comparison in that one of operands
is register and the other one is invariant in the LOOP. Fills var, lim
and cond fields in DESC. */
--- 102,107 ----
*************** simple_loop_p (loops, loop, desc)
*** 348,387 ****
struct loop *loop;
struct loop_desc *desc;
{
! basic_block exit_bb, *body, mod_bb;
int fallthru_out;
rtx condition;
! edge ei, eo, tmp;
! body = get_loop_body (loop);
! /* There must be only a single exit from loop. */
! if (!(exit_bb = simple_exit (loops, loop, body, &fallthru_out)))
! goto ret_false;
ei = exit_bb->succ;
- eo = exit_bb->succ->succ_next;
if ((ei->flags & EDGE_FALLTHRU) && fallthru_out)
! {
! tmp = ei;
! ei = eo;
! eo = tmp;
! }
! desc->out_edge = eo;
desc->in_edge = ei;
/* Condition must be a simple comparison in that one of operands
is register and the other one is invariant. */
if (!(condition = get_condition (exit_bb->end, NULL)))
! goto ret_false;
if (!simple_condition_p (loop, body, condition, desc))
! goto ret_false;
/* Var must be simply incremented or decremented in exactly one insn that
is executed just once every iteration. */
if (!(mod_bb = simple_increment (loops, loop, body, desc)))
! goto ret_false;
/* OK, it is simple loop. Now just fill in remaining info. */
desc->postincr = !dominated_by_p (loops->cfg.dom, exit_bb, mod_bb);
--- 310,422 ----
struct loop *loop;
struct loop_desc *desc;
{
! int i;
! basic_block *body;
! edge e;
! struct loop_desc act;
! bool any = false;
!
! body = get_loop_body (loop);
!
! for (i = 0; i < loop->num_nodes; i++)
! {
! for (e = body[i]->succ; e; e = e->succ_next)
! if (!flow_bb_inside_loop_p (loop, e->dest)
! && simple_loop_exit_p (loops, loop, e, body, &act))
! {
! /* Prefer constant iterations; the less the better. */
! if (!any)
! any = true;
! else if (!act.const_iter
! || (desc->const_iter && act.niter >= desc->niter))
! continue;
! *desc = act;
! }
! }
!
! free (body);
! return any;
! }
!
! /* Counts constant number of iterations of the loop described by DESC;
! returns false if impossible. */
! static bool
! constant_iterations (desc, niter)
! struct loop_desc *desc;
! unsigned HOST_WIDE_INT *niter;
! {
! rtx test, expr;
!
! test = test_for_iteration (desc, 0);
!
! if (test == const0_rtx)
! {
! *niter = 0;
! return true;
! }
!
! if (test != const_true_rtx)
! return false;
!
! if (!(expr = count_loop_iterations (desc, true)))
! abort ();
!
! if (GET_CODE (expr) != CONST_INT)
! return false;
!
! *niter = INTVAL (expr);
! return true;
! }
!
! /* Tests whether exit at EXIT_EDGE from LOOP is simple. Returns simple loop
! description joined to it in in DESC. */
! static bool
! simple_loop_exit_p (loops, loop, exit_edge, body, desc)
! struct loops *loops;
! struct loop *loop;
! edge exit_edge;
! basic_block *body;
! struct loop_desc *desc;
! {
! basic_block mod_bb, exit_bb;
int fallthru_out;
rtx condition;
! edge ei;
! exit_bb = exit_edge->src;
!
! fallthru_out = (exit_edge->flags & EDGE_FALLTHRU);
!
! if (!exit_bb)
! return false;
!
! /* It must be tested once during any iteration. */
! if (!just_once_each_iteration_p (loops, loop, exit_bb))
! return false;
! /* It must end in a simple conditional jump. */
! if (!any_condjump_p (exit_bb->end))
! return false;
ei = exit_bb->succ;
if ((ei->flags & EDGE_FALLTHRU) && fallthru_out)
! ei = exit_bb->succ->succ_next;
!
! desc->out_edge = exit_edge;
desc->in_edge = ei;
/* Condition must be a simple comparison in that one of operands
is register and the other one is invariant. */
if (!(condition = get_condition (exit_bb->end, NULL)))
! return false;
if (!simple_condition_p (loop, body, condition, desc))
! return false;
/* Var must be simply incremented or decremented in exactly one insn that
is executed just once every iteration. */
if (!(mod_bb = simple_increment (loops, loop, body, desc)))
! return false;
/* OK, it is simple loop. Now just fill in remaining info. */
desc->postincr = !dominated_by_p (loops->cfg.dom, exit_bb, mod_bb);
*************** simple_loop_p (loops, loop, desc)
*** 390,406 ****
/* Find initial value of var. */
desc->init = variable_initial_value (loop, desc->var);
! /* Find numeric values of bounds. */
! if (GET_CODE (desc->lim) == CONST_INT)
! desc->lim_n = INTVAL (desc->lim);
! if (desc->init && GET_CODE (desc->init) == CONST_INT)
! desc->init_n = INTVAL (desc->init);
!
! desc->const_iter = GET_CODE (desc->lim) == CONST_INT
! && desc->init
! && GET_CODE (desc->init) == CONST_INT;
!
! free (body);
if (rtl_dump_file)
{
--- 425,434 ----
/* Find initial value of var. */
desc->init = variable_initial_value (loop, desc->var);
! /* Number of iterations. */
! if (!count_loop_iterations (desc, false))
! return false;
! desc->const_iter = constant_iterations (desc, &desc->niter);
if (rtl_dump_file)
{
*************** simple_loop_p (loops, loop, desc)
*** 438,447 ****
}
}
return true;
-
- ret_false:
- free (body);
- return false;
}
/* Return RTX expression representing number of iterations of loop as bounded
--- 466,471 ----
*************** simple_loop_p (loops, loop, desc)
*** 455,461 ****
These cases needs to be eighter cared by copying the loop test in the front
of loop or keeping the test in first iteration of loop.
! When INITIAL is set, the initial values ov reigsters are used instead
of registers themselves, that may lead to expression to be simplified
and computed at compile time. */
static rtx
--- 479,485 ----
These cases needs to be eighter cared by copying the loop test in the front
of loop or keeping the test in first iteration of loop.
! When INITIAL is set, the initial values of reigsters are used instead
of registers themselves, that may lead to expression to be simplified
and computed at compile time. */
static rtx
*************** peel_loop_completely (loops, loop, desc)
*** 588,606 ****
edge e;
int n_remove_edges, i;
edge *remove_edges;
- rtx exp;
- rtx test;
! test = test_for_iteration (desc, 0);
! if (test && test == const0_rtx)
! npeel = 0;
! else
! {
! exp = count_loop_iterations (desc, true);
! if (!exp || GET_CODE (exp) != CONST_INT)
! abort ();
! npeel = INTVAL (exp);
! }
wont_exit = sbitmap_alloc (npeel + 2);
sbitmap_ones (wont_exit);
--- 612,619 ----
edge e;
int n_remove_edges, i;
edge *remove_edges;
! npeel = desc->niter;
wont_exit = sbitmap_alloc (npeel + 2);
sbitmap_ones (wont_exit);
*************** unroll_loop_constant_iterations (loops,
*** 649,661 ****
sbitmap wont_exit;
int n_remove_edges, i;
edge *remove_edges;
- rtx exp;
! /* Normalization. */
! exp = count_loop_iterations (desc, true);
! if (!exp || GET_CODE (exp) != CONST_INT)
! abort ();
! niter = INTVAL (exp);
if (niter <= (unsigned) max_unroll)
abort (); /* Should get into peeling instead. */
--- 662,669 ----
sbitmap wont_exit;
int n_remove_edges, i;
edge *remove_edges;
! niter = desc->niter;
if (niter <= (unsigned) max_unroll)
abort (); /* Should get into peeling instead. */
*************** unroll_loop_constant_iterations (loops,
*** 673,679 ****
in the first copy. */
if (rtl_dump_file)
! fprintf (rtl_dump_file, ";; Condition on beginning of loop.\n");
/* Peel exit_mod iterations. */
RESET_BIT (wont_exit, 0);
--- 681,687 ----
in the first copy. */
if (rtl_dump_file)
! fprintf (rtl_dump_file, ";; Condition on beginning of loop.\n");
/* Peel exit_mod iterations. */
RESET_BIT (wont_exit, 0);
*************** unroll_loop_constant_iterations (loops,
*** 690,696 ****
/* Leave exit test in last copy. */
if (rtl_dump_file)
! fprintf (rtl_dump_file, ";; Condition on end of loop.\n");
/* We know that niter >= max_unroll + 1; so we do not need to care of
case when we would exit before reaching the loop. So just peel
--- 698,704 ----
/* Leave exit test in last copy. */
if (rtl_dump_file)
! fprintf (rtl_dump_file, ";; Condition on end of loop.\n");
/* We know that niter >= max_unroll + 1; so we do not need to care of
case when we would exit before reaching the loop. So just peel
*************** unroll_loop_runtime_iterations (loops, l
*** 785,793 ****
n_peel = max_unroll + 1;
skip_first_test = true;
/* First check for zero is obviously unnecessary now; it might seem
! we could do better by increasing it before AND; but we must have
! guaranteed that exit condition will be checked in first iteration,
! so that we won't miscompile loop with negative number of iterations. */
}
niter = expand_simple_binop (GET_MODE (desc->var), PLUS,
--- 793,801 ----
n_peel = max_unroll + 1;
skip_first_test = true;
/* First check for zero is obviously unnecessary now; it might seem
! we could do better by increasing it before AND; but we must have
! guaranteed that exit condition will be checked in first iteration,
! so that we won't miscompile loop with negative number of iterations. */
}
niter = expand_simple_binop (GET_MODE (desc->var), PLUS,
*************** unroll_loop_runtime_iterations (loops, l
*** 833,840 ****
make_edge (preheader, fake, 0);
/* We must be a bit careful here, as we might have negative
! number of iterations. Also, in case of postincrement we do
! not know whether we should not exit before reaching the loop. */
sbitmap_zero (wont_exit);
if (desc->postincr && (i || desc->cond == NE))
SET_BIT (wont_exit, 1);
--- 841,848 ----
make_edge (preheader, fake, 0);
/* We must be a bit careful here, as we might have negative
! number of iterations. Also, in case of postincrement we do
! not know whether we should not exit before reaching the loop. */
sbitmap_zero (wont_exit);
if (desc->postincr && (i || desc->cond == NE))
SET_BIT (wont_exit, 1);
*************** unroll_or_peel_loop (loops, loop, flags)
*** 1043,1068 ****
exact = false;
if (simple)
{
- rtx exp = count_loop_iterations (&desc, true);
- rtx test = test_for_iteration (&desc, 0);
-
/* Loop iterating 0 times. These should really be elliminated earlier,
but we may create them by other transformations. */
! if (test && test == const0_rtx)
{
flags |= UAP_PEEL;
exact = true;
niter = 0;
}
! else if (!exp)
! simple = false;
! /* Loop with constant number of iterations? */
! else if (GET_CODE (exp) == CONST_INT
! && test && test == const_true_rtx)
! exact = true, niter = INTVAL (exp);
! else
! exact = false;
}
if (!exact)
--- 1051,1070 ----
exact = false;
if (simple)
{
/* Loop iterating 0 times. These should really be elliminated earlier,
but we may create them by other transformations. */
! if (desc.const_iter && desc.niter == 0)
{
flags |= UAP_PEEL;
exact = true;
niter = 0;
}
! else
! {
! exact = desc.const_iter;
! niter = desc.niter;
! }
}
if (!exact)