/* Rtl-level induction variable analysis.
- Copyright (C) 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
This file is part of GCC.
iv_analyze_expr (insn, rhs, mode, iv): Stores to IV the description of iv
corresponding to expression EXPR evaluated at INSN. All registers used bu
EXPR must also be used in INSN.
- iv_current_loop_df (): Returns the dataflow object for the current loop used
- by iv analysis. */
+*/
#include "config.h"
#include "system.h"
struct rtx_iv iv; /* Value of the biv. */
};
+static bool clean_slate = true;
+
+static unsigned int iv_ref_table_size = 0;
+
+/* Table of rtx_ivs indexed by the df_ref uid field. */
+static struct rtx_iv ** iv_ref_table;
+
/* Induction variable stored at the reference. */
-#define DF_REF_IV(REF) ((struct rtx_iv *) DF_REF_DATA (REF))
-#define DF_REF_IV_SET(REF, IV) DF_REF_DATA (REF) = (IV)
+#define DF_REF_IV(REF) iv_ref_table[DF_REF_ID(REF)]
+#define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID(REF)] = (IV)
/* The current loop. */
static struct loop *current_loop;
-/* Dataflow information for the current loop. */
-
-static struct df *df = NULL;
-
/* Bivs of the current loop. */
static htab_t bivs;
-/* Return the dataflow object for the current loop. */
-struct df *
-iv_current_loop_df (void)
-{
- return df;
-}
-
static bool iv_analyze_op (rtx, rtx, struct rtx_iv *);
/* Dumps information about IV to FILE. */
subreg_lowpart_offset (outer_mode, inner_mode));
}
+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 = xrealloc (iv_ref_table,
+ sizeof (struct rtx_iv *) * new_size);
+ 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;
+ }
+}
+
+
/* Checks whether REG is a well-behaved register. */
static bool
static void
clear_iv_info (void)
{
- unsigned i, n_defs = DF_DEFS_SIZE (df);
+ unsigned i, n_defs = DF_DEFS_TABLE_SIZE ();
struct rtx_iv *iv;
- struct df_ref *def;
+ check_iv_ref_table_size ();
for (i = 0; i < n_defs; i++)
{
- def = DF_DEFS_GET (df, i);
- iv = DF_REF_IV (def);
- if (!iv)
- continue;
- free (iv);
- DF_REF_IV_SET (def, NULL);
+ iv = iv_ref_table[i];
+ if (iv)
+ {
+ free (iv);
+ iv_ref_table[i] = NULL;
+ }
}
htab_empty (bivs);
basic_block *body = get_loop_body_in_dom_order (loop), bb;
bitmap blocks = BITMAP_ALLOC (NULL);
unsigned i;
- bool first_time = (df == NULL);
current_loop = loop;
/* Clear the information from the analysis of the previous loop. */
- if (first_time)
+ if (clean_slate)
{
- df = df_init (DF_HARD_REGS | DF_EQUIV_NOTES);
- df_chain_add_problem (df, DF_UD_CHAIN);
+ df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
bivs = htab_create (10, biv_hash, biv_eq, free);
+ clean_slate = false;
}
else
clear_iv_info ();
bb = body[i];
bitmap_set_bit (blocks, bb->index);
}
- df_set_blocks (df, blocks);
- df_analyze (df);
+ /* Get rid of the ud chains before processing the rescans. Then add
+ the problem back. */
+ df_remove_problem (df_chain);
+ df_process_deferred_rescans ();
+ df_chain_add_problem (DF_UD_CHAIN);
+ df_set_blocks (blocks);
+ df_analyze ();
+ if (dump_file)
+ df_dump (dump_file);
+
+ check_iv_ref_table_size ();
BITMAP_FREE (blocks);
free (body);
}
{
struct df_ref *single_rd = NULL, *adef;
unsigned regno = REGNO (reg);
- struct df_reg_info *reg_info = DF_REG_DEF_GET (df, regno);
- struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (df, current_loop->latch);
+ struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (current_loop->latch);
- for (adef = reg_info->reg_chain; adef; adef = adef->next_reg)
+ for (adef = DF_REG_DEF_CHAIN (regno); adef; adef = adef->next_reg)
{
if (!bitmap_bit_p (bb_info->out, DF_REF_ID (adef)))
continue;
reg = SUBREG_REG (reg);
gcc_assert (REG_P (reg));
- use = df_find_use (df, insn, reg);
+ use = df_find_use (insn, reg);
gcc_assert (use != NULL);
if (!DF_REF_CHAIN (use))
return GRD_INVALID;
adef = DF_REF_CHAIN (use)->ref;
+
+ /* We do not handle setting only part of the register. */
+ if (adef->flags & DF_REF_READ_WRITE)
+ return GRD_INVALID;
+
def_insn = DF_REF_INSN (adef);
def_bb = DF_REF_BB (adef);
use_bb = BLOCK_FOR_INSN (insn);
if (use_bb == def_bb)
- dom_p = (DF_INSN_LUID (df, def_insn) < DF_INSN_LUID (df, insn));
+ dom_p = (DF_INSN_LUID (def_insn) < DF_INSN_LUID (insn));
else
dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb);
struct rtx_iv *recorded_iv = XNEW (struct rtx_iv);
*recorded_iv = *iv;
+ check_iv_ref_table_size ();
DF_REF_IV_SET (def, recorded_iv);
}
if (dump_file)
{
- fprintf (dump_file, "Analysing def of ");
+ fprintf (dump_file, "Analyzing def of ");
print_rtl (dump_file, reg);
fprintf (dump_file, " in insn ");
print_rtl_single (dump_file, insn);
}
-
+
+ check_iv_ref_table_size ();
if (DF_REF_IV (def))
{
if (dump_file)
iv->base = NULL_RTX;
iv->step = NULL_RTX;
+ if (!REG_P (reg))
+ return false;
+
set = single_set (insn);
- if (!set || SET_DEST (set) != reg)
+ if (!set)
+ return false;
+
+ if (!REG_P (SET_DEST (set)))
return false;
+ gcc_assert (SET_DEST (set) == reg);
rhs = find_reg_equal_equiv_note (insn);
if (rhs)
rhs = XEXP (rhs, 0);
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);
else
reg = val;
- while (!df_find_use (df, insn, reg))
+ while (!df_find_use (insn, reg))
insn = NEXT_INSN (insn);
}
{
struct df_ref *adef;
- adef = df_find_def (df, insn, def);
+ adef = df_find_def (insn, def);
if (!adef)
return false;
if (!simple_reg_p (reg))
return false;
- def = df_find_def (df, insn, reg);
+ def = df_find_def (insn, reg);
gcc_assert (def != NULL);
if (!latch_dominating_def (reg, &last_def))
return false;
void
iv_analysis_done (void)
{
- if (df)
+ if (!clean_slate)
{
clear_iv_info ();
- df_finish (df);
- df = NULL;
+ clean_slate = true;
+ df_finish_pass ();
htab_delete (bivs);
+ free (iv_ref_table);
+ iv_ref_table = NULL;
+ iv_ref_table_size = 0;
bivs = NULL;
}
}
rtx op0, op1;
if (CONSTANT_P (rhs)
- || REG_P (rhs))
+ || (REG_P (rhs) && !HARD_REGISTER_P (rhs)))
return true;
switch (GET_CODE (rhs))
op0 = XEXP (rhs, 0);
op1 = XEXP (rhs, 1);
/* Allow reg + const sets only. */
- if (REG_P (op0) && CONSTANT_P (op1))
+ if (REG_P (op0) && !HARD_REGISTER_P (op0) && CONSTANT_P (op1))
return true;
- if (REG_P (op1) && CONSTANT_P (op0))
+ if (REG_P (op1) && !HARD_REGISTER_P (op1) && CONSTANT_P (op0))
return true;
return false;
}
}
+ if (b == const_true_rtx)
+ return true;
+
+ if ((GET_RTX_CLASS (GET_CODE (a)) != RTX_COMM_COMPARE
+ && GET_RTX_CLASS (GET_CODE (a)) != RTX_COMPARE)
+ || (GET_RTX_CLASS (GET_CODE (b)) != RTX_COMM_COMPARE
+ && GET_RTX_CLASS (GET_CODE (b)) != RTX_COMPARE))
+ return false;
+
+ op0 = XEXP (a, 0);
+ op1 = XEXP (a, 1);
+ opb0 = XEXP (b, 0);
+ opb1 = XEXP (b, 1);
+
+ 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;
+ }
+
/* 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)
{
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 (SCALAR_INT_MODE_P (mode)
&& rtx_equal_p (op1, opb1)
&& simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
return true;
+ return false;
+ }
+
+ /* A < B or A > B imply A != B. TODO: Likewise
+ A + n < B implies A != B + n if neither wraps. */
+ if (GET_CODE (b) == NE
+ && (GET_CODE (a) == GT || GET_CODE (a) == GTU
+ || GET_CODE (a) == LT || GET_CODE (a) == LTU))
+ {
+ if (rtx_equal_p (op0, opb0)
+ && rtx_equal_p (op1, opb1))
+ return true;
}
+ /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
+ if (GET_CODE (a) == NE
+ && op1 == const0_rtx)
+ {
+ if ((GET_CODE (b) == GTU
+ && opb1 == const0_rtx)
+ || (GET_CODE (b) == GEU
+ && opb1 == const1_rtx))
+ return rtx_equal_p (op0, opb0);
+ }
+
+ /* A != N is equivalent to A - (N + 1) <u -1. */
+ if (GET_CODE (a) == NE
+ && GET_CODE (op1) == CONST_INT
+ && GET_CODE (b) == LTU
+ && opb1 == constm1_rtx
+ && GET_CODE (opb0) == PLUS
+ && GET_CODE (XEXP (opb0, 1)) == CONST_INT
+ /* Avoid overflows. */
+ && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
+ != ((unsigned HOST_WIDE_INT)1
+ << (HOST_BITS_PER_WIDE_INT - 1)) - 1)
+ && INTVAL (XEXP (opb0, 1)) + 1 == -INTVAL (op1))
+ return rtx_equal_p (op0, XEXP (opb0, 0));
+
+ /* Likewise, A != N implies A - N > 0. */
+ if (GET_CODE (a) == NE
+ && GET_CODE (op1) == CONST_INT)
+ {
+ if (GET_CODE (b) == GTU
+ && GET_CODE (opb0) == PLUS
+ && opb1 == const0_rtx
+ && GET_CODE (XEXP (opb0, 1)) == CONST_INT
+ /* Avoid overflows. */
+ && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
+ != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
+ && rtx_equal_p (XEXP (opb0, 0), op0))
+ return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
+ if (GET_CODE (b) == GEU
+ && GET_CODE (opb0) == PLUS
+ && opb1 == const1_rtx
+ && GET_CODE (XEXP (opb0, 1)) == CONST_INT
+ /* Avoid overflows. */
+ && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
+ != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
+ && rtx_equal_p (XEXP (opb0, 0), op0))
+ return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
+ }
+
+ /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
+ if ((GET_CODE (a) == GT || GET_CODE (a) == GE)
+ && GET_CODE (op1) == CONST_INT
+ && ((GET_CODE (a) == GT && op1 == constm1_rtx)
+ || INTVAL (op1) >= 0)
+ && GET_CODE (b) == LTU
+ && GET_CODE (opb1) == CONST_INT)
+ return INTVAL (opb1) < 0;
+
return false;
}
FREE_REG_SET (altered);
return;
}
+ if (for_each_rtx (expr, altered_reg_used, altered))
+ {
+ FREE_REG_SET (altered);
+ return;
+ }
}
if (!single_pred_p (e->src)
/* Tries to estimate the maximum number of iterations. */
static unsigned HOST_WIDEST_INT
-determine_max_iter (struct niter_desc *desc)
+determine_max_iter (struct loop *loop, struct niter_desc *desc)
{
rtx niter = desc->niter_expr;
- rtx mmin, mmax, left, right;
+ rtx mmin, mmax, cmp;
unsigned HOST_WIDEST_INT nmax, inc;
if (GET_CODE (niter) == AND
else
inc = 1;
- if (GET_CODE (niter) == PLUS)
+ /* 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);
+ simplify_using_initial_values (loop, UNKNOWN, &cmp);
+ if (cmp == const_true_rtx)
{
- left = XEXP (niter, 0);
- right = XEXP (niter, 0);
+ nmax--;
- if (GET_CODE (right) == CONST_INT)
- right = GEN_INT (-INTVAL (right));
- }
- else if (GET_CODE (niter) == MINUS)
- {
- left = XEXP (niter, 0);
- right = XEXP (niter, 0);
- }
- else
- {
- left = niter;
- right = mmin;
+ if (dump_file)
+ fprintf (dump_file, ";; improved upper bound by one.\n");
}
-
- if (GET_CODE (left) == CONST_INT)
- mmax = left;
- if (GET_CODE (right) == CONST_INT)
- mmin = right;
- nmax = INTVAL (mmax) - INTVAL (mmin);
-
desc->niter_max = nmax / inc;
return nmax / inc;
}
else
{
if (!desc->niter_max)
- desc->niter_max = determine_max_iter (desc);
+ desc->niter_max = determine_max_iter (loop, desc);
/* simplify_using_initial_values does a copy propagation on the registers
in the expression for the number of iterations. This prolongs life