/* Rtl-level induction variable analysis.
- Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
- Free Software Foundation, Inc.
+ Copyright (C) 2004-2014 Free Software Foundation, Inc.
This file is part of GCC.
#include "intl.h"
#include "diagnostic-core.h"
#include "df.h"
-#include "hashtab.h"
+#include "hash-table.h"
+#include "dumpfile.h"
/* Possible return values of iv_get_reaching_def. */
static struct rtx_iv ** iv_ref_table;
/* Induction variable stored at the reference. */
-#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)
+#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;
+/* Hashtable helper. */
+
+struct biv_entry_hasher : typed_free_remove <biv_entry>
+{
+ typedef biv_entry value_type;
+ typedef rtx_def compare_type;
+ static inline hashval_t hash (const value_type *);
+ static inline bool equal (const value_type *, const compare_type *);
+};
+
+/* Returns hash value for biv B. */
+
+inline hashval_t
+biv_entry_hasher::hash (const value_type *b)
+{
+ return b->regno;
+}
+
+/* Compares biv B and register R. */
+
+inline bool
+biv_entry_hasher::equal (const value_type *b, const compare_type *r)
+{
+ return b->regno == REGNO (r);
+}
+
/* Bivs of the current loop. */
-static htab_t bivs;
+static hash_table <biv_entry_hasher> bivs;
static bool iv_analyze_op (rtx, rtx, struct rtx_iv *);
static void
check_iv_ref_table_size (void)
{
- if (iv_ref_table_size < DF_DEFS_TABLE_SIZE())
+ 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);
}
}
- htab_empty (bivs);
+ bivs.empty ();
}
-/* Returns hash value for biv B. */
-
-static hashval_t
-biv_hash (const void *b)
-{
- return ((const struct biv_entry *) b)->regno;
-}
-
-/* Compares biv B and register R. */
-
-static int
-biv_eq (const void *b, const void *r)
-{
- return ((const struct biv_entry *) b)->regno == REGNO ((const_rtx) r);
-}
/* Prepare the data for an induction variable analysis of a LOOP. */
void
iv_analysis_loop_init (struct loop *loop)
{
- basic_block *body = get_loop_body_in_dom_order (loop), bb;
- bitmap blocks = BITMAP_ALLOC (NULL);
- unsigned i;
-
current_loop = loop;
/* Clear the information from the analysis of the previous loop. */
if (clean_slate)
{
df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
- bivs = htab_create (10, biv_hash, biv_eq, free);
+ bivs.create (10);
clean_slate = false;
}
else
clear_iv_info ();
- for (i = 0; i < loop->num_nodes; i++)
- {
- bb = body[i];
- bitmap_set_bit (blocks, bb->index);
- }
/* 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_set_flags (DF_RD_PRUNE_DEAD_DEFS);
df_chain_add_problem (DF_UD_CHAIN);
df_note_add_problem ();
- df_set_blocks (blocks);
- df_analyze ();
+ df_analyze_loop (loop);
if (dump_file)
df_dump_region (dump_file);
check_iv_ref_table_size ();
- BITMAP_FREE (blocks);
- free (body);
}
/* Finds the definition of REG that dominates loop latch and stores
&& !iv->first_special)
{
rtx val = get_iv_value (iv, const0_rtx);
- val = lowpart_subreg (mode, val, iv->extend_mode);
+ val = lowpart_subreg (mode, val,
+ iv->extend == IV_UNKNOWN_EXTEND
+ ? iv->mode : iv->extend_mode);
iv->base = val;
iv->extend = IV_UNKNOWN_EXTEND;
&& !iv->first_special)
{
rtx val = get_iv_value (iv, const0_rtx);
+ if (iv->extend_mode != iv->mode
+ && iv->extend != IV_UNKNOWN_EXTEND
+ && iv->extend != extend)
+ val = lowpart_subreg (iv->mode, val, iv->extend_mode);
val = simplify_gen_unary (iv_extend_to_rtx_code (extend), mode,
- val, iv->extend_mode);
+ val,
+ iv->extend == extend
+ ? iv->extend_mode : iv->mode);
iv->base = val;
iv->extend = IV_UNKNOWN_EXTEND;
iv->mode = iv->extend_mode = mode;
static bool
analyzed_for_bivness_p (rtx def, struct rtx_iv *iv)
{
- struct biv_entry *biv =
- (struct biv_entry *) htab_find_with_hash (bivs, def, REGNO (def));
+ struct biv_entry *biv = bivs.find_with_hash (def, REGNO (def));
if (!biv)
return false;
record_biv (rtx def, struct rtx_iv *iv)
{
struct biv_entry *biv = XNEW (struct biv_entry);
- void **slot = htab_find_slot_with_hash (bivs, def, REGNO (def), INSERT);
+ biv_entry **slot = bivs.find_slot_with_hash (def, REGNO (def), INSERT);
biv->regno = REGNO (def);
biv->iv = *iv;
clear_iv_info ();
clean_slate = true;
df_finish_pass (true);
- htab_delete (bivs);
+ bivs.dispose ();
free (iv_ref_table);
iv_ref_table = NULL;
iv_ref_table_size = 0;
- bivs = NULL;
}
}
rtx op0, op1, opb0, opb1, r;
enum machine_mode mode;
+ if (rtx_equal_p (a, b))
+ return true;
+
if (GET_CODE (a) == EQ)
{
op0 = XEXP (a, 0);
op1 = XEXP (a, 1);
- if (REG_P (op0))
+ if (REG_P (op0)
+ || (GET_CODE (op0) == SUBREG
+ && REG_P (SUBREG_REG (op0))))
{
r = simplify_replace_rtx (b, op0, op1);
if (r == const_true_rtx)
return true;
}
- if (REG_P (op1))
+ if (REG_P (op1)
+ || (GET_CODE (op1) == SUBREG
+ && REG_P (SUBREG_REG (op1))))
{
r = simplify_replace_rtx (b, op1, op0);
if (r == const_true_rtx)
return;
e = loop_preheader_edge (loop);
- if (e->src == ENTRY_BLOCK_PTR)
+ if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
return;
altered = ALLOC_REG_SET (®_obstack);
note_stores (PATTERN (insn), mark_altered, this_altered);
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))
- SET_REGNO_REG_SET (this_altered, i);
+ unsigned int i;
+ hard_reg_set_iterator hrsi;
+ EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call,
+ 0, i, hrsi)
+ SET_REGNO_REG_SET (this_altered, i);
}
if (suitable_set_for_replacement (insn, &dest, &src))
}
}
else
- /* If we did not use this insn to make a replacement, any overlap
- between stores in this insn and our expression will cause the
- expression to become invalid. */
- if (for_each_rtx (expr, altered_reg_used, this_altered))
- goto out;
+ {
+ rtx *pnote, *pnote_next;
+
+ /* If we did not use this insn to make a replacement, any overlap
+ between stores in this insn and our expression will cause the
+ expression to become invalid. */
+ if (for_each_rtx (expr, altered_reg_used, this_altered))
+ goto out;
+
+ /* Likewise for the conditions. */
+ for (pnote = &cond_list; *pnote; pnote = pnote_next)
+ {
+ rtx note = *pnote;
+ rtx old_cond = XEXP (note, 0);
+
+ pnote_next = &XEXP (note, 1);
+ if (for_each_rtx (&old_cond, altered_reg_used, this_altered))
+ {
+ *pnote = *pnote_next;
+ pnote_next = pnote;
+ free_EXPR_LIST_node (note);
+ }
+ }
+ }
if (CONSTANT_P (*expr))
goto out;
}
if (!single_pred_p (e->src)
- || single_pred (e->src) == ENTRY_BLOCK_PTR)
+ || single_pred (e->src) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
break;
e = single_pred_edge (e->src);
}
rtx niter = desc->niter_expr;
rtx mmin, mmax, cmp;
unsigned HOST_WIDEST_INT nmax, inc;
+ unsigned HOST_WIDEST_INT andmax = 0;
+
+ /* We used to look for constant operand 0 of AND,
+ but canonicalization should always make this impossible. */
+ gcc_checking_assert (GET_CODE (niter) != AND
+ || !CONST_INT_P (XEXP (niter, 0)));
if (GET_CODE (niter) == AND
- && CONST_INT_P (XEXP (niter, 0)))
+ && CONST_INT_P (XEXP (niter, 1)))
{
- nmax = INTVAL (XEXP (niter, 0));
- if (!(nmax & (nmax + 1)))
- return nmax;
+ andmax = UINTVAL (XEXP (niter, 1));
+ niter = XEXP (niter, 0);
}
get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
if (dump_file)
fprintf (dump_file, ";; improved upper bound by one.\n");
}
- return nmax / inc;
+ nmax /= inc;
+ if (andmax)
+ nmax = MIN (nmax, andmax);
+ if (dump_file)
+ fprintf (dump_file, ";; Determined upper bound "HOST_WIDEST_INT_PRINT_DEC".\n",
+ nmax);
+ return nmax;
}
/* Computes number of iterations of the CONDITION in INSN in LOOP and stores
desc->const_iter = false;
desc->niter_expr = NULL_RTX;
- desc->niter_max = 0;
- if (loop->any_upper_bound
- && double_int_fits_in_uhwi_p (loop->nb_iterations_upper_bound))
- desc->niter_max = loop->nb_iterations_upper_bound.low;
cond = GET_CODE (condition);
gcc_assert (COMPARISON_P (condition));
iv1.step = const0_rtx;
}
+ iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
+ iv1.step = lowpart_subreg (mode, iv1.step, comp_mode);
+
/* This is either infinite loop or the one that ends immediately, depending
on initial values. Unswitching should remove this kind of conditions. */
if (iv0.step == const0_rtx && iv1.step == const0_rtx)
step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
else
step = iv0.step;
+ step = lowpart_subreg (mode, step, comp_mode);
delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
delta = lowpart_subreg (mode, delta, comp_mode);
delta = simplify_gen_binary (UMOD, mode, delta, step);
? iv0.base
: mode_mmin);
max = (up - down) / inc + 1;
- if (!desc->niter_max
- || max < desc->niter_max)
- desc->niter_max = max;
+ if (!desc->infinite
+ && !desc->assumptions)
+ record_niter_bound (loop, double_int::from_uhwi (max),
+ false, true);
if (iv0.step == const0_rtx)
{
bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
- tmp = simplify_gen_binary (UMOD, mode, tmp1, GEN_INT (d));
+ tmp = simplify_gen_binary (UMOD, mode, tmp1, gen_int_mode (d, mode));
assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
- tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
+ tmp = simplify_gen_binary (UDIV, mode, tmp1, gen_int_mode (d, mode));
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);
unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
desc->const_iter = true;
- desc->niter_max = desc->niter = val & GET_MODE_MASK (desc->mode);
+ desc->niter = val & GET_MODE_MASK (desc->mode);
+ if (!desc->infinite
+ && !desc->assumptions)
+ record_niter_bound (loop, double_int::from_uhwi (desc->niter),
+ false, true);
}
else
{
max = determine_max_iter (loop, desc, old_niter);
- if (!desc->niter_max
- || max < desc->niter_max)
- desc->niter_max = max;
+ if (!max)
+ goto zero_iter_simplify;
+ if (!desc->infinite
+ && !desc->assumptions)
+ record_niter_bound (loop, double_int::from_uhwi (max),
+ false, true);
/* simplify_using_initial_values does a copy propagation on the registers
in the expression for the number of iterations. This prolongs life
zero_iter:
desc->const_iter = true;
desc->niter = 0;
- desc->niter_max = 0;
+ record_niter_bound (loop, double_int_zero,
+ true, true);
desc->noloop_assumptions = NULL_RTX;
desc->niter_expr = const0_rtx;
return;
print_rtl (dump_file, desc->niter_expr);
fprintf (dump_file, "\n");
- fprintf (dump_file, " upper bound: ");
- fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter_max);
- fprintf (dump_file, "\n");
+ fprintf (dump_file, " upper bound: %li\n",
+ (long)get_max_loop_iterations_int (loop));
+ fprintf (dump_file, " realistic bound: %li\n",
+ (long)get_estimated_loop_iterations_int (loop));
}
else
fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
/* At least desc->infinite is not always initialized by
find_simple_loop_exit. */
- desc = XCNEW (struct niter_desc);
+ desc = ggc_alloc_cleared_niter_desc ();
iv_analysis_loop_init (loop);
find_simple_exit (loop, desc);
- loop->aux = desc;
+ loop->simple_loop_desc = desc;
if (desc->simple_p && (desc->assumptions || desc->infinite))
{
if (!desc)
return;
- free (desc);
- loop->aux = NULL;
+ ggc_free (desc);
+ loop->simple_loop_desc = NULL;
}
projects / gcc.git / blobdiff