#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
+#include "obstack.h"
#include "basic-block.h"
#include "cfgloop.h"
#include "expr.h"
/* Generates a subreg to get the least significant part of EXPR (in mode
INNER_MODE) to OUTER_MODE. */
-static rtx
+rtx
lowpart_subreg (enum machine_mode outer_mode, rtx expr,
enum machine_mode inner_mode)
{
return iv->base != NULL_RTX;
}
+/* Checks whether definition of register REG in INSN a basic induction
+ variable. IV analysis must have been initialized (via a call to
+ iv_analysis_loop_init) for this function to produce a result. */
+
+bool
+biv_p (rtx insn, rtx reg)
+{
+ struct rtx_iv iv;
+
+ if (!REG_P (reg))
+ return false;
+
+ if (last_def[REGNO (reg)] != insn)
+ return false;
+
+ return iv_analyze_biv (reg, &iv);
+}
+
/* Calculates value of IV at ITERATION-th iteration. */
rtx
rtx head, tail, insn;
rtx neutral, aggr;
regset altered;
- regset_head altered_head;
edge e;
if (!*expr)
if (e->src == ENTRY_BLOCK_PTR)
return;
- altered = INITIALIZE_REG_SET (altered_head);
+ altered = ALLOC_REG_SET (®_obstack);
while (1)
{
+ basic_block tmp_bb;
+
insn = BB_END (e->src);
if (any_condjump_p (insn))
{
}
}
- e = e->src->pred;
- if (e->pred_next
+ /* This is a bit subtle. Store away e->src in tmp_bb, since we
+ modify `e' and this can invalidate the subsequent count of
+ e->src's predecessors by looking at the wrong block. */
+ tmp_bb = e->src;
+ e = EDGE_PRED (tmp_bb, 0);
+ if (EDGE_COUNT (tmp_bb->preds) > 1
|| e->src == ENTRY_BLOCK_PTR)
break;
}
the result into DESC. Very similar to determine_number_of_iterations
(basically its rtl version), complicated by things like subregs. */
-void
+static void
iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
struct niter_desc *desc)
{
enum machine_mode mode, comp_mode;
rtx mmin, mmax, mode_mmin, mode_mmax;
unsigned HOST_WIDEST_INT s, size, d, inv;
- HOST_WIDEST_INT up, down, inc;
+ HOST_WIDEST_INT up, down, inc, step_val;
int was_sharp = false;
rtx old_niter;
+ bool step_is_pow2;
/* The meaning of these assumptions is this:
if !assumptions
if (iv0.step == const0_rtx && iv1.step == const0_rtx)
goto fail;
- /* Ignore loops of while (i-- < 10) type. */
- if (cond != NE
- && (INTVAL (iv0.step) < 0 || INTVAL (iv1.step) > 0))
- goto fail;
+ if (cond != NE)
+ {
+ if (iv0.step == const0_rtx)
+ step_val = -INTVAL (iv1.step);
+ else
+ step_val = INTVAL (iv0.step);
+
+ /* Ignore loops of while (i-- < 10) type. */
+ if (step_val < 0)
+ goto fail;
+
+ step_is_pow2 = !(step_val & (step_val - 1));
+ }
+ else
+ {
+ /* We do not care about whether the step is power of two in this
+ case. */
+ step_is_pow2 = false;
+ step_val = 0;
+ }
/* Some more condition normalization. We must record some assumptions
due to overflows. */
/* If the step is a power of two and the final value we have
computed overflows, the cycle is infinite. Otherwise it
is nontrivial to compute the number of iterations. */
- s = INTVAL (step);
- if ((s & (s - 1)) == 0)
+ if (step_is_pow2)
desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
desc->infinite);
else
tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
bound = simplify_gen_binary (MINUS, mode, mode_mmax,
- lowpart_subreg (mode, step, comp_mode));
- assumption = simplify_gen_relational (cond, SImode, mode,
- tmp1, bound);
- desc->assumptions =
- alloc_EXPR_LIST (0, assumption, desc->assumptions);
+ lowpart_subreg (mode, step,
+ comp_mode));
+ if (step_is_pow2)
+ {
+ rtx t0, t1;
+
+ /* If s is power of 2, we know that the loop is infinite if
+ a % s <= b % s and b + s overflows. */
+ assumption = simplify_gen_relational (reverse_condition (cond),
+ SImode, mode,
+ tmp1, bound);
+
+ t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
+ t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
+ tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
+ assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
+ desc->infinite =
+ alloc_EXPR_LIST (0, assumption, desc->infinite);
+ }
+ else
+ {
+ assumption = simplify_gen_relational (cond, SImode, mode,
+ tmp1, bound);
+ desc->assumptions =
+ alloc_EXPR_LIST (0, assumption, desc->assumptions);
+ }
tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
tmp = lowpart_subreg (mode, tmp, comp_mode);
bound = simplify_gen_binary (MINUS, mode, mode_mmin,
lowpart_subreg (mode, step, comp_mode));
- assumption = simplify_gen_relational (cond, SImode, mode,
- bound, tmp0);
- desc->assumptions =
- alloc_EXPR_LIST (0, assumption, desc->assumptions);
+ if (step_is_pow2)
+ {
+ rtx t0, t1;
+
+ /* If s is power of 2, we know that the loop is infinite if
+ a % s <= b % s and a - s overflows. */
+ assumption = simplify_gen_relational (reverse_condition (cond),
+ SImode, mode,
+ bound, tmp0);
+
+ t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
+ t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
+ tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
+ assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
+ desc->infinite =
+ alloc_EXPR_LIST (0, assumption, desc->infinite);
+ }
+ else
+ {
+ assumption = simplify_gen_relational (cond, SImode, mode,
+ bound, tmp0);
+ desc->assumptions =
+ alloc_EXPR_LIST (0, assumption, desc->assumptions);
+ }
tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
tmp = lowpart_subreg (mode, tmp, comp_mode);
{
basic_block exit_bb;
rtx condition, at;
- edge ei;
+ edge ein;
exit_bb = e->src;
desc->simple_p = false;
if (!any_condjump_p (BB_END (exit_bb)))
return;
- ei = exit_bb->succ;
- if (ei == e)
- ei = ei->succ_next;
+ ein = EDGE_SUCC (exit_bb, 0);
+ if (ein == e)
+ ein = EDGE_SUCC (exit_bb, 1);
desc->out_edge = e;
- desc->in_edge = ei;
+ desc->in_edge = ein;
/* Test whether the condition is suitable. */
- if (!(condition = get_condition (BB_END (ei->src), &at, false, false)))
+ if (!(condition = get_condition (BB_END (ein->src), &at, false, false)))
return;
- if (ei->flags & EDGE_FALLTHRU)
+ if (ein->flags & EDGE_FALLTHRU)
{
condition = reversed_condition (condition);
if (!condition)
edge e;
struct niter_desc act;
bool any = false;
+ edge_iterator ei;
desc->simple_p = false;
body = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
{
- for (e = body[i]->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, body[i]->succs)
{
if (flow_bb_inside_loop_p (loop, e->dest))
continue;
OSDN Git Service
