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;
- /* for comparing Virtual uses in E. */
- tree stmt;
+ /* 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).
-
- STMT is the stmt associated with EXPR for comparing virtual operands. */
+ used by iterative_hash_expr). */
hashval_t
-vn_compute (tree expr, hashval_t val, tree stmt)
+vn_compute (tree expr, hashval_t val)
{
- ssa_op_iter iter;
- tree vuse;
-
/* EXPR must not be a statement. We are only interested in value
numbering expressions on the RHS of assignments. */
gcc_assert (expr);
- gcc_assert (!expr->common.ann
- || expr->common.ann->common.type != STMT_ANN);
+ gcc_assert (!expr->base.ann
+ || expr->base.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. */
- if (stmt)
- FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
- val = iterative_hash_expr (vuse, val);
-
return val;
}
-
/* Compare two expressions E1 and E2 and return true if they are
equal. */
static int
val_expr_pair_expr_eq (const void *p1, const void *p2)
{
- bool ret;
+ 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;
if (! expressions_equal_p (ve1->e, ve2->e))
return false;
- ret = compare_ssa_operands_equal (ve1->stmt, ve2->stmt, SSA_OP_VUSE);
- return ret;
+ if (ve1->vuses == ve2->vuses)
+ return true;
+
+ if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))
+ 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) || TREE_CODE (e) == TREE_LIST)
- get_tree_ann (e)->common.value_handle = v;
+ else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST
+ || GIMPLE_STMT_P (e)
+ || TREE_CODE (e) == CONSTRUCTOR)
+ get_tree_common_ann (e)->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. STMT represents the stmt
- associated with EXPR. It is used when computing a hash value for EXPR. */
+ EXPR to the value set for value VAL. */
void
-vn_add (tree expr, tree val, tree stmt)
+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->stmt = stmt;
- new_pair->hashcode = vn_compute (expr, 0, stmt);
+ new_pair->vuses = 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);
}
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_with_vuses (tree expr, VEC (tree, gc) *vuses)
+{
void **slot;
struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
return expr;
vep.e = expr;
- vep.stmt = stmt;
- vep.hashcode = vn_compute (expr, 0, stmt);
+ vep.vuses = 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. STMT represents the stmt associated with EXPR. It is 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, tree stmt)
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, stmt);
+ 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. */
-/* 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.
- NB: If EXPR is min_invariant, this function is *required* to return EXPR. */
+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
-get_value_handle (tree expr)
+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 (is_gimple_min_invariant (expr))
- return expr;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ print_creation_to_file (v, expr, vuses);
- if (TREE_CODE (expr) == SSA_NAME)
- return SSA_NAME_VALUE (expr);
- else if (EXPR_P (expr) || DECL_P (expr) || TREE_CODE (expr) == TREE_LIST)
- {
- tree_ann_t ann = tree_ann (expr);
- return ((ann) ? ann->common.value_handle : NULL_TREE);
+ VALUE_HANDLE_VUSES (v) = vuses;
+ vn_add_with_vuses (expr, v, vuses);
}
- else
- gcc_unreachable ();
-}
+ set_value_handle (expr, v);
+
+ return v;
+}
/* Initialize data structures used in value numbering. */
{
value_table = htab_create (511, val_expr_pair_hash,
val_expr_pair_expr_eq, free);
+ shared_lookup_vuses = NULL;
}
-
/* Delete data used for value numbering. */
void
vn_delete (void)
{
htab_delete (value_table);
+ VEC_free (tree, gc, shared_lookup_vuses);
value_table = NULL;
}
OSDN Git Service
