/* Rtl-level induction variable analysis.
- Copyright (C) 2004 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005 Free Software Foundation, Inc.
This file is part of GCC.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
/* This is just a very simplistic analysis of induction variables of the loop.
The major use is for determining the number of iterations of a loop for
interesting reg, it is now easy to find a reaching definition (there may be
only one).
- Induction variable is then simply analysed by walking the use-def
+ Induction variable is then simply analyzed by walking the use-def
chains.
Usage:
#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
+#include "obstack.h"
#include "basic-block.h"
#include "cfgloop.h"
#include "expr.h"
+#include "intl.h"
#include "output.h"
+#include "toplev.h"
/* The insn information. */
return;
}
- if (iv->step == const0_rtx)
- {
- fprintf (file, "invariant ");
- print_rtl (file, iv->base);
- return;
- }
+ if (iv->step == const0_rtx
+ && !iv->first_special)
+ fprintf (file, "invariant ");
print_rtl (file, iv->base);
- fprintf (file, " + ");
- print_rtl (file, iv->step);
- fprintf (file, " * iteration");
+ if (iv->step != const0_rtx)
+ {
+ fprintf (file, " + ");
+ print_rtl (file, iv->step);
+ fprintf (file, " * iteration");
+ }
fprintf (file, " (in %s)", GET_MODE_NAME (iv->mode));
if (iv->mode != iv->extend_mode)
/* 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)
{
case PLUS:
case MINUS:
case MULT:
+ case ASHIFT:
op0 = XEXP (rhs, 0);
op1 = XEXP (rhs, 1);
&& !CONSTANT_P (op1))
return false;
+ if (GET_CODE (rhs) == ASHIFT
+ && CONSTANT_P (op0))
+ return false;
+
return true;
default:
unsigned regno, uid;
src = find_reg_equal_equiv_note (insn);
- if (!src)
+ if (src)
+ src = XEXP (src, 0);
+ else
src = SET_SRC (set);
if (!simple_set_p (SET_DEST (set), src))
iv->base = cst;
iv->step = const0_rtx;
iv->first_special = false;
- iv->extend = NIL;
+ iv->extend = UNKNOWN;
iv->extend_mode = iv->mode;
iv->delta = const0_rtx;
iv->mult = const1_rtx;
static bool
iv_subreg (struct rtx_iv *iv, enum machine_mode mode)
{
+ /* If iv is invariant, just calculate the new value. */
+ if (iv->step == const0_rtx
+ && !iv->first_special)
+ {
+ rtx val = get_iv_value (iv, const0_rtx);
+ val = lowpart_subreg (mode, val, iv->extend_mode);
+
+ iv->base = val;
+ iv->extend = UNKNOWN;
+ iv->mode = iv->extend_mode = mode;
+ iv->delta = const0_rtx;
+ iv->mult = const1_rtx;
+ return true;
+ }
+
if (iv->extend_mode == mode)
return true;
if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (iv->mode))
return false;
- iv->extend = NIL;
+ iv->extend = UNKNOWN;
iv->mode = mode;
iv->base = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
static bool
iv_extend (struct rtx_iv *iv, enum rtx_code extend, enum machine_mode mode)
{
+ /* If iv is invariant, just calculate the new value. */
+ if (iv->step == const0_rtx
+ && !iv->first_special)
+ {
+ rtx val = get_iv_value (iv, const0_rtx);
+ val = simplify_gen_unary (extend, mode, val, iv->extend_mode);
+
+ iv->base = val;
+ iv->extend = UNKNOWN;
+ iv->mode = iv->extend_mode = mode;
+ iv->delta = const0_rtx;
+ iv->mult = const1_rtx;
+ return true;
+ }
+
if (mode != iv->extend_mode)
return false;
- if (iv->extend != NIL
+ if (iv->extend != UNKNOWN
&& iv->extend != extend)
return false;
static bool
iv_neg (struct rtx_iv *iv)
{
- if (iv->extend == NIL)
+ if (iv->extend == UNKNOWN)
{
iv->base = simplify_gen_unary (NEG, iv->extend_mode,
iv->base, iv->extend_mode);
enum machine_mode mode;
rtx arg;
- /* Extend the constant to extend_mode of the other operand if neccesary. */
- if (iv0->extend == NIL
+ /* Extend the constant to extend_mode of the other operand if necessary. */
+ if (iv0->extend == UNKNOWN
&& iv0->mode == iv0->extend_mode
&& iv0->step == const0_rtx
&& GET_MODE_SIZE (iv0->extend_mode) < GET_MODE_SIZE (iv1->extend_mode))
iv0->base = simplify_gen_unary (ZERO_EXTEND, iv0->extend_mode,
iv0->base, iv0->mode);
}
- if (iv1->extend == NIL
+ if (iv1->extend == UNKNOWN
&& iv1->mode == iv1->extend_mode
&& iv1->step == const0_rtx
&& GET_MODE_SIZE (iv1->extend_mode) < GET_MODE_SIZE (iv0->extend_mode))
if (mode != iv1->extend_mode)
return false;
- if (iv0->extend == NIL && iv1->extend == NIL)
+ if (iv0->extend == UNKNOWN && iv1->extend == UNKNOWN)
{
if (iv0->mode != iv1->mode)
return false;
}
/* Handle addition of constant. */
- if (iv1->extend == NIL
+ if (iv1->extend == UNKNOWN
&& iv1->mode == mode
&& iv1->step == const0_rtx)
{
return true;
}
- if (iv0->extend == NIL
+ if (iv0->extend == UNKNOWN
&& iv0->mode == mode
&& iv0->step == const0_rtx)
{
&& GET_MODE (mby) != mode)
return false;
- if (iv->extend == NIL)
+ if (iv->extend == UNKNOWN)
{
iv->base = simplify_gen_binary (MULT, mode, iv->base, mby);
iv->step = simplify_gen_binary (MULT, mode, iv->step, mby);
return true;
}
+/* Evaluates shift of IV by constant CST. */
+
+static bool
+iv_shift (struct rtx_iv *iv, rtx mby)
+{
+ enum machine_mode mode = iv->extend_mode;
+
+ if (GET_MODE (mby) != VOIDmode
+ && GET_MODE (mby) != mode)
+ return false;
+
+ if (iv->extend == UNKNOWN)
+ {
+ iv->base = simplify_gen_binary (ASHIFT, mode, iv->base, mby);
+ iv->step = simplify_gen_binary (ASHIFT, mode, iv->step, mby);
+ }
+ else
+ {
+ iv->delta = simplify_gen_binary (ASHIFT, mode, iv->delta, mby);
+ iv->mult = simplify_gen_binary (ASHIFT, mode, iv->mult, mby);
+ }
+
+ return true;
+}
+
/* The recursive part of get_biv_step. Gets the value of the single value
defined in INSN wrto initial value of REG inside loop, in shape described
at get_biv_step. */
enum rtx_code *extend, enum machine_mode outer_mode,
rtx *outer_step)
{
- rtx set, lhs, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
+ rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
rtx next, nextr, def_insn, tmp;
enum rtx_code code;
set = single_set (insn);
rhs = find_reg_equal_equiv_note (insn);
- if (!rhs)
+ if (rhs)
+ rhs = XEXP (rhs, 0);
+ else
rhs = SET_SRC (set);
- lhs = SET_DEST (set);
code = GET_CODE (rhs);
switch (code)
return false;
*inner_step = const0_rtx;
- *extend = NIL;
+ *extend = UNKNOWN;
*inner_mode = outer_mode;
*outer_step = const0_rtx;
}
*inner_step = simplify_gen_binary (PLUS, outer_mode,
*inner_step, *outer_step);
*outer_step = const0_rtx;
- *extend = NIL;
+ *extend = UNKNOWN;
}
switch (code)
case SIGN_EXTEND:
case ZERO_EXTEND:
- if (GET_MODE (op0) != *inner_mode
- || *extend != NIL
- || *outer_step != const0_rtx)
- abort ();
+ gcc_assert (GET_MODE (op0) == *inner_mode
+ && *extend == UNKNOWN
+ && *outer_step == const0_rtx);
*extend = code;
break;
default:
- abort ();
+ gcc_unreachable ();
}
return true;
outer_step))
return false;
- if (*inner_mode != *outer_mode
- && *extend == NIL)
- abort ();
-
- if (*inner_mode == *outer_mode
- && *extend != NIL)
- abort ();
-
- if (*inner_mode == *outer_mode
- && *outer_step != const0_rtx)
- abort ();
+ gcc_assert ((*inner_mode == *outer_mode) != (*extend != UNKNOWN));
+ gcc_assert (*inner_mode != *outer_mode || *outer_step == const0_rtx);
return true;
}
if (dump_file)
{
- fprintf (dump_file, "Analysing ");
+ fprintf (dump_file, "Analyzing ");
print_rtl (dump_file, def);
fprintf (dump_file, " for bivness.\n");
}
return iv->base != NULL_RTX;
}
-/* Analyses operand OP of INSN and stores the result to *IV. */
+/* Analyzes operand OP of INSN and stores the result to *IV. */
static bool
iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv)
if (dump_file)
{
- fprintf (dump_file, "Analysing operand ");
+ fprintf (dump_file, "Analyzing operand ");
print_rtl (dump_file, op);
fprintf (dump_file, " of insn ");
print_rtl_single (dump_file, insn);
return iv_analyze (def_insn, op, iv);
}
-/* Analyses iv DEF defined in INSN and stores the result to *IV. */
+/* Analyzes iv DEF defined in INSN and stores the result to *IV. */
bool
iv_analyze (rtx insn, rtx def, struct rtx_iv *iv)
if (dump_file)
{
- fprintf (dump_file, "Analysing def of ");
+ fprintf (dump_file, "Analyzing def of ");
print_rtl (dump_file, def);
fprintf (dump_file, " in insn ");
print_rtl_single (dump_file, insn);
set = single_set (insn);
rhs = find_reg_equal_equiv_note (insn);
- if (!rhs)
+ if (rhs)
+ rhs = XEXP (rhs, 0);
+ else
rhs = SET_SRC (set);
code = GET_CODE (rhs);
mby = XEXP (rhs, 1);
if (!CONSTANT_P (mby))
{
- if (!CONSTANT_P (op0))
- abort ();
+ gcc_assert (CONSTANT_P (op0));
tmp = op0;
op0 = mby;
mby = tmp;
}
break;
-
+
+ case ASHIFT:
+ gcc_assert (!CONSTANT_P (XEXP (rhs, 0)));
+ op0 = XEXP (rhs, 0);
+ mby = XEXP (rhs, 1);
+ break;
+
default:
- abort ();
+ gcc_unreachable ();
}
amode = GET_MODE (rhs);
goto end;
break;
+ case ASHIFT:
+ if (!iv_shift (&iv0, mby))
+ goto end;
+ break;
+
default:
break;
}
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
/* We would need to generate some if_then_else patterns, and so far
it is not needed anywhere. */
- if (iv->first_special)
- abort ();
+ gcc_assert (!iv->first_special);
if (iv->step != const0_rtx && iteration != const0_rtx)
val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base,
val = lowpart_subreg (iv->mode, val, iv->extend_mode);
- if (iv->extend == NIL)
+ if (iv->extend == UNKNOWN)
return val;
val = simplify_gen_unary (iv->extend, iv->extend_mode, val, iv->mode);
}
}
- get_mode_bounds (desc->mode, desc->signed_p, &mmin, &mmax);
+ get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
nmax = INTVAL (mmax) - INTVAL (mmin);
if (GET_CODE (niter) == UDIV)
simplify_using_assignment (rtx insn, rtx *expr, regset altered)
{
rtx set = single_set (insn);
- rtx lhs, rhs;
+ rtx lhs = NULL_RTX, rhs;
bool ret = false;
if (set)
{
lhs = SET_DEST (set);
- if (GET_CODE (lhs) != REG
+ if (!REG_P (lhs)
|| altered_reg_used (&lhs, altered))
ret = true;
}
ret = true;
note_stores (PATTERN (insn), mark_altered, altered);
- if (GET_CODE (insn) == CALL_INSN)
+ if (CALL_P (insn))
{
int i;
return;
rhs = find_reg_equal_equiv_note (insn);
- if (!rhs)
+ if (rhs)
+ rhs = XEXP (rhs, 0);
+ else
rhs = SET_SRC (set);
if (!simple_rhs_p (rhs))
static bool
implies_p (rtx a, rtx b)
{
- rtx op0, op1, r;
+ rtx op0, op1, opb0, opb1, r;
+ enum machine_mode mode;
if (GET_CODE (a) == EQ)
{
}
}
+ /* A < B implies A + 1 <= B. */
+ if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
+ && (GET_CODE (b) == GE || GET_CODE (b) == LE))
+ {
+ op0 = XEXP (a, 0);
+ op1 = XEXP (a, 1);
+ opb0 = XEXP (b, 0);
+ opb1 = XEXP (b, 1);
+
+ if (GET_CODE (a) == GT)
+ {
+ r = op0;
+ op0 = op1;
+ op1 = r;
+ }
+
+ if (GET_CODE (b) == GE)
+ {
+ r = opb0;
+ opb0 = opb1;
+ opb1 = r;
+ }
+
+ mode = GET_MODE (op0);
+ if (mode != GET_MODE (opb0))
+ mode = VOIDmode;
+ else if (mode == VOIDmode)
+ {
+ mode = GET_MODE (op1);
+ if (mode != GET_MODE (opb1))
+ mode = VOIDmode;
+ }
+
+ if (mode != VOIDmode
+ && rtx_equal_p (op1, opb1)
+ && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
+ return true;
+ }
+
return false;
}
mode = GET_MODE (op0);
if (mode == VOIDmode)
mode = GET_MODE (op1);
- if (mode == VOIDmode)
- abort ();
+ gcc_assert (mode != VOIDmode);
if (GET_CODE (op1) == CONST_INT
&& GET_MODE_CLASS (mode) != MODE_CC
{
rtx rev, reve, exp = *expr;
- if (GET_RTX_CLASS (GET_CODE (*expr)) != '<')
+ if (!COMPARISON_P (exp))
return;
/* If some register gets altered later, we do not really speak about its
static void
eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
{
- if (op == AND)
+ switch (op)
{
+ case AND:
/* If A implies *B, we may replace *B by true. */
if (implies_p (a, *b))
*b = const_true_rtx;
- }
- else if (op == IOR)
- {
+ break;
+
+ case IOR:
/* If *B implies A, we may replace *B by false. */
if (implies_p (*b, a))
*b = const0_rtx;
+ break;
+
+ default:
+ gcc_unreachable ();
}
- else
- abort ();
}
/* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
rtx head, tail, insn;
rtx neutral, aggr;
regset altered;
- regset_head altered_head;
edge e;
if (!*expr)
eliminate_implied_conditions (op, &head, tail);
- if (op == AND)
+ switch (op)
{
+ case AND:
neutral = const_true_rtx;
aggr = const0_rtx;
- }
- else if (op == IOR)
- {
+ break;
+
+ case IOR:
neutral = const0_rtx;
aggr = const_true_rtx;
- }
- else
- abort ();
+ break;
- simplify_using_initial_values (loop, NIL, &head);
+ default:
+ gcc_unreachable ();
+ }
+
+ simplify_using_initial_values (loop, UNKNOWN, &head);
if (head == aggr)
{
XEXP (*expr, 0) = aggr;
return;
}
- if (op != NIL)
- abort ();
+ gcc_assert (op == UNKNOWN);
e = loop_preheader_edge (loop);
if (e->src == ENTRY_BLOCK_PTR)
return;
- altered = INITIALIZE_REG_SET (altered_head);
+ altered = ALLOC_REG_SET (®_obstack);
while (1)
{
insn = BB_END (e->src);
if (any_condjump_p (insn))
{
- /* FIXME -- slightly wrong -- what if compared register
- gets altered between start of the condition and insn? */
- rtx cond = get_condition (BB_END (e->src), NULL, false);
+ rtx cond = get_condition (BB_END (e->src), NULL, false, true);
if (cond && (e->flags & EDGE_FALLTHRU))
cond = reversed_condition (cond);
}
}
- e = e->src->pred;
- if (e->pred_next
- || e->src == ENTRY_BLOCK_PTR)
+ if (!single_pred_p (e->src)
+ || single_pred (e->src) == ENTRY_BLOCK_PTR)
break;
+ e = single_pred_edge (e->src);
}
FREE_REG_SET (altered);
{
rtx mmin, mmax, cond_over, cond_under;
- get_mode_bounds (mode, signed_p, &mmin, &mmax);
+ get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
iv->base, mmin);
cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
break;
default:
- abort ();
+ gcc_unreachable ();
}
iv->mode = mode;
}
/* Transforms IV0 and IV1 compared by COND so that they are both compared as
- subregs of the same mode if possible (sometimes it is neccesary to add
+ subregs of the same mode if possible (sometimes it is necessary to add
some assumptions to DESC). */
static bool
break;
case NE:
- if (iv0->extend != NIL
- && iv1->extend != NIL
+ if (iv0->extend != UNKNOWN
+ && iv1->extend != UNKNOWN
&& iv0->extend != iv1->extend)
return false;
signed_p = false;
- if (iv0->extend != NIL)
+ if (iv0->extend != UNKNOWN)
signed_p = iv0->extend == SIGN_EXTEND;
- if (iv1->extend != NIL)
+ if (iv1->extend != UNKNOWN)
signed_p = iv1->extend == SIGN_EXTEND;
break;
default:
- abort ();
+ gcc_unreachable ();
}
/* Values of both variables should be computed in the same mode. These
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)
{
rtx op0, op1, delta, step, bound, may_xform, def_insn, tmp, tmp0, tmp1;
struct rtx_iv iv0, iv1, tmp_iv;
- rtx assumption;
+ rtx assumption, may_not_xform;
enum rtx_code cond;
enum machine_mode mode, comp_mode;
- rtx mmin, mmax;
- unsigned HOST_WIDEST_INT s, size, d;
- HOST_WIDEST_INT up, down, inc;
+ rtx mmin, mmax, mode_mmin, mode_mmax;
+ unsigned HOST_WIDEST_INT s, size, d, inv;
+ 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
desc->niter_max = 0;
cond = GET_CODE (condition);
- if (GET_RTX_CLASS (cond) != '<')
- abort ();
+ gcc_assert (COMPARISON_P (condition));
mode = GET_MODE (XEXP (condition, 0));
if (mode == VOIDmode)
mode = GET_MODE (XEXP (condition, 1));
/* The constant comparisons should be folded. */
- if (mode == VOIDmode)
- abort ();
+ gcc_assert (mode != VOIDmode);
/* We only handle integers or pointers. */
if (GET_MODE_CLASS (mode) != MODE_INT
comp_mode = iv0.extend_mode;
mode = iv0.mode;
size = GET_MODE_BITSIZE (mode);
- get_mode_bounds (mode, (cond == LE || cond == LT), &mmin, &mmax);
+ get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
+ mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
+ mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
if (GET_CODE (iv0.step) != CONST_INT || GET_CODE (iv1.step) != CONST_INT)
goto fail;
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 (iv0.step == const0_rtx)
{
tmp = lowpart_subreg (mode, iv0.base, comp_mode);
- assumption = simplify_gen_relational (EQ, SImode, mode, tmp, mmax);
+ assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
+ mode_mmax);
if (assumption == const_true_rtx)
- goto zero_iter;
+ goto zero_iter_simplify;
iv0.base = simplify_gen_binary (PLUS, comp_mode,
iv0.base, const1_rtx);
}
else
{
tmp = lowpart_subreg (mode, iv1.base, comp_mode);
- assumption = simplify_gen_relational (EQ, SImode, mode, tmp, mmin);
+ assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
+ mode_mmin);
if (assumption == const_true_rtx)
- goto zero_iter;
+ goto zero_iter_simplify;
iv1.base = simplify_gen_binary (PLUS, comp_mode,
iv1.base, constm1_rtx);
}
if (iv0.step == const0_rtx)
{
tmp = lowpart_subreg (mode, iv0.base, comp_mode);
- if (rtx_equal_p (tmp, mmin))
+ if (rtx_equal_p (tmp, mode_mmin))
{
desc->infinite =
alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
- return;
+ /* Fill in the remaining fields somehow. */
+ goto zero_iter_simplify;
}
}
else
{
tmp = lowpart_subreg (mode, iv1.base, comp_mode);
- if (rtx_equal_p (tmp, mmax))
+ if (rtx_equal_p (tmp, mode_mmax))
{
desc->infinite =
alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
- return;
+ /* Fill in the remaining fields somehow. */
+ goto zero_iter_simplify;
}
}
}
delta = lowpart_subreg (mode, delta, comp_mode);
delta = simplify_gen_binary (UMOD, mode, delta, step);
may_xform = const0_rtx;
+ may_not_xform = const_true_rtx;
if (GET_CODE (delta) == CONST_INT)
{
obviously if the test for overflow during that transformation
passed, we cannot overflow here. Most importantly any
loop with sharp end condition and step 1 falls into this
- cathegory, so handling this case specially is definitely
+ category, so handling this case specially is definitely
worth the troubles. */
may_xform = const_true_rtx;
}
tmp = lowpart_subreg (mode, iv0.base, comp_mode);
may_xform = simplify_gen_relational (cond, SImode, mode,
bound, tmp);
+ may_not_xform = simplify_gen_relational (reverse_condition (cond),
+ SImode, mode,
+ bound, tmp);
}
else
{
tmp = lowpart_subreg (mode, iv1.base, comp_mode);
may_xform = simplify_gen_relational (cond, SImode, mode,
tmp, bound);
+ may_not_xform = simplify_gen_relational (reverse_condition (cond),
+ SImode, mode,
+ tmp, bound);
}
}
completely senseless. This is OK, as we would need this assumption
to determine the number of iterations anyway. */
if (may_xform != const_true_rtx)
- desc->assumptions = alloc_EXPR_LIST (0, may_xform,
- desc->assumptions);
+ {
+ /* 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. */
+ if (step_is_pow2)
+ desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
+ desc->infinite);
+ else
+ desc->assumptions = alloc_EXPR_LIST (0, may_xform,
+ desc->assumptions);
+ }
/* We are going to lose some information about upper bound on
number of iterations in this step, so record the information
if (GET_CODE (iv1.base) == CONST_INT)
up = INTVAL (iv1.base);
else
- up = INTVAL (mmax) - inc;
- down = INTVAL (GET_CODE (iv0.base) == CONST_INT ? iv0.base : mmin);
+ up = INTVAL (mode_mmax) - inc;
+ down = INTVAL (GET_CODE (iv0.base) == CONST_INT
+ ? iv0.base
+ : mode_mmin);
desc->niter_max = (up - down) / inc + 1;
if (iv0.step == const0_rtx)
assumption = simplify_gen_relational (reverse_condition (cond),
SImode, mode, tmp0, tmp1);
if (assumption == const_true_rtx)
- goto zero_iter;
+ goto zero_iter_simplify;
else if (assumption != const0_rtx)
desc->noloop_assumptions =
alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
- tmp = simplify_gen_binary (MULT, mode,
- tmp, GEN_INT (inverse (s, size)));
+ inv = inverse (s, size);
+ tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
}
else
tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
- bound = simplify_gen_binary (MINUS, mode, mmax, step);
- assumption = simplify_gen_relational (cond, SImode, mode,
- tmp1, bound);
- desc->assumptions =
- alloc_EXPR_LIST (0, assumption, desc->assumptions);
+ bound = simplify_gen_binary (MINUS, mode, mode_mmax,
+ 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);
tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
- bound = simplify_gen_binary (MINUS, mode, mmin, step);
- assumption = simplify_gen_relational (cond, SImode, mode,
- bound, tmp0);
- desc->assumptions =
- alloc_EXPR_LIST (0, assumption, desc->assumptions);
+ bound = simplify_gen_binary (PLUS, mode, mode_mmin,
+ 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 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);
delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
}
if (assumption == const_true_rtx)
- goto zero_iter;
+ goto zero_iter_simplify;
else if (assumption != const0_rtx)
desc->noloop_assumptions =
alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
desc->niter_expr = delta;
}
+ old_niter = desc->niter_expr;
+
simplify_using_initial_values (loop, AND, &desc->assumptions);
if (desc->assumptions
&& XEXP (desc->assumptions, 0) == const0_rtx)
goto fail;
simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
simplify_using_initial_values (loop, IOR, &desc->infinite);
- simplify_using_initial_values (loop, NIL, &desc->niter_expr);
+ simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
/* Rerun the simplification. Consider code (created by copying loop headers)
goto fail;
simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
simplify_using_initial_values (loop, IOR, &desc->infinite);
- simplify_using_initial_values (loop, NIL, &desc->niter_expr);
+ simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
+
+ if (desc->noloop_assumptions
+ && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
+ goto zero_iter;
if (GET_CODE (desc->niter_expr) == CONST_INT)
{
desc->const_iter = true;
desc->niter_max = desc->niter = val & GET_MODE_MASK (desc->mode);
}
- else if (!desc->niter_max)
- desc->niter_max = determine_max_iter (desc);
+ else
+ {
+ if (!desc->niter_max)
+ desc->niter_max = determine_max_iter (desc);
- return;
+ /* simplify_using_initial_values does a copy propagation on the registers
+ in the expression for the number of iterations. This prolongs life
+ ranges of registers and increases register pressure, and usually
+ brings no gain (and if it happens to do, the cse pass will take care
+ of it anyway). So prevent this behavior, unless it enabled us to
+ derive that the number of iterations is a constant. */
+ desc->niter_expr = old_niter;
+ }
-fail:
- desc->simple_p = false;
return;
+zero_iter_simplify:
+ /* Simplify the assumptions. */
+ simplify_using_initial_values (loop, AND, &desc->assumptions);
+ if (desc->assumptions
+ && XEXP (desc->assumptions, 0) == const0_rtx)
+ goto fail;
+ simplify_using_initial_values (loop, IOR, &desc->infinite);
+
+ /* Fallthru. */
zero_iter:
desc->const_iter = true;
desc->niter = 0;
desc->niter_max = 0;
+ desc->noloop_assumptions = NULL_RTX;
desc->niter_expr = const0_rtx;
return;
+
+fail:
+ desc->simple_p = false;
+ return;
}
/* Checks whether E is a simple exit from LOOP and stores its description
- into DESC. TODO Should replace cfgloopanal.c:simple_loop_exit_p. */
+ into DESC. */
static void
check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
{
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)))
+ 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)
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. */
+/* Finds a simple exit of LOOP and stores its description into DESC. */
void
find_simple_exit (struct loop *loop, struct niter_desc *desc)
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;
if (!act.simple_p)
continue;
- /* Prefer constant iterations; the less the better. */
if (!any)
any = true;
- else if (!act.const_iter
- || (desc->const_iter && act.niter >= desc->niter))
- continue;
+ else
+ {
+ /* Prefer constant iterations; the less the better. */
+ if (!act.const_iter
+ || (desc->const_iter && act.niter >= desc->niter))
+ continue;
+
+ /* Also if the actual exit may be infinite, while the old one
+ not, prefer the old one. */
+ if (act.infinite && !desc->infinite)
+ continue;
+ }
+
*desc = act;
}
}
find_simple_exit (loop, desc);
loop->aux = desc;
+ if (desc->simple_p && (desc->assumptions || desc->infinite))
+ {
+ const char *wording;
+
+ /* Assume that no overflow happens and that the loop is finite.
+ We already warned at the tree level if we ran optimizations there. */
+ if (!flag_tree_loop_optimize && warn_unsafe_loop_optimizations)
+ {
+ if (desc->infinite)
+ {
+ wording =
+ flag_unsafe_loop_optimizations
+ ? N_("assuming that the loop is not infinite")
+ : N_("cannot optimize possibly infinite loops");
+ warning (OPT_Wunsafe_loop_optimizations, "%s",
+ gettext (wording));
+ }
+ if (desc->assumptions)
+ {
+ wording =
+ flag_unsafe_loop_optimizations
+ ? N_("assuming that the loop counter does not overflow")
+ : N_("cannot optimize loop, the loop counter may overflow");
+ warning (OPT_Wunsafe_loop_optimizations, "%s",
+ gettext (wording));
+ }
+ }
+
+ if (flag_unsafe_loop_optimizations)
+ {
+ desc->assumptions = NULL_RTX;
+ desc->infinite = NULL_RTX;
+ }
+ }
+
return desc;
}