/* 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.
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 2, or (at your option) any
+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
for more details.
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, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
/* This is a simple analysis of induction variables of the loop. The major use
is for determining the number of iterations of a loop for loop unrolling,
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);
static int
biv_eq (const void *b, const void *r)
{
- return ((const struct biv_entry *) b)->regno == REGNO ((rtx) r);
+ return ((const struct biv_entry *) b)->regno == REGNO ((const_rtx) r);
}
/* Prepare the data for an induction variable analysis of a LOOP. */
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;
}
}
/* Marks registers altered by EXPR in set ALT. */
static void
-mark_altered (rtx expr, rtx by ATTRIBUTE_UNUSED, void *alt)
+mark_altered (rtx expr, const_rtx by ATTRIBUTE_UNUSED, void *alt)
{
if (GET_CODE (expr) == SUBREG)
expr = SUBREG_REG (expr);
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;
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)