X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Floop-iv.c;h=16e9a52697dafbd76784ff9fa706edefc8ac01f9;hp=123e37cff599a7af8acbfe1ed0bd461740e89370;hb=6fe60bfdba8c1d684d9de61f4a39162ff7cfa33d;hpb=7f7a6f4a129b77b67da8db39c088223443fd8d23
diff --git a/gcc/loop-iv.c b/gcc/loop-iv.c
index 123e37cff59..16e9a52697d 100644
--- a/gcc/loop-iv.c
+++ b/gcc/loop-iv.c
@@ -1,19 +1,19 @@
/* Rtl-level induction variable analysis.
Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
Free Software Foundation, Inc.
-
+
This file is part of GCC.
-
+
GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 3, or (at your option) any
later version.
-
+
GCC is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
-
+
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
. */
@@ -35,7 +35,7 @@ along with GCC; see the file COPYING3. If not see
iv_analysis_done () to clean up the memory.
The available functions are:
-
+
iv_analyze (insn, reg, iv): Stores the description of the induction variable
corresponding to the use of register REG in INSN to IV. Returns true if
REG is an induction variable in INSN. false otherwise.
@@ -168,14 +168,14 @@ lowpart_subreg (enum machine_mode outer_mode, rtx expr,
subreg_lowpart_offset (outer_mode, inner_mode));
}
-static void
+static void
check_iv_ref_table_size (void)
{
if (iv_ref_table_size < DF_DEFS_TABLE_SIZE())
{
unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
iv_ref_table = XRESIZEVEC (struct rtx_iv *, iv_ref_table, new_size);
- memset (&iv_ref_table[iv_ref_table_size], 0,
+ memset (&iv_ref_table[iv_ref_table_size], 0,
(new_size - iv_ref_table_size) * sizeof (struct rtx_iv *));
iv_ref_table_size = new_size;
}
@@ -278,6 +278,7 @@ iv_analysis_loop_init (struct loop *loop)
df_remove_problem (df_chain);
df_process_deferred_rescans ();
df_chain_add_problem (DF_UD_CHAIN);
+ df_note_add_problem ();
df_set_blocks (blocks);
df_analyze ();
if (dump_file)
@@ -329,7 +330,7 @@ iv_get_reaching_def (rtx insn, rtx reg, df_ref *def)
basic_block def_bb, use_bb;
rtx def_insn;
bool dom_p;
-
+
*def = NULL;
if (!simple_reg_p (reg))
return GRD_INVALID;
@@ -858,7 +859,7 @@ iv_analyze_biv (rtx def, struct rtx_iv *iv)
print_rtl (dump_file, def);
fprintf (dump_file, " for bivness.\n");
}
-
+
if (!REG_P (def))
{
if (!CONSTANT_P (def))
@@ -918,7 +919,7 @@ iv_analyze_biv (rtx def, struct rtx_iv *iv)
return iv->base != NULL_RTX;
}
-/* Analyzes expression RHS used at INSN and stores the result to *IV.
+/* Analyzes expression RHS used at INSN and stores the result to *IV.
The mode of the induction variable is MODE. */
bool
@@ -942,7 +943,7 @@ iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv)
{
if (!iv_analyze_op (insn, rhs, iv))
return false;
-
+
if (iv->mode == VOIDmode)
{
iv->mode = mode;
@@ -1056,7 +1057,7 @@ iv_analyze_def (df_ref def, struct rtx_iv *iv)
fprintf (dump_file, " in insn ");
print_rtl_single (dump_file, insn);
}
-
+
check_iv_ref_table_size ();
if (DF_REF_IV (def))
{
@@ -1119,7 +1120,7 @@ iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv)
print_rtl_single (dump_file, insn);
}
- if (CONSTANT_P (op))
+ if (function_invariant_p (op))
res = GRD_INVARIANT;
else if (GET_CODE (op) == SUBREG)
{
@@ -1328,7 +1329,7 @@ simple_rhs_p (rtx rhs)
{
rtx op0, op1;
- if (CONSTANT_P (rhs)
+ if (function_invariant_p (rhs)
|| (REG_P (rhs) && !HARD_REGISTER_P (rhs)))
return true;
@@ -1336,25 +1337,29 @@ simple_rhs_p (rtx rhs)
{
case PLUS:
case MINUS:
+ case AND:
op0 = XEXP (rhs, 0);
op1 = XEXP (rhs, 1);
- /* Allow reg + const and reg + reg. */
+ /* Allow reg OP const and reg OP reg. */
if (!(REG_P (op0) && !HARD_REGISTER_P (op0))
- && !CONSTANT_P (op0))
+ && !function_invariant_p (op0))
return false;
if (!(REG_P (op1) && !HARD_REGISTER_P (op1))
- && !CONSTANT_P (op1))
+ && !function_invariant_p (op1))
return false;
return true;
case ASHIFT:
+ case ASHIFTRT:
+ case LSHIFTRT:
+ case MULT:
op0 = XEXP (rhs, 0);
op1 = XEXP (rhs, 1);
- /* Allow reg << const. */
+ /* Allow reg OP const. */
if (!(REG_P (op0) && !HARD_REGISTER_P (op0)))
return false;
- if (!CONSTANT_P (op1))
+ if (!function_invariant_p (op1))
return false;
return true;
@@ -1364,6 +1369,57 @@ simple_rhs_p (rtx rhs)
}
}
+/* If REG has a single definition, replace it with its known value in EXPR.
+ Callback for for_each_rtx. */
+
+static int
+replace_single_def_regs (rtx *reg, void *expr1)
+{
+ unsigned regno;
+ df_ref adef;
+ rtx set, src;
+ rtx *expr = (rtx *)expr1;
+
+ if (!REG_P (*reg))
+ return 0;
+
+ regno = REGNO (*reg);
+ for (;;)
+ {
+ rtx note;
+ adef = DF_REG_DEF_CHAIN (regno);
+ if (adef == NULL || DF_REF_NEXT_REG (adef) != NULL
+ || DF_REF_IS_ARTIFICIAL (adef))
+ return -1;
+
+ set = single_set (DF_REF_INSN (adef));
+ if (set == NULL || !REG_P (SET_DEST (set))
+ || REGNO (SET_DEST (set)) != regno)
+ return -1;
+
+ note = find_reg_equal_equiv_note (DF_REF_INSN (adef));
+
+ if (note && function_invariant_p (XEXP (note, 0)))
+ {
+ src = XEXP (note, 0);
+ break;
+ }
+ src = SET_SRC (set);
+
+ if (REG_P (src))
+ {
+ regno = REGNO (src);
+ continue;
+ }
+ break;
+ }
+ if (!function_invariant_p (src))
+ return -1;
+
+ *expr = simplify_replace_rtx (*expr, *reg, src);
+ return 1;
+}
+
/* A subroutine of simplify_using_initial_values, this function examines INSN
to see if it contains a suitable set that we can use to make a replacement.
If it is suitable, return true and set DEST and SRC to the lhs and rhs of
@@ -1396,6 +1452,20 @@ suitable_set_for_replacement (rtx insn, rtx *dest, rtx *src)
return true;
}
+/* Using the data returned by suitable_set_for_replacement, replace DEST
+ with SRC in *EXPR and return the new expression. Also call
+ replace_single_def_regs if the replacement changed something. */
+static void
+replace_in_expr (rtx *expr, rtx dest, rtx src)
+{
+ rtx old = *expr;
+ *expr = simplify_replace_rtx (*expr, dest, src);
+ if (old == *expr)
+ return;
+ while (for_each_rtx (expr, replace_single_def_regs, expr) != 0)
+ continue;
+}
+
/* Checks whether A implies B. */
static bool
@@ -1498,11 +1568,11 @@ implies_p (rtx a, rtx b)
/* A != N is equivalent to A - (N + 1) 0. */
if (GET_CODE (a) == NE
- && GET_CODE (op1) == CONST_INT)
+ && CONST_INT_P (op1))
{
if (GET_CODE (b) == GTU
&& GET_CODE (opb0) == PLUS
&& opb1 == const0_rtx
- && GET_CODE (XEXP (opb0, 1)) == CONST_INT
+ && CONST_INT_P (XEXP (opb0, 1))
/* Avoid overflows. */
&& ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
!= ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
@@ -1526,7 +1596,7 @@ implies_p (rtx a, rtx b)
if (GET_CODE (b) == GEU
&& GET_CODE (opb0) == PLUS
&& opb1 == const1_rtx
- && GET_CODE (XEXP (opb0, 1)) == CONST_INT
+ && CONST_INT_P (XEXP (opb0, 1))
/* Avoid overflows. */
&& ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
!= ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
@@ -1536,11 +1606,11 @@ implies_p (rtx a, rtx b)
/* A >s X, where X is positive, implies A = 0)
&& GET_CODE (b) == LTU
- && GET_CODE (opb1) == CONST_INT
+ && CONST_INT_P (opb1)
&& rtx_equal_p (op0, opb0))
return INTVAL (opb1) < 0;
@@ -1579,7 +1649,7 @@ canon_condition (rtx cond)
mode = GET_MODE (op1);
gcc_assert (mode != VOIDmode);
- if (GET_CODE (op1) == CONST_INT
+ if (CONST_INT_P (op1)
&& GET_MODE_CLASS (mode) != MODE_CC
&& GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
{
@@ -1679,7 +1749,7 @@ simplify_using_condition (rtx cond, rtx *expr, regset altered)
*expr = const_true_rtx;
return;
}
-
+
if (reve && implies_p (cond, reve))
{
*expr = const0_rtx;
@@ -1785,7 +1855,7 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
default:
gcc_unreachable ();
}
-
+
simplify_using_initial_values (loop, UNKNOWN, &head);
if (head == aggr)
{
@@ -1806,7 +1876,7 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
*expr = tail;
return;
}
-
+
XEXP (*expr, 0) = head;
XEXP (*expr, 1) = tail;
return;
@@ -1814,6 +1884,12 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
gcc_assert (op == UNKNOWN);
+ for (;;)
+ if (for_each_rtx (expr, replace_single_def_regs, expr) == 0)
+ break;
+ if (CONSTANT_P (*expr))
+ return;
+
e = loop_preheader_edge (loop);
if (e->src == ENTRY_BLOCK_PTR)
return;
@@ -1866,7 +1942,7 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
if (CALL_P (insn))
{
int i;
-
+
/* Kill all call clobbered registers. */
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
@@ -1877,7 +1953,7 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
{
rtx *pnote, *pnote_next;
- *expr = simplify_replace_rtx (*expr, dest, src);
+ replace_in_expr (expr, dest, src);
if (CONSTANT_P (*expr))
goto out;
@@ -1887,8 +1963,8 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
rtx old_cond = XEXP (note, 0);
pnote_next = &XEXP (note, 1);
- XEXP (note, 0) = simplify_replace_rtx (XEXP (note, 0), dest,
- src);
+ replace_in_expr (&XEXP (note, 0), dest, src);
+
/* We can no longer use a condition that has been simplified
to a constant, and simplify_using_condition will abort if
we try. */
@@ -2061,7 +2137,7 @@ canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
and iv0 and iv1 are both ivs iterating in SI mode, but calculated
in different modes. This does not seem impossible to handle, but
it hardly ever occurs in practice.
-
+
The only exception is the case when one of operands is invariant.
For example pentium 3 generates comparisons like
(lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
@@ -2114,17 +2190,20 @@ canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
return true;
}
-/* Tries to estimate the maximum number of iterations. */
+/* Tries to estimate the maximum number of iterations in LOOP, and store the
+ result in DESC. This function is called from iv_number_of_iterations with
+ a number of fields in DESC already filled in. OLD_NITER is the original
+ expression for the number of iterations, before we tried to simplify it. */
static unsigned HOST_WIDEST_INT
-determine_max_iter (struct loop *loop, struct niter_desc *desc)
+determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter)
{
rtx niter = desc->niter_expr;
rtx mmin, mmax, cmp;
unsigned HOST_WIDEST_INT nmax, inc;
if (GET_CODE (niter) == AND
- && GET_CODE (XEXP (niter, 0)) == CONST_INT)
+ && CONST_INT_P (XEXP (niter, 0)))
{
nmax = INTVAL (XEXP (niter, 0));
if (!(nmax & (nmax + 1)))
@@ -2139,7 +2218,7 @@ determine_max_iter (struct loop *loop, struct niter_desc *desc)
if (GET_CODE (niter) == UDIV)
{
- if (GET_CODE (XEXP (niter, 1)) != CONST_INT)
+ if (!CONST_INT_P (XEXP (niter, 1)))
{
desc->niter_max = nmax;
return nmax;
@@ -2152,7 +2231,8 @@ determine_max_iter (struct loop *loop, struct niter_desc *desc)
/* We could use a binary search here, but for now improving the upper
bound by just one eliminates one important corner case. */
- cmp = gen_rtx_fmt_ee (desc->signed_p ? LT : LTU, VOIDmode, niter, mmax);
+ cmp = simplify_gen_relational (desc->signed_p ? LT : LTU, VOIDmode,
+ desc->mode, old_niter, mmax);
simplify_using_initial_values (loop, UNKNOWN, &cmp);
if (cmp == const_true_rtx)
{
@@ -2219,7 +2299,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
goto fail;
if (iv0.extend_mode == VOIDmode)
iv0.mode = iv0.extend_mode = mode;
-
+
op1 = XEXP (condition, 1);
if (!iv_analyze (insn, op1, &iv1))
goto fail;
@@ -2266,7 +2346,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
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)
+ if (!CONST_INT_P (iv0.step) || !CONST_INT_P (iv1.step))
goto fail;
/* We can take care of the case of two induction variables chasing each other
@@ -2397,7 +2477,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
may_xform = const0_rtx;
may_not_xform = const_true_rtx;
- if (GET_CODE (delta) == CONST_INT)
+ if (CONST_INT_P (delta))
{
if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
{
@@ -2460,11 +2540,11 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
number of iterations in this step, so record the information
here. */
inc = INTVAL (iv0.step) - INTVAL (iv1.step);
- if (GET_CODE (iv1.base) == CONST_INT)
+ if (CONST_INT_P (iv1.base))
up = INTVAL (iv1.base);
else
up = INTVAL (mode_mmax) - inc;
- down = INTVAL (GET_CODE (iv0.base) == CONST_INT
+ down = INTVAL (CONST_INT_P (iv0.base)
? iv0.base
: mode_mmin);
desc->niter_max = (up - down) / inc + 1;
@@ -2673,7 +2753,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
&& XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
goto zero_iter;
- if (GET_CODE (desc->niter_expr) == CONST_INT)
+ if (CONST_INT_P (desc->niter_expr))
{
unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
@@ -2683,7 +2763,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
else
{
if (!desc->niter_max)
- desc->niter_max = determine_max_iter (loop, desc);
+ desc->niter_max = determine_max_iter (loop, desc, old_niter);
/* simplify_using_initial_values does a copy propagation on the registers
in the expression for the number of iterations. This prolongs life
@@ -2787,7 +2867,7 @@ find_simple_exit (struct loop *loop, struct niter_desc *desc)
{
if (flow_bb_inside_loop_p (loop, e->dest))
continue;
-
+
check_simple_exit (loop, e, &act);
if (!act.simple_p)
continue;
@@ -2806,7 +2886,7 @@ find_simple_exit (struct loop *loop, struct niter_desc *desc)
if (act.infinite && !desc->infinite)
continue;
}
-
+
*desc = act;
}
}
@@ -2873,15 +2953,15 @@ get_simple_loop_desc (struct loop *loop)
if (desc->simple_p && (desc->assumptions || desc->infinite))
{
- const char *wording;
+ const char *wording;
- /* Assume that no overflow happens and that the loop is finite.
+ /* 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 =
+ wording =
flag_unsafe_loop_optimizations
? N_("assuming that the loop is not infinite")
: N_("cannot optimize possibly infinite loops");
@@ -2890,7 +2970,7 @@ get_simple_loop_desc (struct loop *loop)
}
if (desc->assumptions)
{
- wording =
+ wording =
flag_unsafe_loop_optimizations
? N_("assuming that the loop counter does not overflow")
: N_("cannot optimize loop, the loop counter may overflow");