/* Value Numbering routines for tree expressions.
- Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dan@dberlin.org>, Steven Bosscher
<stevenb@suse.de> and Diego Novillo <dnovillo@redhat.com>
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, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA. */
+the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+Boston, MA 02110-1301, USA. */
#include "config.h"
#include "system.h"
/* Associated expression. */
tree e;
- /* Virtual uses in E. */
- vuse_optype vuses;
+ /* For comparing virtual uses in E. */
+ VEC (tree, gc) *vuses;
/* E's hash value. */
hashval_t hashcode;
any).
VAL can be used to iterate by passing previous value numbers (it is
- used by iterative_hash_expr).
-
- VUSES is the set of virtual use operands associated with EXPR. It
- may be NULL if EXPR has no virtual operands. */
+ used by iterative_hash_expr). */
hashval_t
-vn_compute (tree expr, hashval_t val, vuse_optype vuses)
+vn_compute (tree expr, hashval_t val)
{
- size_t i;
-
/* EXPR must not be a statement. We are only interested in value
numbering expressions on the RHS of assignments. */
gcc_assert (expr);
|| expr->common.ann->common.type != STMT_ANN);
val = iterative_hash_expr (expr, val);
-
- /* If the expression has virtual uses, incorporate them into the
- hash value computed for EXPR. */
- for (i = 0; i < NUM_VUSES (vuses); i++)
- val = iterative_hash_expr (VUSE_OP (vuses, i), val);
-
return val;
}
-
/* Compare two expressions E1 and E2 and return true if they are
equal. */
te1 = TREE_TYPE (e1);
te2 = TREE_TYPE (e2);
- if (TREE_CODE (e1) == TREE_CODE (e2)
- && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
- && operand_equal_p (e1, e2, OEP_PURE_SAME))
+ if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
+ {
+ tree lop1 = e1;
+ tree lop2 = e2;
+ for (lop1 = e1, lop2 = e2;
+ lop1 || lop2;
+ lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
+ {
+ if (!lop1 || !lop2)
+ return false;
+ if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
+ return false;
+ }
+ return true;
+
+ }
+ else if (TREE_CODE (e1) == TREE_CODE (e2)
+ && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
+ && operand_equal_p (e1, e2, OEP_PURE_SAME))
return true;
return false;
static int
val_expr_pair_expr_eq (const void *p1, const void *p2)
{
+ int i;
+ tree vuse1;
const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
- size_t i;
if (! expressions_equal_p (ve1->e, ve2->e))
return false;
- if (NUM_VUSES (ve1->vuses) != NUM_VUSES (ve2->vuses))
+ if (ve1->vuses == ve2->vuses)
+ return true;
+
+ if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))
return false;
-
- for (i = 0; i < NUM_VUSES (ve1->vuses); i++)
- if (! expressions_equal_p (VUSE_OP (ve1->vuses, i),
- VUSE_OP (ve2->vuses, i)))
- return false;
-
+
+ for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++)
+ {
+ if (VEC_index (tree, ve2->vuses, i) != vuse1)
+ return false;
+ }
return true;
}
{
if (TREE_CODE (e) == SSA_NAME)
SSA_NAME_VALUE (e) = v;
- else if (EXPR_P (e) || DECL_P (e))
+ else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST
+ || TREE_CODE (e) == CONSTRUCTOR)
get_tree_ann (e)->common.value_handle = v;
else
/* Do nothing. Constants are their own value handles. */
gcc_assert (is_gimple_min_invariant (e));
}
+/* Copy the virtual uses from STMT into a newly allocated VEC(tree),
+ and return the VEC(tree). */
+
+static VEC (tree, gc) *
+copy_vuses_from_stmt (tree stmt)
+{
+ ssa_op_iter iter;
+ tree vuse;
+ VEC (tree, gc) *vuses = NULL;
+
+ if (!stmt)
+ return NULL;
+
+ FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
+ VEC_safe_push (tree, gc, vuses, vuse);
+
+ return vuses;
+}
+
+/* Place for shared_vuses_from_stmt to shove vuses. */
+static VEC (tree, gc) *shared_lookup_vuses;
+
+/* Copy the virtual uses from STMT into SHARED_LOOKUP_VUSES.
+ This function will overwrite the current SHARED_LOOKUP_VUSES
+ variable. */
+
+static VEC (tree, gc) *
+shared_vuses_from_stmt (tree stmt)
+{
+ ssa_op_iter iter;
+ tree vuse;
+
+ if (!stmt)
+ return NULL;
+
+ VEC_truncate (tree, shared_lookup_vuses, 0);
+
+ FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
+ VEC_safe_push (tree, gc, shared_lookup_vuses, vuse);
+
+ if (VEC_length (tree, shared_lookup_vuses) > 1)
+ sort_vuses (shared_lookup_vuses);
+
+ return shared_lookup_vuses;
+}
/* Insert EXPR into VALUE_TABLE with value VAL, and add expression
- EXPR to the value set for value VAL. VUSES represent the virtual
- use operands associated with EXPR (if any). They are used when
- computing the hash value for EXPR. */
+ EXPR to the value set for value VAL. */
void
-vn_add (tree expr, tree val, vuse_optype vuses)
+vn_add (tree expr, tree val)
+{
+ vn_add_with_vuses (expr, val, NULL);
+}
+
+/* Insert EXPR into VALUE_TABLE with value VAL, and add expression
+ EXPR to the value set for value VAL. VUSES represents the virtual
+ use operands associated with EXPR. It is used when computing a
+ hash value for EXPR. */
+
+void
+vn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses)
{
void **slot;
val_expr_pair_t new_pair;
- new_pair = xmalloc (sizeof (struct val_expr_pair_d));
+ new_pair = XNEW (struct val_expr_pair_d);
new_pair->e = expr;
new_pair->v = val;
new_pair->vuses = vuses;
- new_pair->hashcode = vn_compute (expr, 0, vuses);
+ new_pair->hashcode = vn_compute (expr, 0);
slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
INSERT);
if (*slot)
*slot = (void *) new_pair;
set_value_handle (expr, val);
- add_to_value (val, expr);
+ if (TREE_CODE (val) == VALUE_HANDLE)
+ add_to_value (val, expr);
}
/* Search in VALUE_TABLE for an existing instance of expression EXPR,
- and return its value, or NULL if none has been set. VUSES
- represent the virtual use operands associated with EXPR (if any).
- They are used when computing the hash value for EXPR. */
+ and return its value, or NULL if none has been set. STMT
+ represents the stmt associated with EXPR. It is used when computing the
+ hash value for EXPR. */
+
+tree
+vn_lookup (tree expr, tree stmt)
+{
+ return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt));
+}
+
+/* Search in VALUE_TABLE for an existing instance of expression EXPR,
+ and return its value, or NULL if none has been set. VUSES is the
+ list of virtual use operands associated with EXPR. It is used when
+ computing the hash value for EXPR. */
tree
-vn_lookup (tree expr, vuse_optype vuses)
+vn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses)
{
void **slot;
struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
vep.e = expr;
vep.vuses = vuses;
- vep.hashcode = vn_compute (expr, 0, vuses);
+ vep.hashcode = vn_compute (expr, 0);
slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
if (!slot)
return NULL_TREE;
}
+/* A comparison function for use in qsort to compare vuses. Simply
+ subtracts version numbers. */
+
+static int
+vuses_compare (const void *pa, const void *pb)
+{
+ const tree vusea = *((const tree *)pa);
+ const tree vuseb = *((const tree *)pb);
+ int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb);
+
+ return sn;
+}
+
+/* Print out the "Created value <x> for <Y>" statement to the
+ dump_file.
+ This is factored because both versions of lookup use it, and it
+ obscures the real work going on in those functions. */
+
+static void
+print_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses)
+{
+ fprintf (dump_file, "Created value ");
+ print_generic_expr (dump_file, v, dump_flags);
+ fprintf (dump_file, " for ");
+ print_generic_expr (dump_file, expr, dump_flags);
+
+ if (vuses && VEC_length (tree, vuses) != 0)
+ {
+ size_t i;
+ tree vuse;
+
+ fprintf (dump_file, " vuses: (");
+ for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
+ {
+ print_generic_expr (dump_file, vuse, dump_flags);
+ if (VEC_length (tree, vuses) - 1 != i)
+ fprintf (dump_file, ",");
+ }
+ fprintf (dump_file, ")");
+ }
+ fprintf (dump_file, "\n");
+}
+
/* Like vn_lookup, but creates a new value for expression EXPR, if
EXPR doesn't already have a value. Return the existing/created
- value for EXPR. VUSES represent the virtual use operands
- associated with EXPR (if any). They are used when computing the
- hash value for EXPR. */
+ value for EXPR. STMT represents the stmt associated with EXPR. It
+ is used when computing the VUSES for EXPR. */
tree
-vn_lookup_or_add (tree expr, vuse_optype vuses)
+vn_lookup_or_add (tree expr, tree stmt)
{
- tree v = vn_lookup (expr, vuses);
+ tree v = vn_lookup (expr, stmt);
if (v == NULL_TREE)
{
+ VEC(tree,gc) *vuses;
+
v = make_value_handle (TREE_TYPE (expr));
+ vuses = copy_vuses_from_stmt (stmt);
+ sort_vuses (vuses);
if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Created value ");
- print_generic_expr (dump_file, v, dump_flags);
- fprintf (dump_file, " for ");
- print_generic_expr (dump_file, expr, dump_flags);
- fprintf (dump_file, "\n");
- }
+ print_creation_to_file (v, expr, vuses);
- vn_add (expr, v, vuses);
+ VALUE_HANDLE_VUSES (v) = vuses;
+ vn_add_with_vuses (expr, v, vuses);
}
set_value_handle (expr, v);
return v;
}
+/* Sort the VUSE array so that we can do equality comparisons
+ quicker on two vuse vecs. */
+
+void
+sort_vuses (VEC (tree,gc) *vuses)
+{
+ if (VEC_length (tree, vuses) > 1)
+ qsort (VEC_address (tree, vuses),
+ VEC_length (tree, vuses),
+ sizeof (tree),
+ vuses_compare);
+}
+
+/* Like vn_lookup, but creates a new value for expression EXPR, if
+ EXPR doesn't already have a value. Return the existing/created
+ value for EXPR. STMT represents the stmt associated with EXPR. It is used
+ when computing the hash value for EXPR. */
+
+tree
+vn_lookup_or_add_with_vuses (tree expr, VEC (tree, gc) *vuses)
+{
+ tree v = vn_lookup_with_vuses (expr, vuses);
+ if (v == NULL_TREE)
+ {
+ v = make_value_handle (TREE_TYPE (expr));
+ sort_vuses (vuses);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ print_creation_to_file (v, expr, vuses);
+
+ VALUE_HANDLE_VUSES (v) = vuses;
+ vn_add_with_vuses (expr, v, vuses);
+ }
+
+ set_value_handle (expr, v);
+
+ return v;
+}
+
+
/* Get the value handle of EXPR. This is the only correct way to get
the value handle for a "thing". If EXPR does not have a value
- handle associated, it returns NULL_TREE. */
+ handle associated, it returns NULL_TREE.
+ NB: If EXPR is min_invariant, this function is *required* to return EXPR. */
tree
get_value_handle (tree expr)
{
+
+ if (is_gimple_min_invariant (expr))
+ return expr;
+
if (TREE_CODE (expr) == SSA_NAME)
return SSA_NAME_VALUE (expr);
- else if (EXPR_P (expr) || DECL_P (expr))
+ else if (EXPR_P (expr) || DECL_P (expr) || TREE_CODE (expr) == TREE_LIST
+ || TREE_CODE (expr) == CONSTRUCTOR)
{
tree_ann_t ann = tree_ann (expr);
return ((ann) ? ann->common.value_handle : NULL_TREE);
}
else
- {
- gcc_assert (is_gimple_min_invariant (expr));
- return expr;
- }
+ gcc_unreachable ();
}
{
value_table = htab_create (511, val_expr_pair_hash,
val_expr_pair_expr_eq, free);
+ shared_lookup_vuses = NULL;
}
vn_delete (void)
{
htab_delete (value_table);
+ VEC_free (tree, gc, shared_lookup_vuses);
value_table = NULL;
}
OSDN Git Service
