-/* Checks whether CONDITION is a simple comparison in that one of operands
- is register and the other one is invariant in the LOOP. Fills var, lim
- and cond fields in DESC. */
-static bool
-simple_condition_p (loop, condition, invariant_regs, desc)
- 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 (loops, loop, simple_increment_regs, desc)
- 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 (insn, invariant_regs, var, set_insn)
- 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 (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,
- invariant_regs);
- }
-
- 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 (e, var)
- 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 (desc, niter, may_be_zero)
- struct loop_desc *desc;
- unsigned HOST_WIDE_INT *niter;
- bool *may_be_zero;
-{
- rtx test, expr;
- rtx ainit, alim;
-
- test = test_for_iteration (desc, 0);
- if (test == const0_rtx)
- {
- *niter = 0;
- *may_be_zero = false;
- return true;
- }
-
- *may_be_zero = (test != const_true_rtx);
-
- /* 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)))
- abort ();
- 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))))
- abort ();
- if (GET_CODE (expr) == CONST_INT)
- {
- *niter = INTVAL (expr);
- return true;
- }
- }
-
- 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 (desc, init, lim)
- 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)
- {
- /* Bypass nonsensical tests. */
- if (cond == EQ || cond == GE || cond == GT || cond == GEU
- || cond == GTU)
- return NULL;
- exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
- lim, init);
- }
- else
- {
- /* Bypass 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));
- }
-
- /* 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 (desc, iter)
- struct loop_desc *desc;
- unsigned HOST_WIDE_INT iter;
-{
- enum rtx_code cond = desc->cond;
- rtx exp = XEXP (desc->var_alts, 0);
- rtx addval;
-
- /* Give up on floating point modes and friends. It can be possible to do
- the job for constant loop bounds, but it is probably not worthwhile. */
- if (!INTEGRAL_MODE_P (GET_MODE (desc->var)))
- return NULL;
-
- /* Ensure that we always handle the condition to stay inside loop. */
- if (desc->neg)
- cond = reverse_condition (cond);
-
- /* Compute the value of induction variable. */
- addval = simplify_gen_binary (MULT, GET_MODE (desc->var),
- desc->stride,
- gen_int_mode (desc->postincr
- ? iter : iter + 1,
- GET_MODE (desc->var)));
- exp = simplify_gen_binary (PLUS, GET_MODE (desc->var), exp, addval);
- /* Test at given 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 ");
- fprintf (rtl_dump_file, HOST_WIDE_INT_PRINT_UNSIGNED, iter);
- fprintf (rtl_dump_file, "th iteration: ");
- 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 (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;
-{
- 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;
OSDN Git Service
