/* 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
#include "basic-block.h"
#include "cfgloop.h"
#include "expr.h"
+#include "intl.h"
#include "output.h"
+#include "toplev.h"
/* The insn information. */
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;
rhs = XEXP (rhs, 0);
else
rhs = SET_SRC (set);
- lhs = SET_DEST (set);
code = GET_CODE (rhs);
switch (code)
case SIGN_EXTEND:
case ZERO_EXTEND:
- if (GET_MODE (op0) != *inner_mode
- || *extend != UNKNOWN
- || *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 == UNKNOWN)
- abort ();
-
- if (*inner_mode == *outer_mode
- && *extend != UNKNOWN)
- 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");
}
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);
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);
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:
- if (CONSTANT_P (XEXP (rhs, 0)))
- abort ();
+ gcc_assert (!CONSTANT_P (XEXP (rhs, 0)));
op0 = XEXP (rhs, 0);
mby = XEXP (rhs, 1);
break;
default:
- abort ();
+ gcc_unreachable ();
}
amode = GET_MODE (rhs);
/* 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,
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
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
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;
+ default:
+ gcc_unreachable ();
+ }
+
simplify_using_initial_values (loop, UNKNOWN, &head);
if (head == aggr)
{
return;
}
- if (op != UNKNOWN)
- abort ();
+ gcc_assert (op == UNKNOWN);
e = loop_preheader_edge (loop);
if (e->src == ENTRY_BLOCK_PTR)
return;
- altered = OBSTACK_ALLOC_REG_SET (®_obstack);
+ altered = ALLOC_REG_SET (®_obstack);
while (1)
{
- basic_block tmp_bb;
-
insn = BB_END (e->src);
if (any_condjump_p (insn))
{
}
}
- /* 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)
+ if (!single_pred_p (e->src)
+ || single_pred (e->src) == ENTRY_BLOCK_PTR)
break;
+ e = single_pred_edge (e->src);
}
FREE_REG_SET (altered);
break;
default:
- abort ();
+ gcc_unreachable ();
}
iv->mode = mode;
break;
default:
- abort ();
+ gcc_unreachable ();
}
/* Values of both variables should be computed in the same mode. These
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
desc->niter_max = 0;
cond = GET_CODE (condition);
- if (!COMPARISON_P (condition))
- 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
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. */
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);
}
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);
}
{
desc->infinite =
alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
- return;
+ /* Fill in the remaining fields somehow. */
+ goto zero_iter_simplify;
}
}
else
{
desc->infinite =
alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
- return;
+ /* Fill in the remaining fields somehow. */
+ goto zero_iter_simplify;
}
}
}
/* 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
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);
tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
inv = inverse (s, size);
- inv = trunc_int_for_mode (inv, mode);
- tmp = simplify_gen_binary (MULT, mode, tmp, GEN_INT (inv));
+ tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
}
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);
tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
- bound = simplify_gen_binary (MINUS, mode, mode_mmin,
+ bound = simplify_gen_binary (PLUS, 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);
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);
return;
-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
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;
}
OSDN Git Service
