/* Common subexpression elimination library for GNU compiler.
Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008
+ 1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008, 2009
Free Software Foundation, Inc.
This file is part of GCC.
#include "output.h"
#include "ggc.h"
#include "hashtab.h"
+#include "tree-pass.h"
#include "cselib.h"
#include "params.h"
#include "alloc-pool.h"
static int discard_useless_locs (void **, void *);
static int discard_useless_values (void **, void *);
static void remove_useless_values (void);
-static rtx wrap_constant (enum machine_mode, rtx);
static unsigned int cselib_hash_rtx (rtx, int);
-static cselib_val *new_cselib_val (unsigned int, enum machine_mode);
+static cselib_val *new_cselib_val (unsigned int, enum machine_mode, rtx);
static void add_mem_for_addr (cselib_val *, cselib_val *, rtx);
static cselib_val *cselib_lookup_mem (rtx, int);
static void cselib_invalidate_regno (unsigned int, enum machine_mode);
static void cselib_record_set (rtx, cselib_val *, cselib_val *);
static void cselib_record_sets (rtx);
+struct expand_value_data
+{
+ bitmap regs_active;
+ cselib_expand_callback callback;
+ void *callback_arg;
+};
+
+static rtx cselib_expand_value_rtx_1 (rtx, struct expand_value_data *, int);
+
/* There are three ways in which cselib can look up an rtx:
- for a REG, the reg_values table (which is indexed by regno) is used
- for a MEM, we recursively look up its address and then follow the
/* If nonnull, cselib will call this function before freeing useless
VALUEs. A VALUE is deemed useless if its "locs" field is null. */
void (*cselib_discard_hook) (cselib_val *);
+
+/* If nonnull, cselib will call this function before recording sets or
+ even clobbering outputs of INSN. All the recorded sets will be
+ represented in the array sets[n_sets]. new_val_min can be used to
+ tell whether values present in sets are introduced by this
+ instruction. */
+void (*cselib_record_sets_hook) (rtx insn, struct cselib_set *sets,
+ int n_sets);
+
+#define PRESERVED_VALUE_P(RTX) \
+ (RTL_FLAG_CHECK1("PRESERVED_VALUE_P", (RTX), VALUE)->unchanging)
+#define LONG_TERM_PRESERVED_VALUE_P(RTX) \
+ (RTL_FLAG_CHECK1("LONG_TERM_PRESERVED_VALUE_P", (RTX), VALUE)->in_struct)
+
\f
/* Allocate a struct elt_list and fill in its two elements with the
}
/* Remove all entries from the hash table. Also used during
- initialization. If CLEAR_ALL isn't set, then only clear the entries
- which are known to have been used. */
+ initialization. */
void
cselib_clear_table (void)
{
+ cselib_reset_table_with_next_value (0);
+}
+
+/* Remove all entries from the hash table, arranging for the next
+ value to be numbered NUM. */
+
+void
+cselib_reset_table_with_next_value (unsigned int num)
+{
unsigned int i;
for (i = 0; i < n_used_regs; i++)
n_used_regs = 0;
+ /* ??? Preserve constants? */
htab_empty (cselib_hash_table);
n_useless_values = 0;
- next_unknown_value = 0;
+ next_unknown_value = num;
first_containing_mem = &dummy_val;
}
+/* Return the number of the next value that will be generated. */
+
+unsigned int
+cselib_get_next_unknown_value (void)
+{
+ return next_unknown_value;
+}
+
/* The equality test for our hash table. The first argument ENTRY is a table
element (i.e. a cselib_val), while the second arg X is an rtx. We know
that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
rtx x = CONST_CAST_RTX ((const_rtx)x_arg);
enum machine_mode mode = GET_MODE (x);
- gcc_assert (GET_CODE (x) != CONST_INT && GET_CODE (x) != CONST_FIXED
+ gcc_assert (!CONST_INT_P (x) && GET_CODE (x) != CONST_FIXED
&& (mode != VOIDmode || GET_CODE (x) != CONST_DOUBLE));
if (mode != GET_MODE (v->val_rtx))
/* Unwrap X if necessary. */
if (GET_CODE (x) == CONST
- && (GET_CODE (XEXP (x, 0)) == CONST_INT
+ && (CONST_INT_P (XEXP (x, 0))
|| GET_CODE (XEXP (x, 0)) == CONST_FIXED
|| GET_CODE (XEXP (x, 0)) == CONST_DOUBLE))
x = XEXP (x, 0);
p = &(*p)->next;
}
- if (had_locs && v->locs == 0)
+ if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
{
n_useless_values++;
values_became_useless = 1;
{
cselib_val *v = (cselib_val *)*x;
- if (v->locs == 0)
+ if (v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
{
if (cselib_discard_hook)
cselib_discard_hook (v);
gcc_assert (!n_useless_values);
}
+/* Arrange for a value to not be removed from the hash table even if
+ it becomes useless. */
+
+void
+cselib_preserve_value (cselib_val *v)
+{
+ PRESERVED_VALUE_P (v->val_rtx) = 1;
+}
+
+/* Test whether a value is preserved. */
+
+bool
+cselib_preserved_value_p (cselib_val *v)
+{
+ return PRESERVED_VALUE_P (v->val_rtx);
+}
+
+/* Mark preserved values as preserved for the long term. */
+
+static int
+cselib_preserve_definitely (void **slot, void *info ATTRIBUTE_UNUSED)
+{
+ cselib_val *v = (cselib_val *)*slot;
+
+ if (PRESERVED_VALUE_P (v->val_rtx)
+ && !LONG_TERM_PRESERVED_VALUE_P (v->val_rtx))
+ LONG_TERM_PRESERVED_VALUE_P (v->val_rtx) = true;
+
+ return 1;
+}
+
+/* Clear the preserve marks for values not preserved for the long
+ term. */
+
+static int
+cselib_clear_preserve (void **slot, void *info ATTRIBUTE_UNUSED)
+{
+ cselib_val *v = (cselib_val *)*slot;
+
+ if (PRESERVED_VALUE_P (v->val_rtx)
+ && !LONG_TERM_PRESERVED_VALUE_P (v->val_rtx))
+ {
+ PRESERVED_VALUE_P (v->val_rtx) = false;
+ if (!v->locs)
+ n_useless_values++;
+ }
+
+ return 1;
+}
+
+/* Clean all non-constant expressions in the hash table, but retain
+ their values. */
+
+void
+cselib_preserve_only_values (bool retain)
+{
+ int i;
+
+ htab_traverse (cselib_hash_table,
+ retain ? cselib_preserve_definitely : cselib_clear_preserve,
+ NULL);
+
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ cselib_invalidate_regno (i, reg_raw_mode[i]);
+
+ cselib_invalidate_mem (callmem);
+
+ remove_useless_values ();
+
+ gcc_assert (first_containing_mem == &dummy_val);
+}
+
/* Return the mode in which a register was last set. If X is not a
register, return its mode. If the mode in which the register was
set is not known, or the value was already clobbered, return
return 1;
}
-/* We need to pass down the mode of constants through the hash table
- functions. For that purpose, wrap them in a CONST of the appropriate
- mode. */
-static rtx
-wrap_constant (enum machine_mode mode, rtx x)
-{
- if (GET_CODE (x) != CONST_INT && GET_CODE (x) != CONST_FIXED
- && (GET_CODE (x) != CONST_DOUBLE || GET_MODE (x) != VOIDmode))
- return x;
- gcc_assert (mode != VOIDmode);
- return gen_rtx_CONST (mode, x);
-}
-
/* Hash an rtx. Return 0 if we couldn't hash the rtx.
For registers and memory locations, we look up their cselib_val structure
and return its VALUE element.
value is MODE. */
static inline cselib_val *
-new_cselib_val (unsigned int value, enum machine_mode mode)
+new_cselib_val (unsigned int value, enum machine_mode mode, rtx x)
{
cselib_val *e = (cselib_val *) pool_alloc (cselib_val_pool);
e->addr_list = 0;
e->locs = 0;
e->next_containing_mem = 0;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "cselib value %u ", value);
+ if (flag_dump_noaddr || flag_dump_unnumbered)
+ fputs ("# ", dump_file);
+ else
+ fprintf (dump_file, "%p ", (void*)e);
+ print_rtl_single (dump_file, x);
+ fputc ('\n', dump_file);
+ }
+
return e;
}
if (! create)
return 0;
- mem_elt = new_cselib_val (++next_unknown_value, mode);
+ mem_elt = new_cselib_val (++next_unknown_value, mode, x);
add_mem_for_addr (addr, mem_elt, x);
slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
mem_elt->value, INSERT);
expand to the same place. */
static rtx
-expand_loc (struct elt_loc_list *p, bitmap regs_active, int max_depth)
+expand_loc (struct elt_loc_list *p, struct expand_value_data *evd,
+ int max_depth)
{
rtx reg_result = NULL;
unsigned int regno = UINT_MAX;
the same reg. */
if ((REG_P (p->loc))
&& (REGNO (p->loc) < regno)
- && !bitmap_bit_p (regs_active, REGNO (p->loc)))
+ && !bitmap_bit_p (evd->regs_active, REGNO (p->loc)))
{
reg_result = p->loc;
regno = REGNO (p->loc);
else if (!REG_P (p->loc))
{
rtx result, note;
- if (dump_file)
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
print_inline_rtx (dump_file, p->loc, 0);
fprintf (dump_file, "\n");
&& (note = find_reg_note (p->setting_insn, REG_EQUAL, NULL_RTX))
&& XEXP (note, 0) == XEXP (p->loc, 1))
return XEXP (p->loc, 1);
- result = cselib_expand_value_rtx (p->loc, regs_active, max_depth - 1);
+ result = cselib_expand_value_rtx_1 (p->loc, evd, max_depth - 1);
if (result)
return result;
}
if (regno != UINT_MAX)
{
rtx result;
- if (dump_file)
+ if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "r%d\n", regno);
- result = cselib_expand_value_rtx (reg_result, regs_active, max_depth - 1);
+ result = cselib_expand_value_rtx_1 (reg_result, evd, max_depth - 1);
if (result)
return result;
}
- if (dump_file)
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
if (reg_result)
{
rtx
cselib_expand_value_rtx (rtx orig, bitmap regs_active, int max_depth)
{
+ struct expand_value_data evd;
+
+ evd.regs_active = regs_active;
+ evd.callback = NULL;
+ evd.callback_arg = NULL;
+
+ return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
+}
+
+/* Same as cselib_expand_value_rtx, but using a callback to try to
+ resolve some expressions. The CB function should return ORIG if it
+ can't or does not want to deal with a certain RTX. Any other
+ return value, including NULL, will be used as the expansion for
+ VALUE, without any further changes. */
+
+rtx
+cselib_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth,
+ cselib_expand_callback cb, void *data)
+{
+ struct expand_value_data evd;
+
+ evd.regs_active = regs_active;
+ evd.callback = cb;
+ evd.callback_arg = data;
+
+ return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
+}
+
+/* Internal implementation of cselib_expand_value_rtx and
+ cselib_expand_value_rtx_cb. */
+
+static rtx
+cselib_expand_value_rtx_1 (rtx orig, struct expand_value_data *evd,
+ int max_depth)
+{
rtx copy, scopy;
int i, j;
RTX_CODE code;
|| regno == HARD_FRAME_POINTER_REGNUM)
return orig;
- bitmap_set_bit (regs_active, regno);
+ bitmap_set_bit (evd->regs_active, regno);
- if (dump_file)
+ if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "expanding: r%d into: ", regno);
- result = expand_loc (l->elt->locs, regs_active, max_depth);
- bitmap_clear_bit (regs_active, regno);
+ result = expand_loc (l->elt->locs, evd, max_depth);
+ bitmap_clear_bit (evd->regs_active, regno);
if (result)
return result;
case SUBREG:
{
- rtx subreg = cselib_expand_value_rtx (SUBREG_REG (orig), regs_active,
- max_depth - 1);
+ rtx subreg;
+
+ if (evd->callback)
+ {
+ subreg = evd->callback (orig, evd->regs_active, max_depth,
+ evd->callback_arg);
+ if (subreg != orig)
+ return subreg;
+ }
+
+ subreg = cselib_expand_value_rtx_1 (SUBREG_REG (orig), evd,
+ max_depth - 1);
if (!subreg)
return NULL;
scopy = simplify_gen_subreg (GET_MODE (orig), subreg,
|| (GET_CODE (scopy) == SUBREG
&& !REG_P (SUBREG_REG (scopy))
&& !MEM_P (SUBREG_REG (scopy))))
- return shallow_copy_rtx (orig);
+ return NULL;
+
return scopy;
}
case VALUE:
- if (dump_file)
- fprintf (dump_file, "expanding value %s into: ",
- GET_MODE_NAME (GET_MODE (orig)));
+ {
+ rtx result;
- return expand_loc (CSELIB_VAL_PTR (orig)->locs, regs_active, max_depth);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fputs ("\nexpanding ", dump_file);
+ print_rtl_single (dump_file, orig);
+ fputs (" into...", dump_file);
+ }
+ if (evd->callback)
+ {
+ result = evd->callback (orig, evd->regs_active, max_depth,
+ evd->callback_arg);
+
+ if (result != orig)
+ return result;
+ }
+
+ result = expand_loc (CSELIB_VAL_PTR (orig)->locs, evd, max_depth);
+ return result;
+ }
default:
break;
}
case 'e':
if (XEXP (orig, i) != NULL)
{
- rtx result = cselib_expand_value_rtx (XEXP (orig, i), regs_active, max_depth - 1);
+ rtx result = cselib_expand_value_rtx_1 (XEXP (orig, i), evd,
+ max_depth - 1);
if (!result)
return NULL;
XEXP (copy, i) = result;
XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
for (j = 0; j < XVECLEN (copy, i); j++)
{
- rtx result = cselib_expand_value_rtx (XVECEXP (orig, i, j), regs_active, max_depth - 1);
+ rtx result = cselib_expand_value_rtx_1 (XVECEXP (orig, i, j),
+ evd, max_depth - 1);
if (!result)
return NULL;
XVECEXP (copy, i, j) = result;
{
XEXP (copy, 0)
= gen_rtx_CONST (GET_MODE (XEXP (orig, 0)), XEXP (copy, 0));
- if (dump_file)
+ if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " wrapping const_int result in const to preserve mode %s\n",
GET_MODE_NAME (GET_MODE (XEXP (copy, 0))));
}
scopy = simplify_rtx (copy);
if (scopy)
- return scopy;
+ {
+ if (GET_MODE (copy) != GET_MODE (scopy))
+ scopy = wrap_constant (GET_MODE (copy), scopy);
+ return scopy;
+ }
return copy;
}
{
/* This happens for autoincrements. Assign a value that doesn't
match any other. */
- e = new_cselib_val (++next_unknown_value, GET_MODE (x));
+ e = new_cselib_val (++next_unknown_value, GET_MODE (x), x);
}
return e->val_rtx;
case PRE_DEC:
case POST_MODIFY:
case PRE_MODIFY:
- e = new_cselib_val (++next_unknown_value, GET_MODE (x));
+ e = new_cselib_val (++next_unknown_value, GET_MODE (x), x);
return e->val_rtx;
default:
return copy;
}
+/* Log a lookup of X to the cselib table along with the result RET. */
+
+static cselib_val *
+cselib_log_lookup (rtx x, cselib_val *ret)
+{
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fputs ("cselib lookup ", dump_file);
+ print_inline_rtx (dump_file, x, 2);
+ fprintf (dump_file, " => %u\n", ret ? ret->value : 0);
+ }
+
+ return ret;
+}
+
/* Look up the rtl expression X in our tables and return the value it has.
If CREATE is zero, we return NULL if we don't know the value. Otherwise,
we create a new one if possible, using mode MODE if X doesn't have a mode
l = l->next;
for (; l; l = l->next)
if (mode == GET_MODE (l->elt->val_rtx))
- return l->elt;
+ return cselib_log_lookup (x, l->elt);
if (! create)
- return 0;
+ return cselib_log_lookup (x, 0);
if (i < FIRST_PSEUDO_REGISTER)
{
max_value_regs = n;
}
- e = new_cselib_val (++next_unknown_value, GET_MODE (x));
+ e = new_cselib_val (++next_unknown_value, GET_MODE (x), x);
e->locs = new_elt_loc_list (e->locs, x);
if (REG_VALUES (i) == 0)
{
REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e);
slot = htab_find_slot_with_hash (cselib_hash_table, x, e->value, INSERT);
*slot = e;
- return e;
+ return cselib_log_lookup (x, e);
}
if (MEM_P (x))
- return cselib_lookup_mem (x, create);
+ return cselib_log_lookup (x, cselib_lookup_mem (x, create));
hashval = cselib_hash_rtx (x, create);
/* Can't even create if hashing is not possible. */
if (! hashval)
- return 0;
+ return cselib_log_lookup (x, 0);
slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
hashval, create ? INSERT : NO_INSERT);
if (slot == 0)
- return 0;
+ return cselib_log_lookup (x, 0);
e = (cselib_val *) *slot;
if (e)
- return e;
+ return cselib_log_lookup (x, e);
- e = new_cselib_val (hashval, mode);
+ e = new_cselib_val (hashval, mode, x);
/* We have to fill the slot before calling cselib_subst_to_values:
the hash table is inconsistent until we do so, and
cselib_subst_to_values will need to do lookups. */
*slot = (void *) e;
e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
- return e;
+ return cselib_log_lookup (x, e);
}
/* Invalidate any entries in reg_values that overlap REGNO. This is called
break;
}
}
- if (v->locs == 0)
+ if (v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
n_useless_values++;
}
}
}
if (num_mems < PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS)
&& ! canon_true_dependence (mem_rtx, GET_MODE (mem_rtx), mem_addr,
- x, cselib_rtx_varies_p))
+ x, NULL_RTX, cselib_rtx_varies_p))
{
has_mem = true;
num_mems++;
unchain_one_elt_loc_list (p);
}
- if (had_locs && v->locs == 0)
+ if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
n_useless_values++;
next = v->next_containing_mem;
REG_VALUES (dreg)->elt = src_elt;
}
- if (src_elt->locs == 0)
+ if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx))
n_useless_values--;
src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
}
else if (MEM_P (dest) && dest_addr_elt != 0
&& cselib_record_memory)
{
- if (src_elt->locs == 0)
+ if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx))
n_useless_values--;
add_mem_for_addr (dest_addr_elt, src_elt, dest);
}
}
-/* Describe a single set that is part of an insn. */
-struct set
-{
- rtx src;
- rtx dest;
- cselib_val *src_elt;
- cselib_val *dest_addr_elt;
-};
-
/* There is no good way to determine how many elements there can be
in a PARALLEL. Since it's fairly cheap, use a really large number. */
#define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
{
int n_sets = 0;
int i;
- struct set sets[MAX_SETS];
+ struct cselib_set sets[MAX_SETS];
rtx body = PATTERN (insn);
rtx cond = 0;
}
}
+ if (cselib_record_sets_hook)
+ cselib_record_sets_hook (insn, sets, n_sets);
+
/* Invalidate all locations written by this insn. Note that the elts we
looked up in the previous loop aren't affected, just some of their
locations may go away. */
&& GET_CODE (PATTERN (insn)) == ASM_OPERANDS
&& MEM_VOLATILE_P (PATTERN (insn))))
{
- cselib_clear_table ();
+ cselib_reset_table_with_next_value (next_unknown_value);
return;
}
next_unknown_value = 0;
}
+/* Dump the cselib_val *X to FILE *info. */
+
+static int
+dump_cselib_val (void **x, void *info)
+{
+ cselib_val *v = (cselib_val *)*x;
+ FILE *out = (FILE *)info;
+ bool need_lf = true;
+
+ print_inline_rtx (out, v->val_rtx, 0);
+
+ if (v->locs)
+ {
+ struct elt_loc_list *l = v->locs;
+ if (need_lf)
+ {
+ fputc ('\n', out);
+ need_lf = false;
+ }
+ fputs (" locs:", out);
+ do
+ {
+ fprintf (out, "\n from insn %i ",
+ INSN_UID (l->setting_insn));
+ print_inline_rtx (out, l->loc, 4);
+ }
+ while ((l = l->next));
+ fputc ('\n', out);
+ }
+ else
+ {
+ fputs (" no locs", out);
+ need_lf = true;
+ }
+
+ if (v->addr_list)
+ {
+ struct elt_list *e = v->addr_list;
+ if (need_lf)
+ {
+ fputc ('\n', out);
+ need_lf = false;
+ }
+ fputs (" addr list:", out);
+ do
+ {
+ fputs ("\n ", out);
+ print_inline_rtx (out, e->elt->val_rtx, 2);
+ }
+ while ((e = e->next));
+ fputc ('\n', out);
+ }
+ else
+ {
+ fputs (" no addrs", out);
+ need_lf = true;
+ }
+
+ if (v->next_containing_mem == &dummy_val)
+ fputs (" last mem\n", out);
+ else if (v->next_containing_mem)
+ {
+ fputs (" next mem ", out);
+ print_inline_rtx (out, v->next_containing_mem->val_rtx, 2);
+ fputc ('\n', out);
+ }
+ else if (need_lf)
+ fputc ('\n', out);
+
+ return 1;
+}
+
+/* Dump to OUT everything in the CSELIB table. */
+
+void
+dump_cselib_table (FILE *out)
+{
+ fprintf (out, "cselib hash table:\n");
+ htab_traverse (cselib_hash_table, dump_cselib_val, out);
+ if (first_containing_mem != &dummy_val)
+ {
+ fputs ("first mem ", out);
+ print_inline_rtx (out, first_containing_mem->val_rtx, 2);
+ fputc ('\n', out);
+ }
+ fprintf (out, "last unknown value %i\n", next_unknown_value);
+}
+
#include "gt-cselib.h"
OSDN Git Service
