X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-vn.c;h=a23d7beb4679ee801ec27774d01f8d95f2585911;hb=f5ef996258725dd451733c21e2bba88c87019646;hp=4863cb76f3648cd4a2385fea27625522313a2085;hpb=c75b4594282e6b33803b8332acba704d057f8d97;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-vn.c b/gcc/tree-vn.c index 4863cb76f36..a23d7beb467 100644 --- a/gcc/tree-vn.c +++ b/gcc/tree-vn.c @@ -1,5 +1,5 @@ /* Value Numbering routines for tree expressions. - Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. + Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc. Contributed by Daniel Berlin , Steven Bosscher and Diego Novillo @@ -7,7 +7,7 @@ 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) +the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, @@ -16,9 +16,8 @@ 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. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" @@ -32,35 +31,15 @@ Boston, MA 02110-1301, USA. */ #include "tree-pass.h" #include "tree-dump.h" #include "diagnostic.h" +#include "tree-ssa-sccvn.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. */ - tree stmt; - - /* E's hash value. */ - hashval_t hashcode; -} *val_expr_pair_t; - -static void set_value_handle (tree e, tree v); - +/* Most of this is PRE specific. The real grunt work is done in + tree-ssa-sccvn.c. This is where the lookup and insertion + functions, etc, can be found */ /* Create and return a new value handle node of type TYPE. */ -static tree +tree make_value_handle (tree type) { static unsigned int id = 0; @@ -72,38 +51,6 @@ make_value_handle (tree type) } -/* 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). - - STMT is the stmt associated with EXPR for comparing virtual operands. */ - -hashval_t -vn_compute (tree expr, hashval_t val, tree stmt) -{ - 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); - - 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. */ @@ -112,7 +59,7 @@ bool expressions_equal_p (tree e1, tree e2) { tree te1, te2; - + if (e1 == e2) return true; @@ -135,185 +82,324 @@ expressions_equal_p (tree e1, tree e2) return true; } - else if (TREE_CODE (e1) == TREE_CODE (e2) - && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2)) + else if (TREE_CODE (e1) == TREE_CODE (e2) + && (te1 == te2 + || types_compatible_p (te1, te2)) && operand_equal_p (e1, e2, OEP_PURE_SAME)) return true; return false; } +/* Set the value handle for expression E to value V. */ -/* 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) +void +set_value_handle (tree e, tree v) { - const val_expr_pair_t ve = (val_expr_pair_t) p; - return ve->hashcode; + if (TREE_CODE (e) == SSA_NAME) + SSA_NAME_VALUE (e) = 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)); } - -/* 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. */ +/* A comparison function for use in qsort to compare vuses. Simply + subtracts version numbers. */ static int -val_expr_pair_expr_eq (const void *p1, const void *p2) +vuses_compare (const void *pa, const void *pb) { - bool ret; - const val_expr_pair_t ve1 = (val_expr_pair_t) p1; - const val_expr_pair_t ve2 = (val_expr_pair_t) p2; + const tree vusea = *((const tree *)pa); + const tree vuseb = *((const tree *)pb); + int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb); - if (! expressions_equal_p (ve1->e, ve2->e)) - return false; - - ret = compare_ssa_operands_equal (ve1->stmt, ve2->stmt, SSA_OP_VUSE); - return ret; + return sn; } +/* Print out the "Created value for " 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. */ -/* Set the value handle for expression E to value V. */ - static void -set_value_handle (tree e, tree v) +print_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses) { - 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_ann (e)->common.value_handle = v; - else - /* Do nothing. Constants are their own value handles. */ - gcc_assert (is_gimple_min_invariant (e)); + 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"); } +/* 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); +} + +/* Sort the VUSE array so that we can do equality comparisons + quicker on two vuse vecs. */ + +void +sort_vuses_heap (VEC (tree,heap) *vuses) +{ + if (VEC_length (tree, vuses) > 1) + qsort (VEC_address (tree, vuses), + VEC_length (tree, vuses), + sizeof (tree), + vuses_compare); +} /* 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) +{ + switch (TREE_CODE_CLASS (TREE_CODE (expr))) + { + case tcc_comparison: + case tcc_binary: + vn_binary_op_insert (expr, val); + break; + case tcc_unary: + vn_unary_op_insert (expr, val); + break; + /* In the case of array-refs of constants, for example, we can + end up with no vuses. */ + case tcc_reference: + vn_reference_insert (expr, val, NULL); + break; + /* The *only* time CALL_EXPR should appear here is + when it has no vuses. */ + case tcc_vl_exp: + case tcc_exceptional: + case tcc_expression: + case tcc_declaration: + if (TREE_CODE (expr) == CALL_EXPR || DECL_P (expr)) + { + vn_reference_insert (expr, val, NULL); + break; + } + else if (TREE_CODE (expr) == SSA_NAME) + { + SSA_NAME_VALUE (expr) = val; + break; + } + else if (TREE_CODE (expr) == ADDR_EXPR) + { + vn_unary_op_insert (expr, val); + break; + } + /* FALLTHROUGH */ + default: + gcc_unreachable (); + } + set_value_handle (expr, val); + if (TREE_CODE (val) == VALUE_HANDLE) + add_to_value (val, expr); +} + +/* Insert EXPR into the value numbering tables. 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 (tree expr, tree val, tree stmt) +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->e = expr; - new_pair->v = val; - new_pair->stmt = stmt; - new_pair->hashcode = vn_compute (expr, 0, stmt); - slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode, - INSERT); - if (*slot) - free (*slot); - *slot = (void *) new_pair; + if (!vuses) + { + vn_add (expr, val); + return; + } + vn_reference_insert (expr, val, vuses); 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. STMT - represents the stmt associated with EXPR. It is used when computing the - hash value for EXPR. */ +/* Lookup EXPR in the value numbering tables and return the result, if + we have one. */ + +tree +vn_lookup (tree expr) +{ + /* Constants are their own value. */ + if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL) + return expr; + + switch (TREE_CODE_CLASS (TREE_CODE (expr))) + { + case tcc_comparison: + case tcc_binary: + return vn_binary_op_lookup (expr); + case tcc_unary: + return vn_unary_op_lookup (expr); + break; + /* In the case of array-refs of constants, for example, we can + end up with no vuses. */ + case tcc_reference: + return vn_reference_lookup (expr, NULL); + break; + /* It is possible to have CALL_EXPR with no vuses for things + like "cos", and these will fall into vn_lookup. */ + case tcc_vl_exp: + case tcc_exceptional: + case tcc_expression: + case tcc_declaration: + if (TREE_CODE (expr) == CALL_EXPR || DECL_P (expr)) + return vn_reference_lookup (expr, NULL); + else if (TREE_CODE (expr) == SSA_NAME) + return SSA_NAME_VALUE (expr); + else if (TREE_CODE (expr) == ADDR_EXPR) + return vn_unary_op_lookup (expr); + /* FALLTHROUGH */ + default: + gcc_unreachable (); + } + return NULL; +} + +/* Search in the value numbering tables 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 for reference operations. */ tree -vn_lookup (tree expr, tree stmt) +vn_lookup_with_stmt (tree expr, tree stmt) { - void **slot; - struct val_expr_pair_d vep = {NULL, NULL, NULL, 0}; + if (stmt == NULL) + return vn_lookup (expr); /* Constants are their own value. */ - if (is_gimple_min_invariant (expr)) + if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL) return expr; - vep.e = expr; - vep.stmt = stmt; - vep.hashcode = vn_compute (expr, 0, stmt); - 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; + 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. */ -/* 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_with_vuses (tree expr, VEC (tree, gc) *vuses) +{ + if (!vuses || !VEC_length (tree, vuses)) + return vn_lookup (expr); + + if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL) + return expr; + + return vn_reference_lookup (expr, vuses); +} + +static tree +create_value_handle_for_expr (tree expr, VEC(tree, gc) *vuses) +{ + tree v; + + v = make_value_handle (TREE_TYPE (expr)); + + if (dump_file && (dump_flags & TDF_DETAILS)) + print_creation_to_file (v, expr, vuses); + return v; +} + +/* Like vn_lookup, but creates a new value for the operation if one + does not exist. */ tree -vn_lookup_or_add (tree expr, tree stmt) +vn_lookup_or_add (tree expr) { - tree v = vn_lookup (expr, stmt); + tree v = vn_lookup (expr); + if (v == NULL_TREE) { - v = make_value_handle (TREE_TYPE (expr)); - - 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"); - } - - vn_add (expr, v, stmt); + v = create_value_handle_for_expr (expr, NULL); + vn_add (expr, v); } - - set_value_handle (expr, v); + else + 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. */ +/* Like vn_lookup, but handles reference operations as well by using + STMT to get the set of vuses. */ tree -get_value_handle (tree expr) +vn_lookup_or_add_with_stmt (tree expr, tree stmt) { + tree v; + if (!stmt) + return vn_lookup_or_add (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) + v = vn_lookup_with_stmt (expr, stmt); + if (v == NULL_TREE) { - tree_ann_t ann = tree_ann (expr); - return ((ann) ? ann->common.value_handle : NULL_TREE); + VEC (tree, gc) *vuses = copy_vuses_from_stmt (stmt); + v = create_value_handle_for_expr (expr, 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. */ +/* 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. */ -void -vn_init (void) +tree +vn_lookup_or_add_with_vuses (tree expr, VEC (tree, gc) *vuses) { - value_table = htab_create (511, val_expr_pair_hash, - val_expr_pair_expr_eq, free); -} + tree v; + if (!vuses || VEC_length (tree, vuses) == 0) + return vn_lookup_or_add (expr); -/* Delete data used for value numbering. */ + v = vn_lookup_with_vuses (expr, vuses); + if (v == NULL_TREE) + { + v = create_value_handle_for_expr (expr, vuses); + vn_add_with_vuses (expr, v, vuses); + } + else + set_value_handle (expr, v); -void -vn_delete (void) -{ - htab_delete (value_table); - value_table = NULL; + return v; } +