- 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 = bbs[i]->head;
- insn != NEXT_INSN (bbs[i]->end);
- 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 = bbs[i]->head;
- insn != NEXT_INSN (bbs[i]->end);
- 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 loops *loops, struct loop *loop,
- rtx *simple_increment_regs, struct loop_desc *desc)
-{
- rtx mod_insn, set, set_src, set_add;
- basic_block mod_bb;
-
- /* 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 (loops, 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);
- 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. */
-static rtx
-variable_initial_value (rtx insn, regset invariant_regs, 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 (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)
- {
- /* 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 (!invariant_rtx_wrto_regs_p (val, invariant_regs))
- 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 (edge e, rtx var)
-{
- 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 = e->src->end;
- while (REG_P (var)
- && (var = variable_initial_value (set_insn, invariant_regs, var, &set_insn)))
- 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 and iterates in 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)
-{
- rtx rqmt, n_to_wrap, before_wrap, after_wrap;
- rtx mode_min, mode_max;
- int size;
-
- 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);
-}
-
-/* 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;
-
- /* 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;
-
- 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);
-
- /* 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, GET_MODE (desc->var));
- exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
- lim, init);
- }
- else
- {
- /* Bypass nonsensical tests. */
- if (cond == EQ || cond == LE || cond == LT || cond == LEU
- || cond == LTU)
- return count_strange_loop_iterations (init, lim, cond, desc->postincr,
- stride, GET_MODE (desc->var));
- 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 easily. */
- 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 (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 loops *loops, 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 (loops->cfg.dom, loop->latch, exit_bb))
- return false;
-
- /* It must end in a simple conditional jump. */
- if (!any_condjump_p (exit_bb->end))
- return false;