/* Natural loop analysis code for GNU compiler.
- Copyright (C) 2002 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
This file is part of GCC.
#include "output.h"
struct unmark_altered_insn_data;
-static void unmark_altered PARAMS ((rtx, rtx, regset));
-static void blocks_invariant_registers PARAMS ((basic_block *, int, regset));
-static void unmark_altered_insn PARAMS ((rtx, rtx, struct unmark_altered_insn_data *));
-static void blocks_single_set_registers PARAMS ((basic_block *, int, rtx *));
-static int invariant_rtx_wrto_regs_p_helper PARAMS ((rtx *, regset));
-static bool invariant_rtx_wrto_regs_p PARAMS ((rtx, regset));
-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, regset, rtx *,
- struct loop_desc *));
-static rtx variable_initial_value PARAMS ((rtx, regset, rtx, rtx *));
-static rtx variable_initial_values PARAMS ((edge, rtx));
-static bool simple_condition_p PARAMS ((struct loop *, rtx,
- regset, struct loop_desc *));
-static basic_block simple_increment PARAMS ((struct loops *, struct loop *,
- rtx *, struct loop_desc *));
+static void unmark_altered (rtx, rtx, regset);
+static void blocks_invariant_registers (basic_block *, int, regset);
+static void unmark_altered_insn (rtx, rtx, struct unmark_altered_insn_data *);
+static void blocks_single_set_registers (basic_block *, int, rtx *);
+static int invariant_rtx_wrto_regs_p_helper (rtx *, regset);
+static bool invariant_rtx_wrto_regs_p (rtx, regset);
+static rtx test_for_iteration (struct loop_desc *desc, unsigned HOST_WIDE_INT);
+static bool constant_iterations (struct loop_desc *, unsigned HOST_WIDE_INT *,
+ bool *);
+static bool simple_loop_exit_p (struct loop *, edge, regset,
+ rtx *, struct loop_desc *);
+static rtx variable_initial_value (rtx, regset, rtx, rtx *, enum machine_mode);
+static rtx variable_initial_values (edge, rtx, enum machine_mode);
+static bool simple_condition_p (struct loop *, rtx, regset,
+ struct loop_desc *);
+static basic_block simple_increment (struct loop *, rtx *, struct loop_desc *);
+static rtx count_strange_loop_iterations (rtx, rtx, enum rtx_code,
+ int, rtx, enum machine_mode,
+ enum machine_mode);
+static unsigned HOST_WIDEST_INT inverse (unsigned HOST_WIDEST_INT, int);
+static bool fits_in_mode_p (enum machine_mode mode, rtx expr);
+
+/* Computes inverse to X modulo (1 << MOD). */
+static unsigned HOST_WIDEST_INT
+inverse (unsigned HOST_WIDEST_INT x, int mod)
+{
+ unsigned HOST_WIDEST_INT mask =
+ ((unsigned HOST_WIDEST_INT) 1 << (mod - 1) << 1) - 1;
+ unsigned HOST_WIDEST_INT rslt = 1;
+ int i;
+
+ for (i = 0; i < mod - 1; i++)
+ {
+ rslt = (rslt * x) & mask;
+ x = (x * x) & mask;
+ }
+
+ return rslt;
+}
/* Checks whether BB is executed exactly once in each LOOP iteration. */
bool
-just_once_each_iteration_p (loops, loop, bb)
- struct loops *loops;
- struct loop *loop;
- basic_block bb;
+just_once_each_iteration_p (struct loop *loop, basic_block bb)
{
/* It must be executed at least once each iteration. */
- if (!dominated_by_p (loops->cfg.dom, loop->latch, bb))
+ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
return false;
/* And just once. */
/* Unmarks modified registers; helper to blocks_invariant_registers. */
static void
-unmark_altered (what, by, regs)
- rtx what;
- rtx by ATTRIBUTE_UNUSED;
- regset regs;
+unmark_altered (rtx what, rtx by ATTRIBUTE_UNUSED, regset regs)
{
if (GET_CODE (what) == SUBREG)
what = SUBREG_REG (what);
/* Marks registers that are invariant inside blocks BBS. */
static void
-blocks_invariant_registers (bbs, nbbs, regs)
- basic_block *bbs;
- int nbbs;
- regset regs;
+blocks_invariant_registers (basic_block *bbs, int nbbs, regset regs)
{
rtx insn;
int i;
for (i = 0; i < max_reg_num (); i++)
SET_REGNO_REG_SET (regs, i);
for (i = 0; i < nbbs; i++)
- for (insn = bbs[i]->head;
- insn != NEXT_INSN (bbs[i]->end);
+ for (insn = BB_HEAD (bbs[i]);
+ insn != NEXT_INSN (BB_END (bbs[i]));
insn = NEXT_INSN (insn))
if (INSN_P (insn))
note_stores (PATTERN (insn),
- (void (*) PARAMS ((rtx, rtx, void *))) unmark_altered,
+ (void (*) (rtx, rtx, void *)) unmark_altered,
regs);
}
};
static void
-unmark_altered_insn (what, by, data)
- rtx what;
- rtx by ATTRIBUTE_UNUSED;
- struct unmark_altered_insn_data *data;
+unmark_altered_insn (rtx what, rtx by ATTRIBUTE_UNUSED,
+ struct unmark_altered_insn_data *data)
{
int rn;
/* Marks registers that have just single simple set in BBS; the relevant
insn is returned in REGS. */
static void
-blocks_single_set_registers (bbs, nbbs, regs)
- basic_block *bbs;
- int nbbs;
- rtx *regs;
+blocks_single_set_registers (basic_block *bbs, int nbbs, rtx *regs)
{
rtx insn;
int i;
regs[i] = NULL;
for (i = 0; i < nbbs; i++)
- for (insn = bbs[i]->head;
- insn != NEXT_INSN (bbs[i]->end);
+ for (insn = BB_HEAD (bbs[i]);
+ insn != NEXT_INSN (BB_END (bbs[i]));
insn = NEXT_INSN (insn))
{
rtx set = single_set (insn);
data.regs = regs;
for (i = 0; i < nbbs; i++)
- for (insn = bbs[i]->head;
- insn != NEXT_INSN (bbs[i]->end);
+ for (insn = BB_HEAD (bbs[i]);
+ insn != NEXT_INSN (BB_END (bbs[i]));
insn = NEXT_INSN (insn))
{
if (!INSN_P (insn))
continue;
data.insn = insn;
note_stores (PATTERN (insn),
- (void (*) PARAMS ((rtx, rtx, void *))) unmark_altered_insn,
+ (void (*) (rtx, rtx, void *)) unmark_altered_insn,
&data);
}
}
/* Helper for invariant_rtx_wrto_regs_p. */
static int
-invariant_rtx_wrto_regs_p_helper (expr, invariant_regs)
- rtx *expr;
- regset invariant_regs;
+invariant_rtx_wrto_regs_p_helper (rtx *expr, regset invariant_regs)
{
switch (GET_CODE (*expr))
{
/* Checks that EXPR is invariant provided that INVARIANT_REGS are invariant. */
static bool
-invariant_rtx_wrto_regs_p (expr, invariant_regs)
- rtx expr;
- regset invariant_regs;
+invariant_rtx_wrto_regs_p (rtx expr, regset invariant_regs)
{
return !for_each_rtx (&expr, (rtx_function) invariant_rtx_wrto_regs_p_helper,
invariant_regs);
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, condition, invariant_regs, desc)
- struct loop *loop ATTRIBUTE_UNUSED;
- rtx condition;
- regset invariant_regs;
- struct loop_desc *desc;
+simple_condition_p (struct loop *loop ATTRIBUTE_UNUSED, rtx condition,
+ regset invariant_regs, struct loop_desc *desc)
{
rtx op0, op1;
/* One of operands must be a simple register. */
op0 = XEXP (condition, 0);
op1 = XEXP (condition, 1);
-
+
/* One of operands must be invariant. */
if (invariant_rtx_wrto_regs_p (op0, invariant_regs))
{
iteration. Fills in DESC->stride and returns block in that DESC->var is
modified. */
static basic_block
-simple_increment (loops, loop, simple_increment_regs, desc)
- struct loops *loops;
- struct loop *loop;
- rtx *simple_increment_regs;
- struct loop_desc *desc;
+simple_increment (struct loop *loop, rtx *simple_increment_regs,
+ struct loop_desc *desc)
{
- rtx mod_insn, set, set_src, set_add;
- basic_block mod_bb;
+ rtx mod_insn, mod_insn1, set, set_src, set_add;
+ basic_block mod_bb, mod_bb1;
/* Find insn that modifies var. */
mod_insn = simple_increment_regs[REGNO (desc->var)];
mod_bb = BLOCK_FOR_INSN (mod_insn);
/* Check that it is executed exactly once each iteration. */
- if (!just_once_each_iteration_p (loops, loop, mod_bb))
+ if (!just_once_each_iteration_p (loop, mod_bb))
return NULL;
/* mod_insn must be a simple increment/decrement. */
set_src = find_reg_equal_equiv_note (mod_insn);
if (!set_src)
set_src = SET_SRC (set);
+
+ /* Check for variables that iterate in narrower mode. */
+ if (GET_CODE (set_src) == SIGN_EXTEND
+ || GET_CODE (set_src) == ZERO_EXTEND)
+ {
+ /* If we are sign extending variable that is then compared unsigned
+ or vice versa, there is something weird happening. */
+ if (desc->cond != EQ
+ && desc->cond != NE
+ && ((desc->cond == LEU
+ || desc->cond == LTU
+ || desc->cond == GEU
+ || desc->cond == GTU)
+ ^ (GET_CODE (set_src) == ZERO_EXTEND)))
+ return NULL;
+
+ if (GET_CODE (XEXP (set_src, 0)) != SUBREG
+ || SUBREG_BYTE (XEXP (set_src, 0)) != 0
+ || GET_MODE (SUBREG_REG (XEXP (set_src, 0))) != GET_MODE (desc->var))
+ return NULL;
+
+ desc->inner_mode = GET_MODE (XEXP (set_src, 0));
+ desc->extend = GET_CODE (set_src);
+ set_src = SUBREG_REG (XEXP (set_src, 0));
+
+ if (GET_CODE (set_src) != REG)
+ return NULL;
+
+ /* Find where the reg is set. */
+ mod_insn1 = simple_increment_regs[REGNO (set_src)];
+ if (!mod_insn1)
+ return NULL;
+
+ mod_bb1 = BLOCK_FOR_INSN (mod_insn1);
+ if (!dominated_by_p (CDI_DOMINATORS, mod_bb, mod_bb1))
+ return NULL;
+ if (mod_bb1 == mod_bb)
+ {
+ for (;
+ mod_insn != PREV_INSN (BB_HEAD (mod_bb));
+ mod_insn = PREV_INSN (mod_insn))
+ if (mod_insn == mod_insn1)
+ break;
+
+ if (mod_insn == PREV_INSN (BB_HEAD (mod_bb)))
+ return NULL;
+ }
+
+ /* Replace the source with the possible place of increment. */
+ set = single_set (mod_insn1);
+ if (!set)
+ abort ();
+ if (!rtx_equal_p (SET_DEST (set), set_src))
+ abort ();
+
+ set_src = find_reg_equal_equiv_note (mod_insn1);
+ if (!set_src)
+ set_src = SET_SRC (set);
+ }
+ else
+ {
+ desc->inner_mode = GET_MODE (desc->var);
+ desc->extend = NIL;
+ }
+
if (GET_CODE (set_src) != PLUS)
return NULL;
if (!rtx_equal_p (XEXP (set_src, 0), desc->var))
/* Tries to find initial value of VAR in INSN. This value must be invariant
wrto INVARIANT_REGS. If SET_INSN is not NULL, insn in that var is set is
- placed here. */
+ placed here. INNER_MODE is mode in that induction variable VAR iterates. */
static rtx
-variable_initial_value (insn, invariant_regs, var, set_insn)
- rtx insn;
- regset invariant_regs;
- rtx var;
- rtx *set_insn;
+variable_initial_value (rtx insn, regset invariant_regs,
+ rtx var, rtx *set_insn, enum machine_mode inner_mode)
{
basic_block bb;
rtx set;
+ rtx ret = NULL;
/* Go back through cfg. */
bb = BLOCK_FOR_INSN (insn);
while (1)
{
- for (; insn != bb->head; insn = PREV_INSN (insn))
+ for (; insn != BB_HEAD (bb); insn = PREV_INSN (insn))
{
- if (modified_between_p (var, PREV_INSN (insn), NEXT_INSN (insn)))
- break;
if (INSN_P (insn))
note_stores (PATTERN (insn),
- (void (*) PARAMS ((rtx, rtx, void *))) unmark_altered,
+ (void (*) (rtx, rtx, void *)) unmark_altered,
invariant_regs);
+ if (modified_between_p (var, PREV_INSN (insn), NEXT_INSN (insn)))
+ break;
}
- if (insn != bb->head)
+ if (insn != BB_HEAD (bb))
{
/* We found place where var is set. */
rtx set_dest;
rtx val;
rtx note;
-
+
set = single_set (insn);
if (!set)
return NULL;
val = XEXP (note, 0);
else
val = SET_SRC (set);
+
+ /* If we know that the initial value is indeed in range of
+ the inner mode, record the fact even in case the value itself
+ is useless. */
+ if ((GET_CODE (val) == SIGN_EXTEND
+ || GET_CODE (val) == ZERO_EXTEND)
+ && GET_MODE (XEXP (val, 0)) == inner_mode)
+ ret = gen_rtx_fmt_e (GET_CODE (val),
+ GET_MODE (var),
+ gen_rtx_fmt_ei (SUBREG,
+ inner_mode,
+ var, 0));
+
if (!invariant_rtx_wrto_regs_p (val, invariant_regs))
- return NULL;
+ return ret;
if (set_insn)
*set_insn = insn;
return NULL;
bb = bb->pred->src;
- insn = bb->end;
+ insn = BB_END (bb);
}
return NULL;
}
-/* Returns list of definitions of initial value of VAR at Edge. */
+/* Returns list of definitions of initial value of VAR at edge E. INNER_MODE
+ is mode in that induction variable VAR really iterates. */
static rtx
-variable_initial_values (e, var)
- edge e;
- rtx var;
+variable_initial_values (edge e, rtx var, enum machine_mode inner_mode)
{
rtx set_insn, list;
regset invariant_regs;
if (e->src == ENTRY_BLOCK_PTR)
return list;
- set_insn = e->src->end;
+ set_insn = BB_END (e->src);
while (REG_P (var)
- && (var = variable_initial_value (set_insn, invariant_regs, var, &set_insn)))
+ && (var = variable_initial_value (set_insn, invariant_regs, var,
+ &set_insn, inner_mode)))
list = alloc_EXPR_LIST (0, copy_rtx (var), list);
FREE_REG_SET (invariant_regs);
/* 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;
+constant_iterations (struct loop_desc *desc, unsigned HOST_WIDE_INT *niter,
+ bool *may_be_zero)
{
rtx test, expr;
rtx ainit, alim;
{
alim = XEXP (desc->lim_alts, 0);
if (!(expr = count_loop_iterations (desc, XEXP (ainit, 0), alim)))
- abort ();
+ continue;
if (GET_CODE (expr) == CONST_INT)
{
*niter = INTVAL (expr);
{
ainit = XEXP (desc->var_alts, 0);
if (!(expr = count_loop_iterations (desc, ainit, XEXP (alim, 0))))
- abort ();
+ continue;
if (GET_CODE (expr) == CONST_INT)
{
*niter = INTVAL (expr);
return false;
}
+/* Attempts to determine a number of iterations of a "strange" loop.
+ Its induction variable starts with value INIT, is compared by COND
+ with LIM. If POSTINCR, it is incremented after the test. It is incremented
+ by STRIDE each iteration, has mode MODE but iterates in INNER_MODE.
+
+ By "strange" we mean loops where induction variable increases in the wrong
+ direction wrto comparison, i.e. for (i = 6; i > 5; i++). */
+static rtx
+count_strange_loop_iterations (rtx init, rtx lim, enum rtx_code cond,
+ int postincr, rtx stride, enum machine_mode mode,
+ enum machine_mode inner_mode)
+{
+ rtx rqmt, n_to_wrap, before_wrap, after_wrap;
+ rtx mode_min, mode_max;
+ int size;
+
+ /* This could be handled, but it is not important enough to lose time with
+ it just now. */
+ if (mode != inner_mode)
+ return NULL_RTX;
+
+ if (!postincr)
+ init = simplify_gen_binary (PLUS, mode, init, stride);
+
+ /* If we are able to prove that we don't pass the first test, we are
+ done. */
+ rqmt = simplify_relational_operation (cond, mode, init, lim);
+ if (rqmt == const0_rtx)
+ return const0_rtx;
+
+ /* And if we don't know we pass it, the things are too complicated for us. */
+ if (rqmt != const_true_rtx)
+ return NULL_RTX;
+
+ switch (cond)
+ {
+ case GE:
+ case GT:
+ case LE:
+ case LT:
+ size = GET_MODE_BITSIZE (mode);
+ mode_min = GEN_INT (-((unsigned HOST_WIDEST_INT) 1 << (size - 1)));
+ mode_max = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1)) - 1);
+
+ break;
+
+ case GEU:
+ case GTU:
+ case LEU:
+ case LTU:
+ case EQ:
+ mode_min = const0_rtx;
+ mode_max = simplify_gen_binary (MINUS, mode, const0_rtx, const1_rtx);
+ break;
+
+ default:
+ abort ();
+ }
+
+ switch (cond)
+ {
+ case EQ:
+ /* This iterates once, as init == lim. */
+ return const1_rtx;
+
+ /* The behavior is undefined in signed cases. Never mind, we still
+ try to behave sanely. */
+ case GE:
+ case GT:
+ case GEU:
+ case GTU:
+ if (INTVAL (stride) <= 0)
+ abort ();
+ n_to_wrap = simplify_gen_binary (MINUS, mode, mode_max, copy_rtx (init));
+ n_to_wrap = simplify_gen_binary (UDIV, mode, n_to_wrap, stride);
+ before_wrap = simplify_gen_binary (MULT, mode,
+ copy_rtx (n_to_wrap), stride);
+ before_wrap = simplify_gen_binary (PLUS, mode,
+ before_wrap, copy_rtx (init));
+ after_wrap = simplify_gen_binary (PLUS, mode,
+ before_wrap, stride);
+ if (GET_CODE (after_wrap) != CONST_INT)
+ {
+ after_wrap = simplify_gen_binary (PLUS, mode, mode_min, stride);
+ after_wrap = simplify_gen_binary (MINUS, mode, after_wrap, const1_rtx);
+ }
+ break;
+
+ case LE:
+ case LT:
+ case LEU:
+ case LTU:
+ if (INTVAL (stride) >= 0)
+ abort ();
+ stride = simplify_gen_unary (NEG, mode, stride, mode);
+ n_to_wrap = simplify_gen_binary (MINUS, mode, copy_rtx (init), mode_min);
+ n_to_wrap = simplify_gen_binary (UDIV, mode, n_to_wrap, stride);
+ before_wrap = simplify_gen_binary (MULT, mode,
+ copy_rtx (n_to_wrap), stride);
+ before_wrap = simplify_gen_binary (MINUS, mode,
+ copy_rtx (init), before_wrap);
+ after_wrap = simplify_gen_binary (MINUS, mode,
+ before_wrap, stride);
+ if (GET_CODE (after_wrap) != CONST_INT)
+ {
+ after_wrap = simplify_gen_binary (MINUS, mode, mode_max, stride);
+ after_wrap = simplify_gen_binary (PLUS, mode, after_wrap, const1_rtx);
+ }
+ break;
+ default:
+ abort ();
+ }
+
+ /* If this is const_true_rtx and we did not take a conservative approximation
+ of after_wrap above, we might iterate the calculation (but of course we
+ would have to take care about infinite cases). Ignore this for now. */
+ rqmt = simplify_relational_operation (cond, mode, after_wrap, lim);
+ if (rqmt != const0_rtx)
+ return NULL_RTX;
+
+ return simplify_gen_binary (PLUS, mode, n_to_wrap, const1_rtx);
+}
+
+/* Checks whether value of EXPR fits into range of MODE. */
+static bool
+fits_in_mode_p (enum machine_mode mode, rtx expr)
+{
+ unsigned HOST_WIDEST_INT val;
+ int n_bits = 0;
+
+ if (GET_CODE (expr) == CONST_INT)
+ {
+ for (val = INTVAL (expr); val; val >>= 1)
+ n_bits++;
+
+ return n_bits <= GET_MODE_BITSIZE (mode);
+ }
+
+ if (GET_CODE (expr) == SIGN_EXTEND
+ || GET_CODE (expr) == ZERO_EXTEND)
+ return GET_MODE (XEXP (expr, 0)) == mode;
+
+ return false;
+}
+
/* 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).
+ 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 either 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;
+count_loop_iterations (struct loop_desc *desc, rtx init, rtx lim)
{
enum rtx_code cond = desc->cond;
rtx stride = desc->stride;
- rtx mod, exp;
+ rtx mod, exp, ainit, bound;
+ rtx overflow_check, mx, mxp;
+ enum machine_mode mode = GET_MODE (desc->var);
+ unsigned HOST_WIDEST_INT s, size, d;
/* 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)))
+ if (!INTEGRAL_MODE_P (mode))
return NULL;
init = copy_rtx (init ? init : desc->var);
if (desc->neg)
cond = reverse_condition (cond);
+ if (desc->inner_mode != mode)
+ {
+ /* We have a case when the variable in fact iterates in the narrower
+ mode. This has following consequences:
+
+ For induction variable itself, if !desc->postincr, it does not mean
+ anything too special, since we know the variable is already in range
+ of the inner mode when we compare it (so it is just needed to shorten
+ it into the mode before calculations are done, so that we don't risk
+ wrong results). More complicated case is when desc->postincr; then
+ the first two iterations are special (the first one because the value
+ may be out of range, the second one because after shortening it to the
+ range it may have absolutely any value), and we do not handle this in
+ unrolling. So if we aren't able to prove that the initial value is in
+ the range, we fail in this case.
+
+ Step is just moduled to fit into inner mode.
+
+ If lim is out of range, then either the loop is infinite (and then
+ we may unroll however we like to), or exits in the first iteration
+ (this is also ok, since we handle it specially for this case anyway).
+ So we may safely assume that it fits into the inner mode. */
+
+ for (ainit = desc->var_alts; ainit; ainit = XEXP (ainit, 1))
+ if (fits_in_mode_p (desc->inner_mode, XEXP (ainit, 0)))
+ break;
+
+ if (!ainit)
+ {
+ if (desc->postincr)
+ return NULL_RTX;
+
+ init = simplify_gen_unary (desc->extend,
+ mode,
+ simplify_gen_subreg (desc->inner_mode,
+ init,
+ mode,
+ 0),
+ desc->inner_mode);
+ }
+
+ stride = simplify_gen_subreg (desc->inner_mode, stride, mode, 0);
+ if (stride == const0_rtx)
+ return NULL_RTX;
+ }
+
+ /* Prepare condition to verify that we do not risk overflow. */
+ if (stride == const1_rtx
+ || stride == constm1_rtx
+ || cond == NE
+ || cond == EQ)
+ {
+ /* Overflow at NE conditions does not occur. EQ condition
+ is weird and is handled in count_strange_loop_iterations.
+ If stride is 1, overflow may occur only for <= and >= conditions,
+ and then they are infinite, so it does not bother us. */
+ overflow_check = const0_rtx;
+ }
+ else
+ {
+ if (cond == LT || cond == LTU)
+ mx = simplify_gen_binary (MINUS, mode, lim, const1_rtx);
+ else if (cond == GT || cond == GTU)
+ mx = simplify_gen_binary (PLUS, mode, lim, const1_rtx);
+ else
+ mx = lim;
+ if (mode != desc->inner_mode)
+ mxp = simplify_gen_subreg (desc->inner_mode, mx, mode, 0);
+ else
+ mxp = mx;
+ mxp = simplify_gen_binary (PLUS, desc->inner_mode, mxp, stride);
+ if (mode != desc->inner_mode)
+ mxp = simplify_gen_unary (desc->extend, mode, mxp, desc->inner_mode);
+ overflow_check = simplify_gen_relational (cond, SImode, mode, mx, mxp);
+ }
+
/* Compute absolute value of the difference of initial and final value. */
if (INTVAL (stride) > 0)
{
- /* Bypass nonsensical tests. */
+ /* Handle strange tests specially. */
if (cond == EQ || cond == GE || cond == GT || cond == GEU
|| cond == GTU)
- return NULL;
- exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
- lim, init);
+ return count_strange_loop_iterations (init, lim, cond, desc->postincr,
+ stride, mode, desc->inner_mode);
+ exp = simplify_gen_binary (MINUS, mode, lim, init);
}
else
{
- /* Bypass nonsensical 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));
+ return count_strange_loop_iterations (init, lim, cond, desc->postincr,
+ stride, mode, desc->inner_mode);
+ exp = simplify_gen_binary (MINUS, mode, init, lim);
+ stride = simplify_gen_unary (NEG, mode, stride, mode);
}
+ /* If there is a risk of overflow (i.e. when we increment value satisfying
+ a condition, we may again obtain a value satisfying the condition),
+ fail. */
+ if (overflow_check != const0_rtx)
+ return NULL_RTX;
+
/* 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);
+ exp = simplify_gen_binary (MINUS, mode, 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 easily. */
- if (stride != const1_rtx
- && (simplify_gen_binary (UMOD, GET_MODE (desc->var), exp, stride)
- != const0_rtx))
- return NULL;
+ /* NE tests are easy to handle, because we just perform simple
+ arithmetics modulo power of 2. Let's use the fact to compute the
+ number of iterations exactly. We are now in situation when we want to
+ solve an equation stride * i = c (mod size of inner_mode).
+ Let nsd (stride, size of mode) = d. If d does not divide c, the
+ loop is infinite. Otherwise, the number of iterations is
+ (inverse(s/d) * (c/d)) mod (size of mode/d). */
+ size = GET_MODE_BITSIZE (desc->inner_mode);
+ s = INTVAL (stride);
+ d = 1;
+ while (s % 2 != 1)
+ {
+ s /= 2;
+ d *= 2;
+ size--;
+ }
+ bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
+ exp = simplify_gen_binary (UDIV, mode, exp, GEN_INT (d));
+ exp = simplify_gen_binary (MULT, mode,
+ exp, GEN_INT (inverse (s, size)));
+ exp = simplify_gen_binary (AND, mode, exp, bound);
break;
+
case LT:
case GT:
case LTU:
case GE:
case LEU:
case GEU:
- exp = simplify_gen_binary (PLUS, GET_MODE (desc->var),
- exp, const1_rtx);
+ exp = simplify_gen_binary (PLUS, mode, exp, const1_rtx);
break;
default:
abort ();
}
- if (stride != const1_rtx)
+ if (cond != NE && 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);
+ mod = simplify_gen_binary (UMOD, mode, exp, stride);
/* This is dirty trick. When we can't compute number of iterations
to be constant, we simply ignore the possible overflow, as
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);
+ rtx stridem1 = simplify_gen_binary (PLUS, mode, stride, constm1_rtx);
+ exp = simplify_gen_binary (PLUS, mode, exp, stridem1);
+ exp = simplify_gen_binary (UDIV, mode, exp, stride);
}
else
{
- exp = simplify_gen_binary (UDIV, GET_MODE (desc->var), exp, stride);
+ exp = simplify_gen_binary (UDIV, mode, exp, stride);
if (mod != const0_rtx)
- exp = simplify_gen_binary (PLUS, GET_MODE (desc->var),
- exp, const1_rtx);
+ exp = simplify_gen_binary (PLUS, mode, exp, const1_rtx);
}
}
- if (rtl_dump_file)
+ if (dump_file)
{
- fprintf (rtl_dump_file, "; Number of iterations: ");
- print_simple_rtl (rtl_dump_file, exp);
- fprintf (rtl_dump_file, "\n");
+ fprintf (dump_file, "; Number of iterations: ");
+ print_simple_rtl (dump_file, exp);
+ fprintf (dump_file, "\n");
}
return exp;
described of DESC at given iteration of loop. */
static rtx
-test_for_iteration (desc, iter)
- struct loop_desc *desc;
- unsigned HOST_WIDE_INT iter;
+test_for_iteration (struct loop_desc *desc, unsigned HOST_WIDE_INT iter)
{
enum rtx_code cond = desc->cond;
rtx exp = XEXP (desc->var_alts, 0);
exp = simplify_gen_relational (cond, SImode,
GET_MODE (desc->var), exp, desc->lim);
- if (rtl_dump_file)
+ if (dump_file)
{
- fprintf (rtl_dump_file, "; Conditional to continue loop at "
+ fprintf (dump_file, "; Conditional to continue loop at "
HOST_WIDE_INT_PRINT_UNSIGNED "th iteration: ", iter);
- print_simple_rtl (rtl_dump_file, exp);
- fprintf (rtl_dump_file, "\n");
+ print_simple_rtl (dump_file, exp);
+ fprintf (dump_file, "\n");
}
return exp;
}
description joined to it in in DESC. INVARIANT_REGS and SINGLE_SET_REGS
are results of blocks_{invariant,single_set}_regs over BODY. */
static bool
-simple_loop_exit_p (loops, loop, exit_edge, invariant_regs, single_set_regs, desc)
- struct loops *loops;
- struct loop *loop;
- edge exit_edge;
- struct loop_desc *desc;
- regset invariant_regs;
- rtx *single_set_regs;
+simple_loop_exit_p (struct loop *loop, edge exit_edge,
+ regset invariant_regs, rtx *single_set_regs,
+ struct loop_desc *desc)
{
basic_block mod_bb, exit_bb;
int fallthru_out;
return false;
/* It must be tested (at least) once during any iteration. */
- if (!dominated_by_p (loops->cfg.dom, loop->latch, exit_bb))
+ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
return false;
/* It must end in a simple conditional jump. */
- if (!any_condjump_p (exit_bb->end))
+ if (!any_condjump_p (BB_END (exit_bb)))
return false;
ei = exit_bb->succ;
/* 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)))
+ if (!(condition = get_condition (BB_END (exit_bb), NULL, false)))
return false;
if (!simple_condition_p (loop, condition, invariant_regs, desc))
/* 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, single_set_regs, desc)))
+ if (!(mod_bb = simple_increment (loop, single_set_regs, 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->postincr = !dominated_by_p (CDI_DOMINATORS, exit_bb, mod_bb);
desc->neg = !fallthru_out;
/* Find initial value of var and alternative values for lim. */
e = loop_preheader_edge (loop);
- desc->var_alts = variable_initial_values (e, desc->var);
- desc->lim_alts = variable_initial_values (e, desc->lim);
+ desc->var_alts = variable_initial_values (e, desc->var, desc->inner_mode);
+ desc->lim_alts = variable_initial_values (e, desc->lim, desc->inner_mode);
/* 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 (!desc->const_iter && !count_loop_iterations (desc, NULL, NULL))
+ return false;
return true;
}
/* 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;
+simple_loop_p (struct loop *loop, struct loop_desc *desc)
{
unsigned i;
basic_block *body;
regset_head invariant_regs_head;
rtx *single_set_regs;
int n_branches;
-
+
body = get_loop_body (loop);
invariant_regs = INITIALIZE_REG_SET (invariant_regs_head);
{
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,
+ && simple_loop_exit_p (loop, e,
invariant_regs, single_set_regs, &act))
{
/* Prefer constant iterations; the less the better. */
}
desc->n_branches = n_branches;
- if (rtl_dump_file && any)
+ if (dump_file && any)
{
- fprintf (rtl_dump_file, "; Simple loop %i\n", loop->num);
+ fprintf (dump_file, "; Simple loop %i\n", loop->num);
if (desc->postincr)
- fprintf (rtl_dump_file,
+ fprintf (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 (dump_file, "; Induction variable:");
+ print_simple_rtl (dump_file, desc->var);
+ fputc ('\n', dump_file);
- fprintf (rtl_dump_file, "; Initial values:");
- print_simple_rtl (rtl_dump_file, desc->var_alts);
- fputc ('\n', rtl_dump_file);
+ fprintf (dump_file, "; Initial values:");
+ print_simple_rtl (dump_file, desc->var_alts);
+ fputc ('\n', dump_file);
- fprintf (rtl_dump_file, "; Stride:");
- print_simple_rtl (rtl_dump_file, desc->stride);
- fputc ('\n', rtl_dump_file);
+ fprintf (dump_file, "; Stride:");
+ print_simple_rtl (dump_file, desc->stride);
+ fputc ('\n', dump_file);
- fprintf (rtl_dump_file, "; Compared with:");
- print_simple_rtl (rtl_dump_file, desc->lim);
- fputc ('\n', rtl_dump_file);
+ fprintf (dump_file, "; Compared with:");
+ print_simple_rtl (dump_file, desc->lim);
+ fputc ('\n', dump_file);
- fprintf (rtl_dump_file, "; Alternative values:");
- print_simple_rtl (rtl_dump_file, desc->lim_alts);
- fputc ('\n', rtl_dump_file);
+ fprintf (dump_file, "; Alternative values:");
+ print_simple_rtl (dump_file, desc->lim_alts);
+ fputc ('\n', dump_file);
- fprintf (rtl_dump_file, "; Exit condition:");
+ fprintf (dump_file, "; Exit condition:");
if (desc->neg)
- fprintf (rtl_dump_file, "(negated)");
- fprintf (rtl_dump_file, "%s\n", GET_RTX_NAME (desc->cond));
+ fprintf (dump_file, "(negated)");
+ fprintf (dump_file, "%s\n", GET_RTX_NAME (desc->cond));
- fprintf (rtl_dump_file, "; Number of branches:");
- fprintf (rtl_dump_file, "%d\n", desc->n_branches);
+ fprintf (dump_file, "; Number of branches:");
+ fprintf (dump_file, "%d\n", desc->n_branches);
- fputc ('\n', rtl_dump_file);
+ fputc ('\n', dump_file);
}
free (body);
return any;
}
+/* Structure representing edge of a graph. */
+
+struct edge
+{
+ int src, dest; /* Source and destination. */
+ struct edge *pred_next, *succ_next;
+ /* Next edge in predecessor and successor lists. */
+ void *data; /* Data attached to the edge. */
+};
+
+/* Structure representing vertex of a graph. */
+
+struct vertex
+{
+ struct edge *pred, *succ;
+ /* Lists of predecessors and successors. */
+ int component; /* Number of dfs restarts before reaching the
+ vertex. */
+ int post; /* Postorder number. */
+};
+
+/* Structure representing a graph. */
+
+struct graph
+{
+ int n_vertices; /* Number of vertices. */
+ struct vertex *vertices;
+ /* The vertices. */
+};
+
+/* Dumps graph G into F. */
+
+extern void dump_graph (FILE *, struct graph *);
+void dump_graph (FILE *f, struct graph *g)
+{
+ int i;
+ struct edge *e;
+
+ for (i = 0; i < g->n_vertices; i++)
+ {
+ if (!g->vertices[i].pred
+ && !g->vertices[i].succ)
+ continue;
+
+ fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component);
+ for (e = g->vertices[i].pred; e; e = e->pred_next)
+ fprintf (f, " %d", e->src);
+ fprintf (f, "\n");
+
+ fprintf (f, "\t->");
+ for (e = g->vertices[i].succ; e; e = e->succ_next)
+ fprintf (f, " %d", e->dest);
+ fprintf (f, "\n");
+ }
+}
+
+/* Creates a new graph with N_VERTICES vertices. */
+
+static struct graph *
+new_graph (int n_vertices)
+{
+ struct graph *g = xmalloc (sizeof (struct graph));
+
+ g->n_vertices = n_vertices;
+ g->vertices = xcalloc (n_vertices, sizeof (struct vertex));
+
+ return g;
+}
+
+/* Adds an edge from F to T to graph G, with DATA attached. */
+
+static void
+add_edge (struct graph *g, int f, int t, void *data)
+{
+ struct edge *e = xmalloc (sizeof (struct edge));
+
+ e->src = f;
+ e->dest = t;
+ e->data = data;
+
+ e->pred_next = g->vertices[t].pred;
+ g->vertices[t].pred = e;
+
+ e->succ_next = g->vertices[f].succ;
+ g->vertices[f].succ = e;
+}
+
+/* Runs dfs search over vertices of G, from NQ vertices in queue QS.
+ The vertices in postorder are stored into QT. If FORWARD is false,
+ backward dfs is run. */
+
+static void
+dfs (struct graph *g, int *qs, int nq, int *qt, bool forward)
+{
+ int i, tick = 0, v, comp = 0, top;
+ struct edge *e;
+ struct edge **stack = xmalloc (sizeof (struct edge *) * g->n_vertices);
+
+ for (i = 0; i < g->n_vertices; i++)
+ {
+ g->vertices[i].component = -1;
+ g->vertices[i].post = -1;
+ }
+
+#define FST_EDGE(V) (forward ? g->vertices[(V)].succ : g->vertices[(V)].pred)
+#define NEXT_EDGE(E) (forward ? (E)->succ_next : (E)->pred_next)
+#define EDGE_SRC(E) (forward ? (E)->src : (E)->dest)
+#define EDGE_DEST(E) (forward ? (E)->dest : (E)->src)
+
+ for (i = 0; i < nq; i++)
+ {
+ v = qs[i];
+ if (g->vertices[v].post != -1)
+ continue;
+
+ g->vertices[v].component = comp++;
+ e = FST_EDGE (v);
+ top = 0;
+
+ while (1)
+ {
+ while (e && g->vertices[EDGE_DEST (e)].component != -1)
+ e = NEXT_EDGE (e);
+
+ if (!e)
+ {
+ if (qt)
+ qt[tick] = v;
+ g->vertices[v].post = tick++;
+
+ if (!top)
+ break;
+
+ e = stack[--top];
+ v = EDGE_SRC (e);
+ e = NEXT_EDGE (e);
+ continue;
+ }
+
+ stack[top++] = e;
+ v = EDGE_DEST (e);
+ e = FST_EDGE (v);
+ g->vertices[v].component = comp - 1;
+ }
+ }
+
+ free (stack);
+}
+
+/* Marks the edge E in graph G irreducible if it connects two vertices in the
+ same scc. */
+
+static void
+check_irred (struct graph *g, struct edge *e)
+{
+ edge real = e->data;
+
+ /* All edges should lead from a component with higher number to the
+ one with lower one. */
+ if (g->vertices[e->src].component < g->vertices[e->dest].component)
+ abort ();
+
+ if (g->vertices[e->src].component != g->vertices[e->dest].component)
+ return;
+
+ real->flags |= EDGE_IRREDUCIBLE_LOOP;
+ if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
+ real->src->flags |= BB_IRREDUCIBLE_LOOP;
+}
+
+/* Runs CALLBACK for all edges in G. */
+
+static void
+for_each_edge (struct graph *g,
+ void (callback) (struct graph *, struct edge *))
+{
+ struct edge *e;
+ int i;
+
+ for (i = 0; i < g->n_vertices; i++)
+ for (e = g->vertices[i].succ; e; e = e->succ_next)
+ callback (g, e);
+}
+
+/* Releases the memory occupied by G. */
+
+static void
+free_graph (struct graph *g)
+{
+ struct edge *e, *n;
+ int i;
+
+ for (i = 0; i < g->n_vertices; i++)
+ for (e = g->vertices[i].succ; e; e = n)
+ {
+ n = e->succ_next;
+ free (e);
+ }
+ free (g->vertices);
+ free (g);
+}
+
/* Marks blocks and edges that are part of non-recognized loops; i.e. we
throw away all latch edges and mark blocks inside any remaining cycle.
Everything is a bit complicated due to fact we do not want to do this
for parts of cycles that only "pass" through some loop -- i.e. for
each cycle, we want to mark blocks that belong directly to innermost
- loop containing the whole cycle. */
+ loop containing the whole cycle.
+
+ LOOPS is the loop tree. */
+
+#define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
+#define BB_REPR(BB) ((BB)->index + 1)
+
void
-mark_irreducible_loops (loops)
- struct loops *loops;
+mark_irreducible_loops (struct loops *loops)
{
- int *dfs_in, *closed, *mr, *mri, *n_edges, *stack;
- unsigned i;
- edge **edges, e;
- edge *estack;
basic_block act;
- int stack_top, tick, depth;
+ edge e;
+ int i, src, dest;
+ struct graph *g;
+ int *queue1 = xmalloc ((last_basic_block + loops->num) * sizeof (int));
+ int *queue2 = xmalloc ((last_basic_block + loops->num) * sizeof (int));
+ int nq, depth;
struct loop *cloop;
/* Reset the flags. */
e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
}
- /* The first last_basic_block + 1 entries are for real blocks (including
- entry); then we have loops->num - 1 fake blocks for loops to that we
- assign edges leading from loops (fake loop 0 is not interesting). */
- dfs_in = xmalloc ((last_basic_block + loops->num) * sizeof (int));
- closed = xmalloc ((last_basic_block + loops->num) * sizeof (int));
- mr = xmalloc ((last_basic_block + loops->num) * sizeof (int));
- mri = xmalloc ((last_basic_block + loops->num) * sizeof (int));
- n_edges = xmalloc ((last_basic_block + loops->num) * sizeof (int));
- edges = xmalloc ((last_basic_block + loops->num) * sizeof (edge *));
- stack = xmalloc ((n_basic_blocks + loops->num) * sizeof (int));
- estack = xmalloc ((n_basic_blocks + loops->num) * sizeof (edge));
-
/* Create the edge lists. */
- for (i = 0; i < last_basic_block + loops->num; i++)
- n_edges[i] = 0;
+ g = new_graph (last_basic_block + loops->num);
+
FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
for (e = act->succ; e; e = e->succ_next)
{
/* Ignore edges to exit. */
if (e->dest == EXIT_BLOCK_PTR)
continue;
+
/* And latch edges. */
if (e->dest->loop_father->header == e->dest
&& e->dest->loop_father->latch == act)
continue;
+
/* Edges inside a single loop should be left where they are. Edges
to subloop headers should lead to representative of the subloop,
- but from the same place. */
- if (act->loop_father == e->dest->loop_father
- || act->loop_father == e->dest->loop_father->outer)
- {
- n_edges[act->index + 1]++;
- continue;
- }
- /* Edges exiting loops remain. They should lead from representative
+ but from the same place.
+
+ Edges exiting loops should lead from representative
of the son of nearest common ancestor of the loops in that
act lays. */
- depth = find_common_loop (act->loop_father, e->dest->loop_father)->depth + 1;
- if (depth == act->loop_father->depth)
- cloop = act->loop_father;
- else
- cloop = act->loop_father->pred[depth];
- n_edges[cloop->num + last_basic_block]++;
- }
- for (i = 0; i < last_basic_block + loops->num; i++)
- {
- edges[i] = xmalloc (n_edges[i] * sizeof (edge));
- n_edges[i] = 0;
- }
+ src = BB_REPR (act);
+ dest = BB_REPR (e->dest);
- FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
- for (e = act->succ; e; e = e->succ_next)
- {
- if (e->dest == EXIT_BLOCK_PTR)
- continue;
- if (e->dest->loop_father->header == e->dest
- && e->dest->loop_father->latch == act)
- continue;
- if (act->loop_father == e->dest->loop_father
- || act->loop_father == e->dest->loop_father->outer)
+ if (e->dest->loop_father->header == e->dest)
+ dest = LOOP_REPR (e->dest->loop_father);
+
+ if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
{
- edges[act->index + 1][n_edges[act->index + 1]++] = e;
- continue;
+ depth = find_common_loop (act->loop_father,
+ e->dest->loop_father)->depth + 1;
+ if (depth == act->loop_father->depth)
+ cloop = act->loop_father;
+ else
+ cloop = act->loop_father->pred[depth];
+
+ src = LOOP_REPR (cloop);
}
- depth = find_common_loop (act->loop_father, e->dest->loop_father)->depth + 1;
- if (depth == act->loop_father->depth)
- cloop = act->loop_father;
- else
- cloop = act->loop_father->pred[depth];
- i = cloop->num + last_basic_block;
- edges[i][n_edges[i]++] = e;
+
+ add_edge (g, src, dest, e);
}
- /* Compute dfs numbering, starting from loop headers, and mark found
- loops.*/
- tick = 0;
- for (i = 0; i < last_basic_block + loops->num; i++)
+ /* Find the strongly connected components. Use the algorithm of Tarjan --
+ first determine the postorder dfs numbering in reversed graph, then
+ run the dfs on the original graph in the order given by decreasing
+ numbers assigned by the previous pass. */
+ nq = 0;
+ FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
{
- dfs_in[i] = -1;
- closed[i] = 0;
- mr[i] = last_basic_block + loops->num;
- mri[i] = -1;
+ queue1[nq++] = BB_REPR (act);
}
-
- stack_top = 0;
- for (i = 0; i < loops->num; i++)
+ for (i = 1; i < (int) loops->num; i++)
if (loops->parray[i])
- {
- stack[stack_top] = loops->parray[i]->header->index + 1;
- estack[stack_top] = NULL;
- stack_top++;
- }
+ queue1[nq++] = LOOP_REPR (loops->parray[i]);
+ dfs (g, queue1, nq, queue2, false);
+ for (i = 0; i < nq; i++)
+ queue1[i] = queue2[nq - i - 1];
+ dfs (g, queue1, nq, NULL, true);
- while (stack_top)
- {
- int idx, sidx;
+ /* Mark the irreducible loops. */
+ for_each_edge (g, check_irred);
- idx = stack[stack_top - 1];
- if (dfs_in[idx] < 0)
- dfs_in[idx] = tick++;
+ free_graph (g);
+ free (queue1);
+ free (queue2);
- while (n_edges[idx])
- {
- e = edges[idx][--n_edges[idx]];
- sidx = e->dest->loop_father->header == e->dest
- ? e->dest->loop_father->num + last_basic_block
- : e->dest->index + 1;
- if (closed[sidx])
- {
- if (!closed[mri[sidx]])
- {
- if (mr[sidx] < mr[idx])
- {
- mr[idx] = mr[sidx];
- mri[idx] = mri[sidx];
- }
-
- if (mr[sidx] <= dfs_in[idx])
- e->flags |= EDGE_IRREDUCIBLE_LOOP;
- }
- continue;
- }
- if (dfs_in[sidx] < 0)
- {
- stack[stack_top] = sidx;
- estack[stack_top] = e;
- stack_top++;
- goto next;
- }
- if (dfs_in[sidx] < mr[idx])
- {
- mr[idx] = dfs_in[sidx];
- mri[idx] = sidx;
- }
- e->flags |= EDGE_IRREDUCIBLE_LOOP;
- }
-
- /* Return back. */
- closed[idx] = 1;
- e = estack[stack_top - 1];
- stack_top--;
- if (e)
- {
- /* Propagate information back. */
- sidx = stack[stack_top - 1];
- if (mr[sidx] > mr[idx])
- {
- mr[sidx] = mr[idx];
- mri[sidx] = mri[idx];
- }
- if (mr[idx] <= dfs_in[sidx])
- e->flags |= EDGE_IRREDUCIBLE_LOOP;
- }
- /* Mark the block if relevant. */
- if (idx && idx <= last_basic_block && mr[idx] <= dfs_in[idx])
- BASIC_BLOCK (idx - 1)->flags |= BB_IRREDUCIBLE_LOOP;
-next:;
- }
-
- free (stack);
- free (estack);
- free (dfs_in);
- free (closed);
- free (mr);
- free (mri);
- for (i = 0; i < last_basic_block + loops->num; i++)
- free (edges[i]);
- free (edges);
- free (n_edges);
loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
}
/* Counts number of insns inside LOOP. */
int
-num_loop_insns (loop)
- struct loop *loop;
+num_loop_insns (struct loop *loop)
{
basic_block *bbs, bb;
unsigned i, ninsns = 0;
{
bb = bbs[i];
ninsns++;
- for (insn = bb->head; insn != bb->end; insn = NEXT_INSN (insn))
+ for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
if (INSN_P (insn))
ninsns++;
}
free(bbs);
-
+
return ninsns;
}
/* Counts number of insns executed on average per iteration LOOP. */
int
-average_num_loop_insns (loop)
- struct loop *loop;
+average_num_loop_insns (struct loop *loop)
{
basic_block *bbs, bb;
unsigned i, binsns, ninsns, ratio;
bb = bbs[i];
binsns = 1;
- for (insn = bb->head; insn != bb->end; insn = NEXT_INSN (insn))
+ for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
if (INSN_P (insn))
binsns++;
ninsns += binsns * ratio;
}
free(bbs);
-
+
ninsns /= BB_FREQ_MAX;
if (!ninsns)
ninsns = 1; /* To avoid division by zero. */
Compute upper bound on number of iterations in case they do not fit integer
to help loop peeling heuristics. Use exact counts if at all possible. */
unsigned
-expected_loop_iterations (loop)
- const struct loop *loop;
+expected_loop_iterations (const struct loop *loop)
{
edge e;
OSDN Git Service
