This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] Remove (now unused) old simple loop analysis
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 17 Feb 2004 20:37:54 +0100
- Subject: [patch] Remove (now unused) old simple loop analysis
Hello,
this patch removes the old simple loop analysis that became unused.
Zdenek
* cfgloop.h (struct loop_desc): Removed.
(struct loop): Fields simple, desc and has_desc removed.
(simple_loop_p, count_loop_iterations): Declaration removed.
* cfgloopanal.c (struct unmark_altered_insn_data): Removed.
(unmark_altered, blocks_invariant_registers, unmark_altered_insn
blocks_single_set_registers, invariant_rtx_wrto_regs_p_helper,
invariant_rtx_wrto_regs_p, test_for_iteration, constant_iterations,
simple_loop_exit_p, variable_initial_value, variable_initial_values,
simple_condition_p, simple_increment, count_strange_loop_iterations,
inverse, fits_in_mode_p, simple_loop_p, count_loop_iterations):
Removed.
* loop-iv.c (check_simple_exit, find_simple_exit): Update comments.
Index: cfgloop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.h,v
retrieving revision 1.13
diff -c -3 -p -r1.13 cfgloop.h
*** cfgloop.h 17 Feb 2004 16:41:43 -0000 1.13
--- cfgloop.h 17 Feb 2004 16:55:42 -0000
*************** struct lpt_decision
*** 36,64 ****
unsigned times;
};
- /* Description of loop for simple loop unrolling. */
- struct loop_desc
- {
- int postincr; /* 1 if increment/decrement is done after loop exit condition. */
- rtx stride; /* Value added to VAR in each iteration. */
- rtx var; /* Loop control variable. */
- enum machine_mode inner_mode;
- /* The mode from that it is extended. */
- enum rtx_code extend; /* With this extend. */
- rtx var_alts; /* List of definitions of its initial value. */
- rtx lim; /* Expression var is compared with. */
- rtx lim_alts; /* List of definitions of its initial value. */
- bool const_iter; /* True if it iterates constant number of times. */
- unsigned HOST_WIDE_INT niter;
- /* Number of iterations if it is constant. */
- bool may_be_zero; /* If we cannot determine that the first iteration will pass. */
- enum rtx_code cond; /* Exit condition. */
- int neg; /* Set to 1 if loop ends when condition is satisfied. */
- edge out_edge; /* The exit edge. */
- edge in_edge; /* And the other one. */
- int n_branches; /* Number of branches inside the loop. */
- };
-
/* Structure to hold information for each natural loop. */
struct loop
{
--- 36,41 ----
*************** struct loop
*** 77,87 ****
/* For loop unrolling/peeling decision. */
struct lpt_decision lpt_decision;
- /* Simple loop description. */
- int simple;
- struct loop_desc desc;
- int has_desc;
-
/* Number of loop insns. */
unsigned ninsns;
--- 54,59 ----
*************** extern void force_single_succ_latches (s
*** 305,312 ****
extern void verify_loop_structure (struct loops *);
/* Loop analysis. */
- extern bool simple_loop_p (struct loop *, struct loop_desc *);
- extern rtx count_loop_iterations (struct loop_desc *, rtx, rtx);
extern bool just_once_each_iteration_p (struct loop *, basic_block);
extern unsigned expected_loop_iterations (const struct loop *);
--- 277,282 ----
*************** struct rtx_iv
*** 370,377 ****
unsigned first_special : 1;
};
! /* This should replace struct loop_desc. We keep this just so that we are
! able to compare the results. */
struct niter_desc
{
--- 340,347 ----
unsigned first_special : 1;
};
! /* The description of an exit from the loop and of the number of iterations
! till we take the exit. */
struct niter_desc
{
Index: cfgloopanal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloopanal.c,v
retrieving revision 1.19
diff -c -3 -p -r1.19 cfgloopanal.c
*** cfgloopanal.c 13 Feb 2004 11:19:09 -0000 1.19
--- cfgloopanal.c 17 Feb 2004 16:55:42 -0000
*************** Software Foundation, 59 Temple Place - S
*** 29,76 ****
#include "expr.h"
#include "output.h"
- struct unmark_altered_insn_data;
- 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 (struct loop *loop, basic_block bb)
{
--- 29,36 ----
#include "expr.h"
#include "output.h"
/* Checks whether BB is executed exactly once in each LOOP iteration. */
+
bool
just_once_each_iteration_p (struct loop *loop, basic_block bb)
{
*************** just_once_each_iteration_p (struct loop
*** 87,1114 ****
return false;
return true;
- }
-
-
- /* Unmarks modified registers; helper to blocks_invariant_registers. */
- static void
- unmark_altered (rtx what, rtx by ATTRIBUTE_UNUSED, regset regs)
- {
- if (GET_CODE (what) == SUBREG)
- what = SUBREG_REG (what);
- if (!REG_P (what))
- return;
- CLEAR_REGNO_REG_SET (regs, REGNO (what));
- }
-
- /* Marks registers that are invariant inside blocks BBS. */
- static void
- 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 = BB_HEAD (bbs[i]);
- insn != NEXT_INSN (BB_END (bbs[i]));
- insn = NEXT_INSN (insn))
- if (INSN_P (insn))
- note_stores (PATTERN (insn),
- (void (*) (rtx, rtx, void *)) unmark_altered,
- regs);
- }
-
- /* Unmarks modified registers; helper to blocks_single_set_registers. */
- struct unmark_altered_insn_data
- {
- rtx *regs;
- rtx insn;
- };
-
- static void
- unmark_altered_insn (rtx what, rtx by ATTRIBUTE_UNUSED,
- struct unmark_altered_insn_data *data)
- {
- int rn;
-
- if (GET_CODE (what) == SUBREG)
- what = SUBREG_REG (what);
- if (!REG_P (what))
- return;
- rn = REGNO (what);
- if (data->regs[rn] == data->insn)
- return;
- data->regs[rn] = NULL;
- }
-
- /* Marks registers that have just single simple set in BBS; the relevant
- insn is returned in REGS. */
- static void
- blocks_single_set_registers (basic_block *bbs, int nbbs, rtx *regs)
- {
- rtx insn;
- int i;
- struct unmark_altered_insn_data data;
-
- for (i = 0; i < max_reg_num (); i++)
- regs[i] = NULL;
-
- for (i = 0; i < nbbs; i++)
- for (insn = BB_HEAD (bbs[i]);
- insn != NEXT_INSN (BB_END (bbs[i]));
- insn = NEXT_INSN (insn))
- {
- rtx set = single_set (insn);
- if (!set)
- continue;
- if (!REG_P (SET_DEST (set)))
- continue;
- regs[REGNO (SET_DEST (set))] = insn;
- }
-
- data.regs = regs;
- for (i = 0; i < nbbs; i++)
- 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 (*) (rtx, rtx, void *)) unmark_altered_insn,
- &data);
- }
- }
-
- /* Helper for invariant_rtx_wrto_regs_p. */
- static int
- invariant_rtx_wrto_regs_p_helper (rtx *expr, regset invariant_regs)
- {
- switch (GET_CODE (*expr))
- {
- case CC0:
- case PC:
- case UNSPEC_VOLATILE:
- return 1;
-
- case CONST_INT:
- case CONST_DOUBLE:
- case CONST:
- case SYMBOL_REF:
- case LABEL_REF:
- return 0;
-
- case ASM_OPERANDS:
- return MEM_VOLATILE_P (*expr);
-
- case MEM:
- /* If the memory is not constant, assume it is modified. If it is
- constant, we still have to check the address. */
- return !RTX_UNCHANGING_P (*expr);
-
- case REG:
- return !REGNO_REG_SET_P (invariant_regs, REGNO (*expr));
-
- default:
- return 0;
- }
- }
-
- /* Checks that EXPR is invariant provided that INVARIANT_REGS are invariant. */
- static bool
- 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);
- }
-
- /* 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 (struct loop *loop ATTRIBUTE_UNUSED, rtx condition,
- regset invariant_regs, struct loop_desc *desc)
- {
- rtx op0, op1;
-
- /* 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_rtx_wrto_regs_p (op0, invariant_regs))
- {
- /* And the other one must be a register. */
- if (!REG_P (op1))
- return false;
- desc->var = op1;
- desc->lim = op0;
-
- desc->cond = swap_condition (GET_CODE (condition));
- if (desc->cond == UNKNOWN)
- return false;
- return true;
- }
-
- /* Check the other operand. */
- if (!invariant_rtx_wrto_regs_p (op1, invariant_regs))
- return false;
- if (!REG_P (op0))
- return false;
-
- desc->var = op0;
- desc->lim = 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 (struct loop *loop, rtx *simple_increment_regs,
- struct loop_desc *desc)
- {
- 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)];
- if (!mod_insn)
- return NULL;
- mod_bb = BLOCK_FOR_INSN (mod_insn);
-
- /* Check that it is executed exactly once each iteration. */
- if (!just_once_each_iteration_p (loop, mod_bb))
- return NULL;
-
- /* mod_insn must be a simple increment/decrement. */
- set = single_set (mod_insn);
- if (!set)
- abort ();
- if (!rtx_equal_p (SET_DEST (set), desc->var))
- abort ();
-
- 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))
- 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 invariant
- wrto INVARIANT_REGS. If SET_INSN is not NULL, insn in that var is set is
- placed here. INNER_MODE is mode in that induction variable VAR iterates. */
- static rtx
- 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 (bb); insn = PREV_INSN (insn))
- {
- if (INSN_P (insn))
- note_stores (PATTERN (insn),
- (void (*) (rtx, rtx, void *)) unmark_altered,
- invariant_regs);
- if (modified_between_p (var, PREV_INSN (insn), NEXT_INSN (insn)))
- break;
- }
-
- 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;
- 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 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 ret;
-
- 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 (bb);
- }
-
- return NULL;
- }
-
- /* 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 (edge e, rtx var, enum machine_mode inner_mode)
- {
- rtx set_insn, list;
- regset invariant_regs;
- regset_head invariant_regs_head;
- int i;
-
- invariant_regs = INITIALIZE_REG_SET (invariant_regs_head);
- for (i = 0; i < max_reg_num (); i++)
- SET_REGNO_REG_SET (invariant_regs, i);
-
- list = alloc_EXPR_LIST (0, copy_rtx (var), NULL);
-
- if (e->src == ENTRY_BLOCK_PTR)
- return list;
-
- set_insn = BB_END (e->src);
- while (REG_P (var)
- && (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);
- return list;
- }
-
- /* Counts constant number of iterations of the loop described by DESC;
- returns false if impossible. */
- static bool
- constant_iterations (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);
-
- /* It would make a little sense to check every with every when we
- know that all but the first alternative are simply registers. */
- for (ainit = desc->var_alts; ainit; ainit = XEXP (ainit, 1))
- {
- alim = XEXP (desc->lim_alts, 0);
- if (!(expr = count_loop_iterations (desc, XEXP (ainit, 0), alim)))
- continue;
- if (GET_CODE (expr) == CONST_INT)
- {
- *niter = INTVAL (expr);
- return true;
- }
- }
- for (alim = XEXP (desc->lim_alts, 1); alim; alim = XEXP (alim, 1))
- {
- ainit = XEXP (desc->var_alts, 0);
- if (!(expr = count_loop_iterations (desc, ainit, XEXP (alim, 0))))
- continue;
- if (GET_CODE (expr) == CONST_INT)
- {
- *niter = INTVAL (expr);
- return true;
- }
- }
-
- 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).
-
- 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 (struct loop_desc *desc, rtx init, rtx lim)
- {
- enum rtx_code cond = desc->cond;
- rtx stride = desc->stride;
- 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 (mode))
- return NULL;
-
- init = copy_rtx (init ? init : desc->var);
- lim = copy_rtx (lim ? lim : desc->lim);
-
- /* Ensure that we always handle the condition to stay inside loop. */
- 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)
- {
- /* Handle strange tests specially. */
- if (cond == EQ || cond == GE || cond == GT || cond == GEU
- || cond == GTU)
- return count_strange_loop_iterations (init, lim, cond, desc->postincr,
- stride, mode, desc->inner_mode);
- exp = simplify_gen_binary (MINUS, mode, lim, init);
- }
- else
- {
- if (cond == EQ || cond == LE || cond == LT || cond == LEU
- || cond == LTU)
- 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, mode, exp, stride);
-
- /* Determine delta caused by exit condition. */
- switch (cond)
- {
- case NE:
- /* 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 GTU:
- break;
- case LE:
- case GE:
- case LEU:
- case GEU:
- exp = simplify_gen_binary (PLUS, mode, exp, const1_rtx);
- break;
- default:
- abort ();
- }
-
- 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, 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
- 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, 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, mode, exp, stride);
- if (mod != const0_rtx)
- exp = simplify_gen_binary (PLUS, mode, 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 (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 condition. */
- 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 "
- HOST_WIDE_INT_PRINT_UNSIGNED "th iteration: ", iter);
- print_simple_rtl (rtl_dump_file, exp);
- fprintf (rtl_dump_file, "\n");
- }
- return exp;
- }
-
-
- /* Tests whether exit at EXIT_EDGE from LOOP is simple. Returns simple loop
- 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 (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;
- 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 (at least) once during any iteration. */
- if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
- return false;
-
- /* It must end in a simple conditional jump. */
- if (!any_condjump_p (BB_END (exit_bb)))
- return false;
-
- ei = exit_bb->succ;
- if (ei == exit_edge)
- ei = ei->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 (BB_END (exit_bb), NULL, false)))
- return false;
-
- if (!simple_condition_p (loop, condition, invariant_regs, 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 (loop, single_set_regs, desc)))
- return false;
-
- /* OK, it is simple loop. Now just fill in remaining info. */
- 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->inner_mode);
- desc->lim_alts = variable_initial_values (e, desc->lim, desc->inner_mode);
-
- /* Number of iterations. */
- 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 (struct loop *loop, struct loop_desc *desc)
- {
- unsigned i;
- basic_block *body;
- edge e;
- struct loop_desc act;
- bool any = false;
- regset invariant_regs;
- 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);
- single_set_regs = xmalloc (max_reg_num () * sizeof (rtx));
-
- blocks_invariant_registers (body, loop->num_nodes, invariant_regs);
- blocks_single_set_registers (body, loop->num_nodes, single_set_regs);
-
- n_branches = 0;
- 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 (loop, e,
- invariant_regs, single_set_regs, &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;
- }
-
- if (body[i]->succ && body[i]->succ->succ_next)
- n_branches++;
- }
- desc->n_branches = n_branches;
-
- if (rtl_dump_file && any)
- {
- 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));
-
- fprintf (rtl_dump_file, "; Number of branches:");
- fprintf (rtl_dump_file, "%d\n", desc->n_branches);
-
- fputc ('\n', rtl_dump_file);
- }
-
- free (body);
- FREE_REG_SET (invariant_regs);
- free (single_set_regs);
- return any;
}
/* Structure representing edge of a graph. */
--- 47,52 ----
Index: loop-iv.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop-iv.c,v
retrieving revision 2.1
diff -c -3 -p -r2.1 loop-iv.c
*** loop-iv.c 17 Feb 2004 16:41:43 -0000 2.1
--- loop-iv.c 17 Feb 2004 16:55:42 -0000
*************** zero_iter:
*** 2306,2312 ****
}
/* Checks whether E is a simple exit from LOOP and stores its description
! into DESC. TODO Should replace cfgloopanal.c:simple_loop_exit_p. */
static void
check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
--- 2306,2312 ----
}
/* Checks whether E is a simple exit from LOOP and stores its description
! into DESC. */
static void
check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
*************** check_simple_exit (struct loop *loop, ed
*** 2353,2360 ****
iv_number_of_iterations (loop, at, condition, desc);
}
! /* Finds a simple exit of LOOP and stores its description into DESC.
! TODO Should replace cfgloopanal.c:simple_loop_p. */
void
find_simple_exit (struct loop *loop, struct niter_desc *desc)
--- 2353,2359 ----
iv_number_of_iterations (loop, at, condition, desc);
}
! /* Finds a simple exit of LOOP and stores its description into DESC. */
void
find_simple_exit (struct loop *loop, struct niter_desc *desc)