| /* Value Numbering routines for tree expressions. |
| 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> |
| |
| 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 version. |
| |
| GCC is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU General Public License 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. */ |
| |
| #include "config.h" |
| #include "system.h" |
| #include "coretypes.h" |
| #include "tm.h" |
| #include "ggc.h" |
| #include "tree.h" |
| #include "tree-flow.h" |
| #include "hashtab.h" |
| #include "langhooks.h" |
| #include "tree-pass.h" |
| #include "tree-dump.h" |
| #include "diagnostic.h" |
| |
| /* The value table that maps expressions to values. */ |
| static htab_t value_table; |
| |
| /* Map expressions to values. These are simple pairs of expressions |
| and the values they represent. To find the value represented by |
| an expression, we use a hash table where the elements are {e,v} |
| pairs, and the expression is the key. */ |
| typedef struct val_expr_pair_d |
| { |
| /* Value handle. */ |
| tree v; |
| |
| /* Associated expression. */ |
| tree e; |
| |
| /* For comparing virtual uses in E. */ |
| VEC (tree, gc) *vuses; |
| |
| /* E's hash value. */ |
| hashval_t hashcode; |
| } *val_expr_pair_t; |
| |
| static void set_value_handle (tree e, tree v); |
| |
| |
| /* Create and return a new value handle node of type TYPE. */ |
| |
| static tree |
| make_value_handle (tree type) |
| { |
| static unsigned int id = 0; |
| tree vh; |
| |
| vh = build0 (VALUE_HANDLE, type); |
| VALUE_HANDLE_ID (vh) = id++; |
| return vh; |
| } |
| |
| |
| /* Given an expression EXPR, compute a hash value number using the |
| code of the expression, its real operands and virtual operands (if |
| any). |
| |
| VAL can be used to iterate by passing previous value numbers (it is |
| used by iterative_hash_expr). */ |
| |
| hashval_t |
| vn_compute (tree expr, hashval_t val) |
| { |
| /* 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); |
| |
| val = iterative_hash_expr (expr, val); |
| return val; |
| } |
| |
| /* Compare two expressions E1 and E2 and return true if they are |
| equal. */ |
| |
| bool |
| expressions_equal_p (tree e1, tree e2) |
| { |
| tree te1, te2; |
| |
| if (e1 == e2) |
| return true; |
| |
| te1 = TREE_TYPE (e1); |
| te2 = TREE_TYPE (e2); |
| |
| 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; |
| } |
| |
| |
| /* Hash a {v,e} pair that is pointed to by P. |
| The hashcode is cached in the val_expr_pair, so we just return |
| that. */ |
| |
| static hashval_t |
| val_expr_pair_hash (const void *p) |
| { |
| const val_expr_pair_t ve = (val_expr_pair_t) p; |
| return ve->hashcode; |
| } |
| |
| |
| /* Given two val_expr_pair_t's, return true if they represent the same |
| expression, false otherwise. |
| P1 and P2 should point to the val_expr_pair_t's to be compared. */ |
| |
| 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; |
| |
| if (! expressions_equal_p (ve1->e, ve2->e)) |
| return false; |
| |
| 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; |
| } |
| |
| |
| /* Set the value handle for expression E to value V. */ |
| |
| static void |
| set_value_handle (tree e, tree v) |
| { |
| if (TREE_CODE (e) == SSA_NAME) |
| SSA_NAME_VALUE (e) = v; |
| else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST |
| || 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. */ |
| |
| void |
| 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 = 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); |
| slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode, |
| INSERT); |
| if (*slot) |
| free (*slot); |
| *slot = (void *) new_pair; |
| |
| set_value_handle (expr, val); |
| 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. 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_with_vuses (tree expr, VEC (tree, gc) *vuses) |
| { |
| void **slot; |
| struct val_expr_pair_d vep = {NULL, NULL, NULL, 0}; |
| |
| /* Constants are their own value. */ |
| if (is_gimple_min_invariant (expr)) |
| return expr; |
| |
| vep.e = expr; |
| 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; |
| else |
| return ((val_expr_pair_t) *slot)->v; |
| } |
| |
| |
| /* 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 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)) |
| 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; |
| } |
| |
| /* 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. |
| 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) || TREE_CODE (expr) == TREE_LIST |
| || TREE_CODE (expr) == CONSTRUCTOR) |
| { |
| tree_ann_common_t ann = tree_common_ann (expr); |
| return ((ann) ? ann->value_handle : NULL_TREE); |
| } |
| else |
| gcc_unreachable (); |
| } |
| |
| |
| /* Initialize data structures used in value numbering. */ |
| |
| void |
| vn_init (void) |
| { |
| 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; |
| } |