/* 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 Free Software Foundation, Inc.
+ 1999, 2000, 2001, 2003, 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 later
+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
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/>. */
#include "config.h"
#include "system.h"
each time memory is invalidated. */
static cselib_val *first_containing_mem = &dummy_val;
static alloc_pool elt_loc_list_pool, elt_list_pool, cselib_val_pool, value_pool;
+
+/* 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 *);
\f
/* Allocate a struct elt_list and fill in its two elements with the
entry_and_rtx_equal_p (const void *entry, const void *x_arg)
{
struct elt_loc_list *l;
- const cselib_val *v = (const cselib_val *) entry;
+ const cselib_val *const v = (const cselib_val *) entry;
rtx x = (rtx) x_arg;
enum machine_mode mode = GET_MODE (x);
- gcc_assert (GET_CODE (x) != CONST_INT
+ gcc_assert (GET_CODE (x) != CONST_INT && GET_CODE (x) != CONST_FIXED
&& (mode != VOIDmode || GET_CODE (x) != CONST_DOUBLE));
- if (mode != GET_MODE (v->u.val_rtx))
+ if (mode != GET_MODE (v->val_rtx))
return 0;
/* Unwrap X if necessary. */
if (GET_CODE (x) == CONST
&& (GET_CODE (XEXP (x, 0)) == CONST_INT
+ || GET_CODE (XEXP (x, 0)) == CONST_FIXED
|| GET_CODE (XEXP (x, 0)) == CONST_DOUBLE))
x = XEXP (x, 0);
static hashval_t
get_value_hash (const void *entry)
{
- const cselib_val *v = (const cselib_val *) entry;
+ const cselib_val *const v = (const cselib_val *) entry;
return v->value;
}
removed. */
int
-references_value_p (rtx x, int only_useless)
+references_value_p (const_rtx x, int only_useless)
{
- enum rtx_code code = GET_CODE (x);
+ const enum rtx_code code = GET_CODE (x);
const char *fmt = GET_RTX_FORMAT (code);
int i, j;
if (v->locs == 0)
{
- CSELIB_VAL_PTR (v->u.val_rtx) = NULL;
+ if (cselib_discard_hook)
+ cselib_discard_hook (v);
+
+ CSELIB_VAL_PTR (v->val_rtx) = NULL;
htab_clear_slot (cselib_hash_table, x);
unchain_one_value (v);
n_useless_values--;
VOIDmode. */
enum machine_mode
-cselib_reg_set_mode (rtx x)
+cselib_reg_set_mode (const_rtx x)
{
if (!REG_P (x))
return GET_MODE (x);
|| REG_VALUES (REGNO (x))->elt == NULL)
return VOIDmode;
- return GET_MODE (REG_VALUES (REGNO (x))->elt->u.val_rtx);
+ return GET_MODE (REG_VALUES (REGNO (x))->elt->val_rtx);
}
/* Return nonzero if we can prove that X and Y contain the same value, taking
cselib_val *e = cselib_lookup (x, GET_MODE (x), 0);
if (e)
- x = e->u.val_rtx;
+ x = e->val_rtx;
}
if (REG_P (y) || MEM_P (y))
cselib_val *e = cselib_lookup (y, GET_MODE (y), 0);
if (e)
- y = e->u.val_rtx;
+ y = e->val_rtx;
}
if (x == y)
switch (GET_CODE (x))
{
case CONST_DOUBLE:
+ case CONST_FIXED:
return 0;
case LABEL_REF:
static rtx
wrap_constant (enum machine_mode mode, rtx x)
{
- if (GET_CODE (x) != CONST_INT
+ 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);
+ (unsigned) CONST_DOUBLE_HIGH (x));
return hash ? hash : (unsigned int) CONST_DOUBLE;
+ case CONST_FIXED:
+ hash += (unsigned int) code + (unsigned int) GET_MODE (x);
+ hash += fixed_hash (CONST_FIXED_VALUE (x));
+ return hash ? hash : (unsigned int) CONST_FIXED;
+
case CONST_VECTOR:
{
int units;
precisely when we can have VALUE RTXen (when cselib is active)
so we don't need to put them in garbage collected memory.
??? Why should a VALUE be an RTX in the first place? */
- e->u.val_rtx = pool_alloc (value_pool);
- memset (e->u.val_rtx, 0, RTX_HDR_SIZE);
- PUT_CODE (e->u.val_rtx, VALUE);
- PUT_MODE (e->u.val_rtx, mode);
- CSELIB_VAL_PTR (e->u.val_rtx) = e;
+ e->val_rtx = pool_alloc (value_pool);
+ memset (e->val_rtx, 0, RTX_HDR_SIZE);
+ PUT_CODE (e->val_rtx, VALUE);
+ PUT_MODE (e->val_rtx, mode);
+ CSELIB_VAL_PTR (e->val_rtx) = e;
e->addr_list = 0;
e->locs = 0;
e->next_containing_mem = 0;
addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
mem_elt->locs
= new_elt_loc_list (mem_elt->locs,
- replace_equiv_address_nv (x, addr_elt->u.val_rtx));
+ replace_equiv_address_nv (x, addr_elt->val_rtx));
if (mem_elt->next_containing_mem == NULL)
{
mem_elt->next_containing_mem = first_containing_mem;
/* Find a value that describes a value of our mode at that address. */
for (l = addr->addr_list; l; l = l->next)
- if (GET_MODE (l->elt->u.val_rtx) == mode)
+ if (GET_MODE (l->elt->val_rtx) == mode)
return l->elt;
if (! create)
return mem_elt;
}
+/* Search thru the possible substitutions in P. We prefer a non reg
+ substitution because this allows us to expand the tree further. If
+ we find, just a reg, take the lowest regno. There may be several
+ non-reg results, we just take the first one because they will all
+ expand to the same place. */
+
+static rtx
+expand_loc (struct elt_loc_list *p, bitmap regs_active, int max_depth)
+{
+ rtx reg_result = NULL;
+ unsigned int regno = UINT_MAX;
+ struct elt_loc_list *p_in = p;
+
+ for (; p; p = p -> next)
+ {
+ /* Avoid infinite recursion trying to expand a reg into a
+ the same reg. */
+ if ((REG_P (p->loc))
+ && (REGNO (p->loc) < regno)
+ && !bitmap_bit_p (regs_active, REGNO (p->loc)))
+ {
+ reg_result = p->loc;
+ regno = REGNO (p->loc);
+ }
+ /* Avoid infinite recursion and do not try to expand the
+ value. */
+ else if (GET_CODE (p->loc) == VALUE
+ && CSELIB_VAL_PTR (p->loc)->locs == p_in)
+ continue;
+ else if (!REG_P (p->loc))
+ {
+ rtx result;
+ if (dump_file)
+ {
+ print_inline_rtx (dump_file, p->loc, 0);
+ fprintf (dump_file, "\n");
+ }
+ result = cselib_expand_value_rtx (p->loc, regs_active, max_depth - 1);
+ if (result)
+ return result;
+ }
+
+ }
+
+ if (regno != UINT_MAX)
+ {
+ rtx result;
+ if (dump_file)
+ fprintf (dump_file, "r%d\n", regno);
+
+ result = cselib_expand_value_rtx (reg_result, regs_active, max_depth - 1);
+ if (result)
+ return result;
+ }
+
+ if (dump_file)
+ {
+ if (reg_result)
+ {
+ print_inline_rtx (dump_file, reg_result, 0);
+ fprintf (dump_file, "\n");
+ }
+ else
+ fprintf (dump_file, "NULL\n");
+ }
+ return reg_result;
+}
+
+
+/* Forward substitute and expand an expression out to its roots.
+ This is the opposite of common subexpression. Because local value
+ numbering is such a weak optimization, the expanded expression is
+ pretty much unique (not from a pointer equals point of view but
+ from a tree shape point of view.
+
+ This function returns NULL if the expansion fails. The expansion
+ will fail if there is no value number for one of the operands or if
+ one of the operands has been overwritten between the current insn
+ and the beginning of the basic block. For instance x has no
+ expansion in:
+
+ r1 <- r1 + 3
+ x <- r1 + 8
+
+ REGS_ACTIVE is a scratch bitmap that should be clear when passing in.
+ It is clear on return. */
+
+rtx
+cselib_expand_value_rtx (rtx orig, bitmap regs_active, int max_depth)
+{
+ rtx copy, scopy;
+ int i, j;
+ RTX_CODE code;
+ const char *format_ptr;
+
+ code = GET_CODE (orig);
+
+ /* For the context of dse, if we end up expand into a huge tree, we
+ will not have a useful address, so we might as well just give up
+ quickly. */
+ if (max_depth <= 0)
+ return NULL;
+
+ switch (code)
+ {
+ case REG:
+ {
+ struct elt_list *l = REG_VALUES (REGNO (orig));
+
+ if (l && l->elt == NULL)
+ l = l->next;
+ for (; l; l = l->next)
+ if (GET_MODE (l->elt->val_rtx) == GET_MODE (orig))
+ {
+ rtx result;
+ int regno = REGNO (orig);
+
+ /* The only thing that we are not willing to do (this
+ is requirement of dse and if others potential uses
+ need this function we should add a parm to control
+ it) is that we will not substitute the
+ STACK_POINTER_REGNUM, FRAME_POINTER or the
+ HARD_FRAME_POINTER.
+
+ These expansions confuses the code that notices that
+ stores into the frame go dead at the end of the
+ function and that the frame is not effected by calls
+ to subroutines. If you allow the
+ STACK_POINTER_REGNUM substitution, then dse will
+ think that parameter pushing also goes dead which is
+ wrong. If you allow the FRAME_POINTER or the
+ HARD_FRAME_POINTER then you lose the opportunity to
+ make the frame assumptions. */
+ if (regno == STACK_POINTER_REGNUM
+ || regno == FRAME_POINTER_REGNUM
+ || regno == HARD_FRAME_POINTER_REGNUM)
+ return orig;
+
+ bitmap_set_bit (regs_active, regno);
+
+ if (dump_file)
+ fprintf (dump_file, "expanding: r%d into: ", regno);
+
+ result = expand_loc (l->elt->locs, regs_active, max_depth);
+ bitmap_clear_bit (regs_active, regno);
+
+ if (result)
+ return result;
+ else
+ return orig;
+ }
+ }
+
+ case CONST_INT:
+ case CONST_DOUBLE:
+ case CONST_VECTOR:
+ case SYMBOL_REF:
+ case CODE_LABEL:
+ case PC:
+ case CC0:
+ case SCRATCH:
+ /* SCRATCH must be shared because they represent distinct values. */
+ return orig;
+ case CLOBBER:
+ if (REG_P (XEXP (orig, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig, 0))))
+ return orig;
+ break;
+
+ case CONST:
+ if (shared_const_p (orig))
+ return orig;
+ break;
+
+
+ case VALUE:
+ {
+ rtx result;
+ if (dump_file)
+ fprintf (dump_file, "expanding value %s into: ", GET_MODE_NAME (GET_MODE (orig)));
+
+ result = expand_loc (CSELIB_VAL_PTR (orig)->locs, regs_active, max_depth);
+ if (result
+ && GET_CODE (result) == CONST_INT
+ && GET_MODE (orig) != VOIDmode)
+ {
+ result = gen_rtx_CONST (GET_MODE (orig), result);
+ if (dump_file)
+ fprintf (dump_file, " wrapping const_int result in const to preserve mode %s\n",
+ GET_MODE_NAME (GET_MODE (orig)));
+ }
+ return result;
+ }
+ default:
+ break;
+ }
+
+ /* Copy the various flags, fields, and other information. We assume
+ that all fields need copying, and then clear the fields that should
+ not be copied. That is the sensible default behavior, and forces
+ us to explicitly document why we are *not* copying a flag. */
+ copy = shallow_copy_rtx (orig);
+
+ format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
+
+ for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
+ switch (*format_ptr++)
+ {
+ case 'e':
+ if (XEXP (orig, i) != NULL)
+ {
+ rtx result = cselib_expand_value_rtx (XEXP (orig, i), regs_active, max_depth - 1);
+ if (!result)
+ return NULL;
+ XEXP (copy, i) = result;
+ }
+ break;
+
+ case 'E':
+ case 'V':
+ if (XVEC (orig, i) != NULL)
+ {
+ 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);
+ if (!result)
+ return NULL;
+ XVECEXP (copy, i, j) = result;
+ }
+ }
+ break;
+
+ case 't':
+ case 'w':
+ case 'i':
+ case 's':
+ case 'S':
+ case 'T':
+ case 'u':
+ case 'B':
+ case '0':
+ /* These are left unchanged. */
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+
+ scopy = simplify_rtx (copy);
+ if (scopy)
+ return scopy;
+ return copy;
+}
+
/* Walk rtx X and replace all occurrences of REG and MEM subexpressions
with VALUE expressions. This way, it becomes independent of changes
to registers and memory.
if (l && l->elt == NULL)
l = l->next;
for (; l; l = l->next)
- if (GET_MODE (l->elt->u.val_rtx) == GET_MODE (x))
- return l->elt->u.val_rtx;
+ if (GET_MODE (l->elt->val_rtx) == GET_MODE (x))
+ return l->elt->val_rtx;
gcc_unreachable ();
match any other. */
e = new_cselib_val (++next_unknown_value, GET_MODE (x));
}
- return e->u.val_rtx;
+ return e->val_rtx;
case CONST_DOUBLE:
case CONST_VECTOR:
case CONST_INT:
+ case CONST_FIXED:
return x;
case POST_INC:
case POST_MODIFY:
case PRE_MODIFY:
e = new_cselib_val (++next_unknown_value, GET_MODE (x));
- return e->u.val_rtx;
+ return e->val_rtx;
default:
break;
if (l && l->elt == NULL)
l = l->next;
for (; l; l = l->next)
- if (mode == GET_MODE (l->elt->u.val_rtx))
+ if (mode == GET_MODE (l->elt->val_rtx))
return l->elt;
if (! create)
else
i = regno - max_value_regs;
- endregno = regno + hard_regno_nregs[regno][mode];
+ endregno = end_hard_regno (mode, regno);
}
else
{
unsigned int this_last = i;
if (i < FIRST_PSEUDO_REGISTER && v != NULL)
- this_last += hard_regno_nregs[i][GET_MODE (v->u.val_rtx)] - 1;
+ this_last = end_hard_regno (GET_MODE (v->val_rtx), i) - 1;
if (this_last < regno || v == NULL)
{
executions of the program. 0 means X can be compared reliably
against certain constants or near-constants. */
-static int
-cselib_rtx_varies_p (rtx x ATTRIBUTE_UNUSED, int from_alias ATTRIBUTE_UNUSED)
+static bool
+cselib_rtx_varies_p (const_rtx x ATTRIBUTE_UNUSED, bool from_alias ATTRIBUTE_UNUSED)
{
/* We actually don't need to verify very hard. This is because
if X has actually changed, we invalidate the memory anyway,
/* A wrapper for cselib_invalidate_rtx to be called via note_stores. */
static void
-cselib_invalidate_rtx_note_stores (rtx dest, rtx ignore ATTRIBUTE_UNUSED,
+cselib_invalidate_rtx_note_stores (rtx dest, const_rtx ignore ATTRIBUTE_UNUSED,
void *data ATTRIBUTE_UNUSED)
{
cselib_invalidate_rtx (dest);
if (call_used_regs[i]
|| (REG_VALUES (i) && REG_VALUES (i)->elt
&& HARD_REGNO_CALL_PART_CLOBBERED (i,
- GET_MODE (REG_VALUES (i)->elt->u.val_rtx))))
+ GET_MODE (REG_VALUES (i)->elt->val_rtx))))
cselib_invalidate_regno (i, reg_raw_mode[i]);
if (! CONST_OR_PURE_CALL_P (insn))
if (n_useless_values > MAX_USELESS_VALUES
/* remove_useless_values is linear in the hash table size. Avoid
- quadratic behaviour for very large hashtables with very few
+ quadratic behavior for very large hashtables with very few
useless elements. */
&& (unsigned int)n_useless_values > cselib_hash_table->n_elements / 4)
remove_useless_values ();
void
cselib_finish (void)
{
+ cselib_discard_hook = NULL;
free_alloc_pool (elt_list_pool);
free_alloc_pool (elt_loc_list_pool);
free_alloc_pool (cselib_val_pool);