This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[CFG] handle loop with multiple exits
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-pdo at atrey dot karlin dot mff dot cuni dot cz, gcc-patches at gcc dot gnu dot org
- Date: Sat, 4 May 2002 22:10:18 +0200
- Subject: [CFG] handle loop with multiple exits
Hello.
This patch makes it possible to recognize loops with more exits as simple.
It also moves counting the (constant) number of iterations to one place.
Bootstrapped on i686.
Zdenek
Changelog:
* loop.h (struct loop_desc): lim_n and init_n removed, niter added.
* unroll-new.c (simple_exit): Removed.
(simple_loop_exit_p, constant_iterations): New.
(simple_loop_p): Modified to handle loops with more than one exit.
(peel_loop_completely, unroll_loop_constant_iterations,
unroll_or_peel_loop): Use desc->niter instead of computing it again.
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:00:56 -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:00:59 -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,418 ----
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 && 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;
! }
!
! /* 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)
{
--- 421,430 ----
/* 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
--- 462,467 ----
*************** 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
--- 475,481 ----
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);
--- 608,615 ----
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. */
--- 658,665 ----
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);
--- 677,683 ----
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
--- 694,700 ----
/* 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,
--- 789,797 ----
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);
--- 837,844 ----
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)
--- 1047,1066 ----
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)