unroll-new.c breakup
Jan Hubicka
jh@suse.cz
Tue Jun 4 07:41:00 GMT 2002
Hi,
this patch moves the loop analysis code out of unroll loop to the cfgloopanal
so other passes may use it as well and it is easier to merge into the mainline
tree. I've also implemented simple code in predict.c to estimate number of
iterations when it is constant replacing the existing loop.c code in stronger
way.
Honza
Tue Jun 4 16:36:04 CEST 2002 Jan Hubicka <jh@suse.cz>
* cfgloopanal.c: Include loop.h and expr.h
(cfg_for_each_insn_in_loop): rename from for_each_insn_in_loop.
(invariant_in_blocks_p, test_for_iteration, constant_iterations,
simple_loop_exit_p, variable_initial_value, variable_initial_values,
simple_condition_p, simple_increment): Move from ....
* unroll-new.c: ... here.
* loop.h (simple_loop_p, count_loop_iterations): Declare.
* predict.c: Include loop.h.
(estimate_probability): Implement cfg_loop_iterations predictor.
* predict.def (PRED_CFG_LOOP_ITERATIONS): Declare.
Index: cfgloopanal.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/Attic/cfgloopanal.c,v
retrieving revision 1.1.2.10
diff -c -3 -p -r1.1.2.10 cfgloopanal.c
*** cfgloopanal.c 23 May 2002 14:59:01 -0000 1.1.2.10
--- cfgloopanal.c 4 Jun 2002 14:33:55 -0000
***************
*** 7,15 ****
#include "output.h"
#include "function.h"
#include "cfglayout.h"
typedef int (*loop_function) PARAMS ((rtx insn, void *data));
! static int for_each_insn_in_loop PARAMS ((struct loop *, loop_function, void *));
static int mark_def_varies PARAMS ((rtx insn, void *data));
static int collect_stores PARAMS ((rtx insn, void *data));
static void note_mem_store PARAMS ((rtx, rtx, void *));
--- 7,17 ----
#include "output.h"
#include "function.h"
#include "cfglayout.h"
+ #include "loop.h"
+ #include "expr.h"
typedef int (*loop_function) PARAMS ((rtx insn, void *data));
! static int cfg_for_each_insn_in_loop PARAMS ((struct loop *, loop_function, void *));
static int mark_def_varies PARAMS ((rtx insn, void *data));
static int collect_stores PARAMS ((rtx insn, void *data));
static void note_mem_store PARAMS ((rtx, rtx, void *));
*************** static int discover_invariant PARAMS ((
*** 17,25 ****
static int not_invariant_rtx PARAMS ((rtx *rtxp, void *data));
static bool mark_maybe_invariant_set PARAMS ((rtx, rtx, rtx, struct loop_invariants *));
static bool cbp_enum_p PARAMS ((basic_block, void *));
static int
! for_each_insn_in_loop (loop, fun, data)
struct loop *loop;
loop_function fun;
void *data;
--- 19,43 ----
static int not_invariant_rtx PARAMS ((rtx *rtxp, void *data));
static bool mark_maybe_invariant_set PARAMS ((rtx, rtx, rtx, struct loop_invariants *));
static bool cbp_enum_p PARAMS ((basic_block, void *));
+ static bool invariant_in_blocks_p PARAMS ((rtx, basic_block *, int));
+ static rtx test_for_iteration PARAMS ((struct loop_desc *desc,
+ unsigned HOST_WIDE_INT));
+ static bool constant_iterations PARAMS ((struct loop_desc *,
+ unsigned HOST_WIDE_INT *,
+ bool *));
+ static bool simple_loop_exit_p PARAMS ((struct loops *, struct loop *,
+ edge, basic_block *,
+ struct loop_desc *));
+ static rtx variable_initial_value PARAMS ((rtx, basic_block, rtx, rtx *));
+ static rtx variable_initial_values PARAMS ((edge, rtx));
+ static bool simple_condition_p PARAMS ((struct loop *, basic_block *,
+ rtx, struct loop_desc *));
+ static basic_block simple_increment PARAMS ((struct loops *, struct loop *,
+ basic_block *,
+ struct loop_desc *));
static int
! cfg_for_each_insn_in_loop (loop, fun, data)
struct loop *loop;
loop_function fun;
void *data;
*************** init_loop_invariants (loop, df)
*** 325,336 ****
/* Mark everything inside loop as not invariant first. */
! for_each_insn_in_loop (loop, mark_def_varies, inv);
s.unknown_address_altered = false;
s.unknown_constant_address_altered = false;
s.inv = inv;
! for_each_insn_in_loop (loop, collect_stores, &s);
if (s.unknown_address_altered)
{
--- 343,354 ----
/* Mark everything inside loop as not invariant first. */
! cfg_for_each_insn_in_loop (loop, mark_def_varies, inv);
s.unknown_address_altered = false;
s.unknown_constant_address_altered = false;
s.inv = inv;
! cfg_for_each_insn_in_loop (loop, collect_stores, &s);
if (s.unknown_address_altered)
{
*************** init_loop_invariants (loop, df)
*** 348,354 ****
/* Attempt to prove invariantness of each insn.
Iterate until process stabilize. */
! while (for_each_insn_in_loop (loop, discover_invariant, inv))
i++;
if (rtl_dump_file)
--- 366,372 ----
/* Attempt to prove invariantness of each insn.
Iterate until process stabilize. */
! while (cfg_for_each_insn_in_loop (loop, discover_invariant, inv))
i++;
if (rtl_dump_file)
*************** force_single_succ_latches (loops)
*** 657,661 ****
--- 675,1256 ----
for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next);
loop_split_edge_with (e, NULL_RTX, loops);
}
+ }
+
+ /* Checks whether EXPR is invariant in basic blocks BBS. */
+ static bool
+ invariant_in_blocks_p (expr, bbs, nbbs)
+ rtx expr;
+ basic_block *bbs;
+ int nbbs;
+ {
+ int i;
+
+ for (i = 0; i < nbbs; i++)
+ if (modified_between_p (expr, bbs[i]->head, NEXT_INSN (bbs[i]->end)))
+ return false;
+
+ return true;
+ }
+
+ /* 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. */
+ static bool
+ simple_condition_p (loop, body, condition, desc)
+ struct loop *loop;
+ basic_block *body;
+ rtx condition;
+ struct loop_desc *desc;
+ {
+ rtx op0, op1;
+ edge e = loop_preheader_edge (loop);
+
+ /* Check condition. */
+ switch (GET_CODE (condition))
+ {
+ case EQ:
+ case NE:
+ case LE:
+ case LT:
+ case GE:
+ case GT:
+ case GEU:
+ case GTU:
+ case LEU:
+ case LTU:
+ break;
+ default:
+ return false;
+ }
+
+ /* Of integers or pointers. */
+ if (GET_MODE_CLASS (GET_MODE (XEXP (condition, 0))) != MODE_INT
+ && GET_MODE_CLASS (GET_MODE (XEXP (condition, 0))) != MODE_PARTIAL_INT)
+ return false;
+
+ /* One of operands must be a simple register. */
+ op0 = XEXP (condition, 0);
+ op1 = XEXP (condition, 1);
+
+ /* One of operands must be invariant. */
+ if (invariant_in_blocks_p (op0, body, loop->num_nodes))
+ {
+ /* And the other one must be a register. */
+ if (!REG_P (op1))
+ return false;
+ desc->var = op1;
+ desc->lim = op0;
+
+ desc->lim_alts = variable_initial_values (e, op0);
+
+ desc->cond = swap_condition (GET_CODE (condition));
+ if (desc->cond == UNKNOWN)
+ return false;
+ return true;
+ }
+
+ /* Check the other operand. */
+ if (!invariant_in_blocks_p (op1, body, loop->num_nodes))
+ return false;
+ if (!REG_P (op0))
+ return false;
+
+ desc->var = op0;
+ desc->lim = op1;
+
+ desc->lim_alts = variable_initial_values (e, op1);
+
+ desc->cond = GET_CODE (condition);
+
+ return true;
+ }
+
+ /* Checks whether DESC->var is incremented/decremented exactly once each
+ iteration. Fills in DESC->stride and returns block in that DESC->var is
+ modified. */
+ static basic_block
+ simple_increment (loops, loop, body, desc)
+ struct loops *loops;
+ struct loop *loop;
+ basic_block *body;
+ struct loop_desc *desc;
+ {
+ rtx mod_insn, insn, set, set_src, set_add;
+ basic_block mod_bb = NULL;
+ int i;
+
+ /* Find insn that modifies var. */
+ mod_insn = NULL;
+ for (i = 0; i < loop->num_nodes; i++)
+ if (modified_between_p (desc->var, body[i]->head, NEXT_INSN (body[i]->end)))
+ {
+ for (insn = NEXT_INSN (body[i]->head);
+ insn != NEXT_INSN (body[i]->end);
+ insn = NEXT_INSN (insn))
+ if (modified_between_p (desc->var, PREV_INSN (insn), NEXT_INSN (insn)))
+ {
+ if (mod_insn)
+ return NULL;
+ else
+ mod_insn = insn;
+ }
+ mod_bb = body[i];
+ }
+ if (!mod_insn)
+ return NULL;
+
+ /* Check that it is executed exactly once each iteration. */
+ if (!just_once_each_iteration_p (loops, loop, mod_bb))
+ return NULL;
+
+ /* mod_insn must be a simple increment/decrement. */
+ set = single_set (mod_insn);
+ if (!set)
+ return NULL;
+ if (!rtx_equal_p (SET_DEST (set), desc->var))
+ return NULL;
+
+ set_src = SET_SRC (set);
+ if (GET_CODE (set_src) != PLUS)
+ return NULL;
+ if (!rtx_equal_p (XEXP (set_src, 0), desc->var))
+ return NULL;
+
+ /* Set desc->stride. */
+ set_add = XEXP (set_src, 1);
+ if (CONSTANT_P (set_add))
+ desc->stride = set_add;
+ else
+ return NULL;
+
+ return mod_bb;
+ }
+
+ /* Tries to find initial value of VAR in INSN. This value must be valid in
+ END_BB too. If SET_INSN is not NULL, insn in that var is set is placed
+ here. */
+ static rtx
+ variable_initial_value (insn, end_bb, var, set_insn)
+ rtx insn;
+ basic_block end_bb;
+ rtx var;
+ rtx *set_insn;
+ {
+ basic_block bb;
+ rtx set;
+
+ /* Go back through cfg. */
+ bb = BLOCK_FOR_INSN (insn);
+ while (1)
+ {
+ for (; insn != bb->head; insn = PREV_INSN (insn))
+ if (modified_between_p (var, PREV_INSN (insn), NEXT_INSN (insn)))
+ break;
+
+ if (insn != bb->head)
+ {
+ /* We found place where var is set. */
+ rtx set_dest;
+ basic_block b;
+ rtx val;
+ rtx note;
+
+ set = single_set (insn);
+ if (!set)
+ return NULL;
+ set_dest = SET_DEST (set);
+ if (!rtx_equal_p (set_dest, var))
+ return NULL;
+
+ note = find_reg_equal_equiv_note (insn);
+ if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
+ val = XEXP (note, 0);
+ else
+ val = SET_SRC (set);
+ if (modified_between_p (val, insn, NEXT_INSN (bb->end)))
+ return NULL;
+ for (b = end_bb; b != bb; b = b->pred->src)
+ if (modified_between_p (val, b->head, NEXT_INSN (b->end)))
+ return NULL;
+
+ if (set_insn)
+ *set_insn = insn;
+ return val;
+ }
+
+ if (bb->pred->pred_next || bb->pred->src == ENTRY_BLOCK_PTR)
+ return NULL;
+
+ bb = bb->pred->src;
+ insn = bb->end;
+ }
+
+ return NULL;
+ }
+
+ /* Returns list of definitions of initial value of VAR at Edge. */
+ static rtx
+ variable_initial_values (e, var)
+ edge e;
+ rtx var;
+ {
+ rtx set_insn, list;
+
+ list = alloc_EXPR_LIST (0, copy_rtx (var), NULL);
+
+ if (e->src == ENTRY_BLOCK_PTR)
+ return list;
+
+ set_insn = e->src->end;
+ while (REG_P (var)
+ && (var = variable_initial_value (set_insn, e->src, var, &set_insn)))
+ list = alloc_EXPR_LIST (0, copy_rtx (var), list);
+
+ return list;
+ }
+
+ /* Tests whether LOOP is simple for loop. Returns simple loop description
+ in DESC. */
+ bool
+ simple_loop_p (loops, loop, desc)
+ struct loops *loops;
+ 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, may_be_zero)
+ struct loop_desc *desc;
+ unsigned HOST_WIDE_INT *niter;
+ bool *may_be_zero;
+ {
+ rtx test, expr;
+ rtx ainit, alim;
+
+ test = test_for_iteration (desc, 0);
+ if (test == const0_rtx)
+ {
+ *niter = 0;
+ *may_be_zero = false;
+ return true;
+ }
+
+ *may_be_zero = (test != const_true_rtx);
+
+ for (ainit = desc->var_alts; ainit; ainit = XEXP (ainit, 1))
+ for (alim = desc->lim_alts; alim; alim = XEXP (alim, 1))
+ {
+ if (!(expr = count_loop_iterations (desc, XEXP (ainit, 0), XEXP (alim, 0))))
+ abort ();
+ if (GET_CODE (expr) == CONST_INT)
+ {
+ *niter = INTVAL (expr);
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+ /* 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, e;
+
+ 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);
+ desc->neg = !fallthru_out;
+
+ /* Find initial value of var. */
+ e = loop_preheader_edge (loop);
+ desc->var_alts = variable_initial_values (e, desc->var);
+
+ /* Number of iterations. */
+ if (!count_loop_iterations (desc, NULL, NULL))
+ return false;
+ desc->const_iter = constant_iterations (desc, &desc->niter, &desc->may_be_zero);
+
+ if (rtl_dump_file)
+ {
+ fprintf (rtl_dump_file, "; Simple loop %i\n", loop->num);
+ if (desc->postincr)
+ fprintf (rtl_dump_file,
+ "; does postincrement after loop exit condition\n");
+
+ fprintf (rtl_dump_file, "; Induction variable:");
+ print_simple_rtl (rtl_dump_file, desc->var);
+ fputc ('\n', rtl_dump_file);
+
+ fprintf (rtl_dump_file, "; Initial values:");
+ print_simple_rtl (rtl_dump_file, desc->var_alts);
+ fputc ('\n', rtl_dump_file);
+
+ fprintf (rtl_dump_file, "; Stride:");
+ print_simple_rtl (rtl_dump_file, desc->stride);
+ fputc ('\n', rtl_dump_file);
+
+ fprintf (rtl_dump_file, "; Compared with:");
+ print_simple_rtl (rtl_dump_file, desc->lim);
+ fputc ('\n', rtl_dump_file);
+
+ fprintf (rtl_dump_file, "; Alternative values:");
+ print_simple_rtl (rtl_dump_file, desc->lim_alts);
+ fputc ('\n', rtl_dump_file);
+
+ fprintf (rtl_dump_file, "; Exit condition:");
+ if (desc->neg)
+ fprintf (rtl_dump_file, "(negated)");
+ fprintf (rtl_dump_file, "%s\n", GET_RTX_NAME (desc->cond));
+ fputc ('\n', rtl_dump_file);
+ }
+ return true;
+ }
+
+ /* Return RTX expression representing number of iterations of loop as bounded
+ by test described by DESC (in the case loop really has multiple exit
+ edges, fewer iterations may happen in the practice).
+
+ Return NULL if it is unknown. Additionally the value may be invalid for
+ paradoxical loop (lets define paradoxical loops as loops whose test is
+ failing at -1th iteration, for instance "for (i=5;i<1;i++);").
+
+ 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 INIT/LIM are set, they are used instead of var/lim of DESC. */
+ rtx
+ count_loop_iterations (desc, init, lim)
+ struct loop_desc *desc;
+ rtx init;
+ rtx lim;
+ {
+ enum rtx_code cond = desc->cond;
+ rtx stride = desc->stride;
+ rtx mod, exp;
+
+ init = init ? copy_rtx (init) : copy_rtx (desc->var);
+ lim = lim ? copy_rtx (lim) : copy_rtx (desc->lim);
+
+ /* Give up on floating point modes and friends. It can be possible to do
+ the job for constant loop bounds, but it is probably not worthwhile. */
+ if (!INTEGRAL_MODE_P (GET_MODE (desc->var)))
+ return NULL;
+
+ /* Ensure that we always handle the condition to stay inside loop. */
+ if (desc->neg)
+ cond = reverse_condition (cond);
+
+ /* Compute absolute value of the difference of initial and final value. */
+ if (INTVAL (stride) > 0)
+ {
+ /* Bypass nonsential tests. */
+ if (cond == EQ || cond == GE || cond == GT || cond == GEU
+ || cond == GTU)
+ return NULL;
+ exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
+ lim, init);
+ }
+ else
+ {
+ /* Bypass nonsential tests. */
+ if (cond == EQ || cond == LE || cond == LT || cond == LEU
+ || cond == LTU)
+ return NULL;
+ exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
+ init, lim);
+ stride = simplify_gen_unary (NEG, GET_MODE (desc->var),
+ stride, GET_MODE (desc->var));
+ }
+
+ /* Normalize difference so the value is always first examined
+ and later incremented. */
+
+ if (!desc->postincr)
+ exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
+ exp, stride);
+
+ /* Determine delta caused by exit condition. */
+ switch (cond)
+ {
+ case NE:
+ /* For NE tests, make sure that the iteration variable won't miss
+ the final value. If EXP mod STRIDE is not zero, then the
+ iteration variable will overflow before the loop exits, and we
+ can not calculate the number of iterations easilly. */
+ if (stride != const1_rtx
+ && (simplify_gen_binary (UMOD, GET_MODE (desc->var), exp, stride)
+ != const0_rtx))
+ return NULL;
+ break;
+ case LT:
+ case GT:
+ case LTU:
+ case GTU:
+ break;
+ case LE:
+ case GE:
+ case LEU:
+ case GEU:
+ exp = simplify_gen_binary (PLUS, GET_MODE (desc->var),
+ exp, const1_rtx);
+ break;
+ default:
+ abort ();
+ }
+
+ if (stride != const1_rtx)
+ {
+ /* Number of iterations is now (EXP + STRIDE - 1 / STRIDE),
+ but we need to take care for overflows. */
+
+ mod = simplify_gen_binary (UMOD, GET_MODE (desc->var), exp, stride);
+
+ /* This is dirty trick. When we can't compute number of iterations
+ to be constant, we simply ignore the possible overflow, as
+ runtime unroller always use power of 2 amounts and does not
+ care about possible lost bits. */
+
+ if (GET_CODE (mod) != CONST_INT)
+ {
+ rtx stridem1 = simplify_gen_binary (PLUS, GET_MODE (desc->var),
+ stride, constm1_rtx);
+ exp = simplify_gen_binary (PLUS, GET_MODE (desc->var),
+ exp, stridem1);
+ exp = simplify_gen_binary (UDIV, GET_MODE (desc->var), exp, stride);
+ }
+ else
+ {
+ exp = simplify_gen_binary (UDIV, GET_MODE (desc->var), exp, stride);
+ if (mod != const0_rtx)
+ exp = simplify_gen_binary (PLUS, GET_MODE (desc->var),
+ exp, const1_rtx);
+ }
+ }
+
+ if (rtl_dump_file)
+ {
+ fprintf (rtl_dump_file, "; Number of iterations: ");
+ print_simple_rtl (rtl_dump_file, exp);
+ fprintf (rtl_dump_file, "\n");
+ }
+
+ return exp;
+ }
+
+ /* Return simplified RTX expression representing the value of test
+ described of DESC at given iteration of loop. */
+
+ static rtx
+ test_for_iteration (desc, iter)
+ struct loop_desc *desc;
+ unsigned HOST_WIDE_INT iter;
+ {
+ enum rtx_code cond = desc->cond;
+ rtx exp = XEXP (desc->var_alts, 0);
+ rtx addval;
+
+ /* Give up on floating point modes and friends. It can be possible to do
+ the job for constant loop bounds, but it is probably not worthwhile. */
+ if (!INTEGRAL_MODE_P (GET_MODE (desc->var)))
+ return NULL;
+
+ /* Ensure that we always handle the condition to stay inside loop. */
+ if (desc->neg)
+ cond = reverse_condition (cond);
+
+ /* Compute the value of induction variable. */
+ addval = simplify_gen_binary (MULT, GET_MODE (desc->var),
+ desc->stride,
+ gen_int_mode (desc->postincr
+ ? iter : iter + 1,
+ GET_MODE (desc->var)));
+ exp = simplify_gen_binary (PLUS, GET_MODE (desc->var), exp, addval);
+ /* Test at given condtion. */
+ exp = simplify_gen_relational (cond, SImode,
+ GET_MODE (desc->var), exp, desc->lim);
+
+ if (rtl_dump_file)
+ {
+ fprintf (rtl_dump_file,
+ "; Conditional to continue loop at %i th iteration: ", iter);
+ print_simple_rtl (rtl_dump_file, exp);
+ fprintf (rtl_dump_file, "\n");
+ }
+ return exp;
}
Index: loop.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/loop.h,v
retrieving revision 1.56.2.18
diff -c -3 -p -r1.56.2.18 loop.h
*** loop.h 1 Jun 2002 18:07:22 -0000 1.56.2.18
--- loop.h 4 Jun 2002 14:33:56 -0000
*************** struct loop_desc
*** 455,460 ****
--- 455,463 ----
};
bool can_duplicate_loop_p PARAMS ((struct loop *loop));
+ bool simple_loop_p PARAMS ((struct loops *, struct loop *,
+ struct loop_desc *));
+ rtx count_loop_iterations PARAMS ((struct loop_desc *, rtx, rtx));
#define DLTHE_FLAG_UPDATE_FREQ 1
#define DLTHE_FLAG_ALL (DLTHE_FLAG_UPDATE_FREQ)
Index: predict.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/predict.c,v
retrieving revision 1.44.2.33
diff -c -3 -p -r1.44.2.33 predict.c
*** predict.c 1 Jun 2002 18:07:25 -0000 1.44.2.33
--- predict.c 4 Jun 2002 14:33:56 -0000
*************** Software Foundation, 59 Temple Place - S
*** 49,54 ****
--- 49,55 ----
#include "real.h"
#include "params.h"
#include "target.h"
+ #include "loop.h"
/* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE, 0.5,
REAL_BB_FREQ_MAX. */
*************** estimate_probability (loops_info)
*** 434,441 ****
--- 435,452 ----
{
int header_found = 0;
edge e;
+ struct loop_desc desc;
bb = bbs[j];
+
+ if (simple_loop_p (loops_info, loop, &desc)
+ && desc.const_iter)
+ {
+ predict_edge (desc.in_edge, PRED_CFG_LOOP_ITERATIONS,
+ REG_BR_PROB_BASE
+ - (REG_BR_PROB_BASE + (desc.niter + 1) /2)
+ / (desc.niter + 1));
+ }
/* Bypass loop heuristics on continue statement. These
statements construct loops via "non-loop" constructs
Index: predict.def
===================================================================
RCS file: /cvs/gcc/egcs/gcc/predict.def,v
retrieving revision 1.12.2.9
diff -c -3 -p -r1.12.2.9 predict.def
*** predict.def 8 May 2002 12:03:38 -0000 1.12.2.9
--- predict.def 4 Jun 2002 14:33:56 -0000
*************** DEF_PREDICTOR (PRED_UNCONDITIONAL, "unco
*** 56,61 ****
--- 56,63 ----
/* Use number of loop iterations determined by loop unroller to set
probability. We don't want to use Dempster-Shaffer theory here,
as the predictions is exact. */
+ DEF_PREDICTOR (PRED_CFG_LOOP_ITERATIONS, "cfgloop iterations", 0,
+ PRED_FLAG_FIRST_MATCH)
DEF_PREDICTOR (PRED_LOOP_ITERATIONS, "loop iterations", 0,
PRED_FLAG_FIRST_MATCH)
Index: unroll-new.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/Attic/unroll-new.c,v
retrieving revision 1.1.2.29
diff -c -3 -p -r1.1.2.29 unroll-new.c
*** unroll-new.c 29 May 2002 10:40:49 -0000 1.1.2.29
--- unroll-new.c 4 Jun 2002 14:33:56 -0000
*************** Software Foundation, 59 Temple Place - S
*** 42,63 ****
#include "params.h"
#include "output.h"
- static bool simple_condition_p PARAMS ((struct loop *, basic_block *,
- rtx, struct loop_desc *));
- static basic_block simple_increment PARAMS ((struct loops *, struct loop *,
- basic_block *,
- struct loop_desc *));
- static rtx variable_initial_value PARAMS ((rtx, basic_block, rtx, rtx *));
- static rtx variable_initial_values PARAMS ((edge, 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 *,
- bool *));
- static rtx count_loop_iterations PARAMS ((struct loop_desc *, rtx, rtx));
static void unroll_or_peel_loop PARAMS ((struct loops *, struct loop *, int));
static bool peel_loop_simple PARAMS ((struct loops *, struct loop *, int));
static bool peel_loop_completely PARAMS ((struct loops *, struct loop *,
--- 42,47 ----
*************** static bool unroll_loop_constant_iterati
*** 69,77 ****
static bool unroll_loop_runtime_iterations PARAMS ((struct loops *,
struct loop *, int,
struct loop_desc *));
- static rtx test_for_iteration PARAMS ((struct loop_desc *desc,
- unsigned HOST_WIDE_INT));
- static bool invariant_in_blocks_p PARAMS ((rtx, basic_block *, int));
/* Unroll and peel (depending on FLAGS) LOOPS. */
void
--- 53,58 ----
*************** unroll_and_peel_loops (loops, flags)
*** 104,687 ****
loop = next;
}
}
-
- /* Checks whether EXPR is invariant in basic blocks BBS. */
- static bool
- invariant_in_blocks_p (expr, bbs, nbbs)
- rtx expr;
- basic_block *bbs;
- int nbbs;
- {
- int i;
-
- for (i = 0; i < nbbs; i++)
- if (modified_between_p (expr, bbs[i]->head, NEXT_INSN (bbs[i]->end)))
- return false;
-
- return true;
- }
-
- /* 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. */
- static bool
- simple_condition_p (loop, body, condition, desc)
- struct loop *loop;
- basic_block *body;
- rtx condition;
- struct loop_desc *desc;
- {
- rtx op0, op1;
- edge e = loop_preheader_edge (loop);
-
- /* Check condition. */
- switch (GET_CODE (condition))
- {
- case EQ:
- case NE:
- case LE:
- case LT:
- case GE:
- case GT:
- case GEU:
- case GTU:
- case LEU:
- case LTU:
- break;
- default:
- return false;
- }
-
- /* Of integers or pointers. */
- if (GET_MODE_CLASS (GET_MODE (XEXP (condition, 0))) != MODE_INT
- && GET_MODE_CLASS (GET_MODE (XEXP (condition, 0))) != MODE_PARTIAL_INT)
- return false;
-
- /* One of operands must be a simple register. */
- op0 = XEXP (condition, 0);
- op1 = XEXP (condition, 1);
-
- /* One of operands must be invariant. */
- if (invariant_in_blocks_p (op0, body, loop->num_nodes))
- {
- /* And the other one must be a register. */
- if (!REG_P (op1))
- return false;
- desc->var = op1;
- desc->lim = op0;
-
- desc->lim_alts = variable_initial_values (e, op0);
-
- desc->cond = swap_condition (GET_CODE (condition));
- if (desc->cond == UNKNOWN)
- return false;
- return true;
- }
-
- /* Check the other operand. */
- if (!invariant_in_blocks_p (op1, body, loop->num_nodes))
- return false;
- if (!REG_P (op0))
- return false;
-
- desc->var = op0;
- desc->lim = op1;
-
- desc->lim_alts = variable_initial_values (e, op1);
-
- desc->cond = GET_CODE (condition);
-
- return true;
- }
-
- /* Checks whether DESC->var is incremented/decremented exactly once each
- iteration. Fills in DESC->stride and returns block in that DESC->var is
- modified. */
- static basic_block
- simple_increment (loops, loop, body, desc)
- struct loops *loops;
- struct loop *loop;
- basic_block *body;
- struct loop_desc *desc;
- {
- rtx mod_insn, insn, set, set_src, set_add;
- basic_block mod_bb = NULL;
- int i;
-
- /* Find insn that modifies var. */
- mod_insn = NULL;
- for (i = 0; i < loop->num_nodes; i++)
- if (modified_between_p (desc->var, body[i]->head, NEXT_INSN (body[i]->end)))
- {
- for (insn = NEXT_INSN (body[i]->head);
- insn != NEXT_INSN (body[i]->end);
- insn = NEXT_INSN (insn))
- if (modified_between_p (desc->var, PREV_INSN (insn), NEXT_INSN (insn)))
- {
- if (mod_insn)
- return NULL;
- else
- mod_insn = insn;
- }
- mod_bb = body[i];
- }
- if (!mod_insn)
- return NULL;
-
- /* Check that it is executed exactly once each iteration. */
- if (!just_once_each_iteration_p (loops, loop, mod_bb))
- return NULL;
-
- /* mod_insn must be a simple increment/decrement. */
- set = single_set (mod_insn);
- if (!set)
- return NULL;
- if (!rtx_equal_p (SET_DEST (set), desc->var))
- return NULL;
-
- set_src = SET_SRC (set);
- if (GET_CODE (set_src) != PLUS)
- return NULL;
- if (!rtx_equal_p (XEXP (set_src, 0), desc->var))
- return NULL;
-
- /* Set desc->stride. */
- set_add = XEXP (set_src, 1);
- if (CONSTANT_P (set_add))
- desc->stride = set_add;
- else
- return NULL;
-
- return mod_bb;
- }
-
- /* Tries to find initial value of VAR in INSN. This value must be valid in
- END_BB too. If SET_INSN is not NULL, insn in that var is set is placed
- here. */
- static rtx
- variable_initial_value (insn, end_bb, var, set_insn)
- rtx insn;
- basic_block end_bb;
- rtx var;
- rtx *set_insn;
- {
- basic_block bb;
- rtx set;
-
- /* Go back through cfg. */
- bb = BLOCK_FOR_INSN (insn);
- while (1)
- {
- for (; insn != bb->head; insn = PREV_INSN (insn))
- if (modified_between_p (var, PREV_INSN (insn), NEXT_INSN (insn)))
- break;
-
- if (insn != bb->head)
- {
- /* We found place where var is set. */
- rtx set_dest;
- basic_block b;
- rtx val;
- rtx note;
-
- set = single_set (insn);
- if (!set)
- return NULL;
- set_dest = SET_DEST (set);
- if (!rtx_equal_p (set_dest, var))
- return NULL;
-
- note = find_reg_equal_equiv_note (insn);
- if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
- val = XEXP (note, 0);
- else
- val = SET_SRC (set);
- if (modified_between_p (val, insn, NEXT_INSN (bb->end)))
- return NULL;
- for (b = end_bb; b != bb; b = b->pred->src)
- if (modified_between_p (val, b->head, NEXT_INSN (b->end)))
- return NULL;
-
- if (set_insn)
- *set_insn = insn;
- return val;
- }
-
- if (bb->pred->pred_next || bb->pred->src == ENTRY_BLOCK_PTR)
- return NULL;
-
- bb = bb->pred->src;
- insn = bb->end;
- }
-
- return NULL;
- }
-
- /* Returns list of definitions of initial value of VAR at Edge. */
- static rtx
- variable_initial_values (e, var)
- edge e;
- rtx var;
- {
- rtx set_insn, list;
-
- list = alloc_EXPR_LIST (0, copy_rtx (var), NULL);
-
- if (e->src == ENTRY_BLOCK_PTR)
- return list;
-
- set_insn = e->src->end;
- while (REG_P (var)
- && (var = variable_initial_value (set_insn, e->src, var, &set_insn)))
- list = alloc_EXPR_LIST (0, copy_rtx (var), list);
-
- return list;
- }
-
- /* Tests whether LOOP is simple for loop. Returns simple loop description
- in DESC. */
- static bool
- simple_loop_p (loops, loop, desc)
- struct loops *loops;
- 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, may_be_zero)
- struct loop_desc *desc;
- unsigned HOST_WIDE_INT *niter;
- bool *may_be_zero;
- {
- rtx test, expr;
- rtx ainit, alim;
-
- test = test_for_iteration (desc, 0);
- if (test == const0_rtx)
- {
- *niter = 0;
- *may_be_zero = false;
- return true;
- }
-
- *may_be_zero = (test != const_true_rtx);
-
- for (ainit = desc->var_alts; ainit; ainit = XEXP (ainit, 1))
- for (alim = desc->lim_alts; alim; alim = XEXP (alim, 1))
- {
- if (!(expr = count_loop_iterations (desc, XEXP (ainit, 0), XEXP (alim, 0))))
- abort ();
- if (GET_CODE (expr) == CONST_INT)
- {
- *niter = INTVAL (expr);
- return true;
- }
- }
-
- return false;
- }
-
- /* 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, e;
-
- 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);
- desc->neg = !fallthru_out;
-
- /* Find initial value of var. */
- e = loop_preheader_edge (loop);
- desc->var_alts = variable_initial_values (e, desc->var);
-
- /* Number of iterations. */
- if (!count_loop_iterations (desc, NULL, NULL))
- return false;
- desc->const_iter = constant_iterations (desc, &desc->niter, &desc->may_be_zero);
-
- if (rtl_dump_file)
- {
- fprintf (rtl_dump_file, "; Simple loop %i\n", loop->num);
- if (desc->postincr)
- fprintf (rtl_dump_file,
- "; does postincrement after loop exit condition\n");
-
- fprintf (rtl_dump_file, "; Induction variable:");
- print_simple_rtl (rtl_dump_file, desc->var);
- fputc ('\n', rtl_dump_file);
-
- fprintf (rtl_dump_file, "; Initial values:");
- print_simple_rtl (rtl_dump_file, desc->var_alts);
- fputc ('\n', rtl_dump_file);
-
- fprintf (rtl_dump_file, "; Stride:");
- print_simple_rtl (rtl_dump_file, desc->stride);
- fputc ('\n', rtl_dump_file);
-
- fprintf (rtl_dump_file, "; Compared with:");
- print_simple_rtl (rtl_dump_file, desc->lim);
- fputc ('\n', rtl_dump_file);
-
- fprintf (rtl_dump_file, "; Alternative values:");
- print_simple_rtl (rtl_dump_file, desc->lim_alts);
- fputc ('\n', rtl_dump_file);
-
- fprintf (rtl_dump_file, "; Exit condition:");
- if (desc->neg)
- fprintf (rtl_dump_file, "(negated)");
- fprintf (rtl_dump_file, "%s\n", GET_RTX_NAME (desc->cond));
- fputc ('\n', rtl_dump_file);
- }
- return true;
- }
-
- /* Return RTX expression representing number of iterations of loop as bounded
- by test described by DESC (in the case loop really has multiple exit
- edges, fewer iterations may happen in the practice).
-
- Return NULL if it is unknown. Additionally the value may be invalid for
- paradoxical loop (lets define paradoxical loops as loops whose test is
- failing at -1th iteration, for instance "for (i=5;i<1;i++);").
-
- 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 INIT/LIM are set, they are used instead of var/lim of DESC. */
- static rtx
- count_loop_iterations (desc, init, lim)
- struct loop_desc *desc;
- rtx init;
- rtx lim;
- {
- enum rtx_code cond = desc->cond;
- rtx stride = desc->stride;
- rtx mod, exp;
-
- init = init ? copy_rtx (init) : copy_rtx (desc->var);
- lim = lim ? copy_rtx (lim) : copy_rtx (desc->lim);
-
- /* Give up on floating point modes and friends. It can be possible to do
- the job for constant loop bounds, but it is probably not worthwhile. */
- if (!INTEGRAL_MODE_P (GET_MODE (desc->var)))
- return NULL;
-
- /* Ensure that we always handle the condition to stay inside loop. */
- if (desc->neg)
- cond = reverse_condition (cond);
-
- /* Compute absolute value of the difference of initial and final value. */
- if (INTVAL (stride) > 0)
- {
- /* Bypass nonsential tests. */
- if (cond == EQ || cond == GE || cond == GT || cond == GEU
- || cond == GTU)
- return NULL;
- exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
- lim, init);
- }
- else
- {
- /* Bypass nonsential tests. */
- if (cond == EQ || cond == LE || cond == LT || cond == LEU
- || cond == LTU)
- return NULL;
- exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
- init, lim);
- stride = simplify_gen_unary (NEG, GET_MODE (desc->var),
- stride, GET_MODE (desc->var));
- }
-
- /* Normalize difference so the value is always first examined
- and later incremented. */
-
- if (!desc->postincr)
- exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
- exp, stride);
-
- /* Determine delta caused by exit condition. */
- switch (cond)
- {
- case NE:
- /* For NE tests, make sure that the iteration variable won't miss
- the final value. If EXP mod STRIDE is not zero, then the
- iteration variable will overflow before the loop exits, and we
- can not calculate the number of iterations easilly. */
- if (stride != const1_rtx
- && (simplify_gen_binary (UMOD, GET_MODE (desc->var), exp, stride)
- != const0_rtx))
- return NULL;
- break;
- case LT:
- case GT:
- case LTU:
- case GTU:
- break;
- case LE:
- case GE:
- case LEU:
- case GEU:
- exp = simplify_gen_binary (PLUS, GET_MODE (desc->var),
- exp, const1_rtx);
- break;
- default:
- abort ();
- }
-
- if (stride != const1_rtx)
- {
- /* Number of iterations is now (EXP + STRIDE - 1 / STRIDE),
- but we need to take care for overflows. */
-
- mod = simplify_gen_binary (UMOD, GET_MODE (desc->var), exp, stride);
-
- /* This is dirty trick. When we can't compute number of iterations
- to be constant, we simply ignore the possible overflow, as
- runtime unroller always use power of 2 amounts and does not
- care about possible lost bits. */
-
- if (GET_CODE (mod) != CONST_INT)
- {
- rtx stridem1 = simplify_gen_binary (PLUS, GET_MODE (desc->var),
- stride, constm1_rtx);
- exp = simplify_gen_binary (PLUS, GET_MODE (desc->var),
- exp, stridem1);
- exp = simplify_gen_binary (UDIV, GET_MODE (desc->var), exp, stride);
- }
- else
- {
- exp = simplify_gen_binary (UDIV, GET_MODE (desc->var), exp, stride);
- if (mod != const0_rtx)
- exp = simplify_gen_binary (PLUS, GET_MODE (desc->var),
- exp, const1_rtx);
- }
- }
-
- if (rtl_dump_file)
- {
- fprintf (rtl_dump_file, "; Number of iterations: ");
- print_simple_rtl (rtl_dump_file, exp);
- fprintf (rtl_dump_file, "\n");
- }
-
- return exp;
- }
-
- /* Return simplified RTX expression representing the value of test
- described of DESC at given iteration of loop. */
-
- static rtx
- test_for_iteration (desc, iter)
- struct loop_desc *desc;
- unsigned HOST_WIDE_INT iter;
- {
- enum rtx_code cond = desc->cond;
- rtx exp = XEXP (desc->var_alts, 0);
- rtx addval;
-
- /* Give up on floating point modes and friends. It can be possible to do
- the job for constant loop bounds, but it is probably not worthwhile. */
- if (!INTEGRAL_MODE_P (GET_MODE (desc->var)))
- return NULL;
-
- /* Ensure that we always handle the condition to stay inside loop. */
- if (desc->neg)
- cond = reverse_condition (cond);
-
- /* Compute the value of induction variable. */
- addval = simplify_gen_binary (MULT, GET_MODE (desc->var),
- desc->stride,
- gen_int_mode (desc->postincr
- ? iter : iter + 1,
- GET_MODE (desc->var)));
- exp = simplify_gen_binary (PLUS, GET_MODE (desc->var), exp, addval);
- /* Test at given condtion. */
- exp = simplify_gen_relational (cond, SImode,
- GET_MODE (desc->var), exp, desc->lim);
-
- if (rtl_dump_file)
- {
- fprintf (rtl_dump_file,
- "; Conditional to continue loop at %i th iteration: ", iter);
- print_simple_rtl (rtl_dump_file, exp);
- fprintf (rtl_dump_file, "\n");
- }
- return exp;
- }
-
/* Peel NPEEL iterations from LOOP, remove exit edges (and cancel the loop
completely). */
static bool
--- 85,90 ----
More information about the Gcc-patches
mailing list