diff options
| -rw-r--r-- | gcc/ChangeLog | 30 | ||||
| -rw-r--r-- | gcc/Makefile.in | 8 | ||||
| -rw-r--r-- | gcc/tree-dfa.c | 4 | ||||
| -rw-r--r-- | gcc/tree-flow.h | 22 | ||||
| -rw-r--r-- | gcc/tree-optimize.c | 28 | ||||
| -rw-r--r-- | gcc/tree-pretty-print.c | 6 | ||||
| -rw-r--r-- | gcc/tree-ssa-pre.c | 322 | ||||
| -rw-r--r-- | gcc/tree-ssa.c | 2 | ||||
| -rw-r--r-- | gcc/tree-vn.c | 257 | ||||
| -rw-r--r-- | gcc/tree.c | 5 | ||||
| -rw-r--r-- | gcc/tree.def | 6 | ||||
| -rw-r--r-- | gcc/tree.h | 24 |
12 files changed, 435 insertions, 279 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index e2ca75138bc..320edb0020e 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,33 @@ +2004-06-23 Diego Novillo <dnovillo@redhat.com> + + * Makefile.in (tree-vn.o): New. + (tree-ssa-pre.o): Don't depend on RTL_H. + * tree-dfa.c (find_referenced_vars): Don't call init_tree_ssa. + * tree-flow.h (struct var_ann_d): Remove field expr_set. + (add_to_value, expressions_equal_p, get_value_handle, vn_compute, + vn_lookup_or_add, vn_add, vn_lookup, vn_init, vn_delete): Declare. + * tree-optimize.c (execute_init_datastructures): New local function. + (pass_init_datastructures): New local variable. + (init_tree_optimization_passes): Sequence pass_init_datastructures. + * tree-pretty-print.c (MASK_POINTER): Remove. + (dump_generic_node): Handle VALUE_HANDLE. + * tree-ssa-pre.c: Move all value numbering routines to tree-vn.c. + Update callers to use new function names. + Use VALUE_HANDLE_ID and VALUE_HANDLE_EXPR_SET instead of + variable annotations. + * tree-ssa.c (init_tree_ssa): Call vn_init. + (delete_tree_ssa): Call vn_delete. + * tree-vn.c: New file. + * tree.c (tree_size): Handle VALUE_HANDLE. + (tree_node_structure): Likewise. + (iterative_hash_expr): Likewise. + * tree.def (VALUE_HANDLE): New code. + * tree.h (struct tree_value_handle): New. + (VALUE_HANDLE_ID): Define. + (VALUE_HANDLE_EXPR_SET): Define. + (enum tree_node_structure_enum): Add TS_VALUE_HANDLE. + (union tree_node): Add struct tree_value_handle. + 2004-06-23 Andrew Pinski <apinski@apple.com> * c-typeck.c (composite_type): diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 63c7ebc3d13..81b5b7e51eb 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -887,7 +887,7 @@ C_OBJS = c-parse.o c-lang.o stub-objc.o $(C_AND_OBJC_OBJS) OBJS-common = \ tree-cfg.o tree-dfa.o tree-eh.o tree-ssa.o tree-optimize.o tree-gimple.o \ tree-alias-type.o gimplify.o tree-pretty-print.o tree-into-ssa.o \ - tree-outof-ssa.o tree-alias-common.o tree-ssa-ccp.o \ + tree-outof-ssa.o tree-alias-common.o tree-ssa-ccp.o tree-vn.o \ @ANDER@ tree-ssa-dce.o tree-ssa-copy.o tree-nrv.o tree-ssa-copyrename.o \ tree-ssa-pre.o tree-ssa-live.o tree-ssa-operands.o tree-ssa-alias.o \ tree-ssa-phiopt.o tree-ssa-forwprop.o tree-nested.o tree-ssa-dse.o \ @@ -1640,9 +1640,12 @@ tree-ssa-copyrename.o : tree-ssa-copyrename.c $(TREE_FLOW_H) $(CONFIG_H) \ diagnostic.h errors.h toplev.h function.h $(TIMEVAR_H) tree-pass.h \ tree-alias-common.h $(TM_H) coretypes.h $(TREE_DUMP_H) $(TREE_SSA_LIVE_H) tree-ssa-pre.o : tree-ssa-pre.c $(TREE_FLOW_H) $(CONFIG_H) \ - $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) \ + $(SYSTEM_H) $(TREE_H) $(TM_P_H) $(EXPR_H) \ $(GGC_H) output.h diagnostic.h errors.h toplev.h $(TIMEVAR_H) \ $(TM_H) coretypes.h $(TREE_DUMP_H) tree-pass.h $(FLAGS_H) +tree-vn.o : tree-vn.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(GGC_H) \ + $(TREE_H) $(TREE_FLOW_H) $(HASHTAB_H) langhooks.h tree-pass.h \ + $(TREE_DUMP_H) diagnostic.h tree-cfg.o : tree-cfg.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) $(FLAGS_H) output.h \ diagnostic.h errors.h function.h $(TIMEVAR_H) $(TM_H) coretypes.h \ @@ -3068,6 +3071,7 @@ distclean: clean lang.distclean -rm -f fixinc/Makefile # Delete po/*.gmo only if we are not building in the source directory. -if [ ! -f po/exgettext ]; then rm -f po/*.gmo; fi + -rmdir ada cp f java objc fixinc intl po testsuite 2>/dev/null # Get rid of every file that's generated from some other file, except for `configure'. # Most of these files ARE PRESENT in the GCC distribution. diff --git a/gcc/tree-dfa.c b/gcc/tree-dfa.c index 307086bedb7..bc1f8f5dd44 100644 --- a/gcc/tree-dfa.c +++ b/gcc/tree-dfa.c @@ -111,10 +111,6 @@ find_referenced_vars (void) struct walk_state walk_state; tree block; - /* This is the very first pass in preparation for building the SSA - form of the function, so initialize internal data structures now. */ - init_tree_ssa (); - /* Walk the lexical blocks in the function looking for variables that may have been used to declare VLAs and for nested functions. Both constructs create hidden uses of variables. diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index 6ddf72c2cfc..e18c1e4c48d 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -167,11 +167,6 @@ struct var_ann_d GTY(()) live at the same time and this can happen for each call to the dominator optimizer. */ tree current_def; - - /* The set of expressions represented by this variable if it is a - value handle. This is used by GVN-PRE. */ - PTR GTY ((skip)) expr_set; - }; @@ -576,12 +571,23 @@ extern bool tree_can_throw_internal (tree); extern bool tree_can_throw_external (tree); extern void add_stmt_to_eh_region (tree, int); -/* In tree-ssa-pre.c */ -tree get_value_handle (tree); -void set_value_handle (tree, tree); +/* In tree-ssa-pre.c */ +void add_to_value (tree, tree); void debug_value_expressions (tree); void print_value_expressions (FILE *, tree); + +/* In tree-vn.c */ +bool expressions_equal_p (tree e1, tree e2); +tree get_value_handle (tree); +hashval_t vn_compute (tree, hashval_t); +tree vn_lookup_or_add (tree); +void vn_add (tree, tree); +tree vn_lookup (tree); +void vn_init (void); +void vn_delete (void); + + /* In tree-sra.c */ void insert_edge_copies (tree stmt, basic_block bb); diff --git a/gcc/tree-optimize.c b/gcc/tree-optimize.c index 30e1e7c25ef..a9217b187c4 100644 --- a/gcc/tree-optimize.c +++ b/gcc/tree-optimize.c @@ -153,6 +153,33 @@ static struct tree_opt_pass pass_free_datastructures = 0 /* todo_flags_finish */ }; + +/* Do the actions required to initialize internal data structures used + in tree-ssa optimization passes. */ + +static void +execute_init_datastructures (void) +{ + /* Allocate hash tables, arrays and other structures. */ + init_tree_ssa (); +} + +static struct tree_opt_pass pass_init_datastructures = +{ + NULL, /* name */ + NULL, /* gate */ + execute_init_datastructures, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + 0, /* tv_id */ + PROP_cfg, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0 /* todo_flags_finish */ +}; + /* Iterate over the pass tree allocating dump file numbers. We want to do this depth first, and independent of whether the pass is enabled or not. */ @@ -253,6 +280,7 @@ init_tree_optimization_passes (void) NEXT_PASS (pass_lower_eh); NEXT_PASS (pass_build_cfg); NEXT_PASS (pass_tree_profile); + NEXT_PASS (pass_init_datastructures); NEXT_PASS (pass_all_optimizations); NEXT_PASS (pass_mudflap_2); NEXT_PASS (pass_free_datastructures); diff --git a/gcc/tree-pretty-print.c b/gcc/tree-pretty-print.c index 6ebf07564c7..fe115bc3ca8 100644 --- a/gcc/tree-pretty-print.c +++ b/gcc/tree-pretty-print.c @@ -55,8 +55,6 @@ static void dump_generic_bb_buff (pretty_printer *, basic_block, int, int); lang_hooks.decl_printable_name (TREE_OPERAND (NODE, 0), 1) : \ lang_hooks.decl_printable_name (NODE, 1)) -#define MASK_POINTER(P) ((unsigned)((unsigned long)(P) & 0xffff)) - static pretty_printer buffer; static int initialized = 0; static bool dumping_stmts; @@ -1403,6 +1401,10 @@ dump_generic_node (pretty_printer *buffer, tree node, int spc, int flags, pp_decimal_int (buffer, SSA_NAME_VERSION (node)); break; + case VALUE_HANDLE: + pp_printf (buffer, "VH.%d", VALUE_HANDLE_ID (node)); + break; + default: NIY; } diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index c8d8035f5ec..5c32bc28787 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -19,6 +19,7 @@ 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. */ + #include "config.h" #include "system.h" #include "coretypes.h" @@ -26,11 +27,6 @@ Boston, MA 02111-1307, USA. */ #include "errors.h" #include "ggc.h" #include "tree.h" - -/* These RTL headers are needed for basic-block.h. */ -#include "rtl.h" -#include "tm_p.h" -#include "hard-reg-set.h" #include "basic-block.h" #include "diagnostic.h" #include "tree-inline.h" @@ -48,6 +44,7 @@ Boston, MA 02111-1307, USA. */ #include "splay-tree.h" #include "bitmap.h" #include "langhooks.h" + /* TODO: 1. Implement load value numbering. @@ -279,10 +276,8 @@ static struct static tree find_leader (value_set_t, tree); static void value_insert_into_set (value_set_t, tree); static void insert_into_set (value_set_t, tree); -static void add_to_value (tree, tree); static value_set_t set_new (bool); static bool is_undefined_value (tree); -static bool expressions_equal_p (tree, tree); static tree create_expression_by_pieces (basic_block, tree, tree); /* We can add and remove elements and entries to and from sets @@ -293,117 +288,12 @@ static alloc_pool value_set_node_pool; static alloc_pool binary_node_pool; static alloc_pool unary_node_pool; -/* The value table that maps expressions to values. */ - -static htab_t value_table; /* The phi_translate_table caches phi translations for a given expression and predecessor. */ static htab_t phi_translate_table; -/* Compare two expressions E1 and E2 and return true if they are - equal. */ - -static 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_CODE (e2) - && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2)) - && operand_equal_p (e1, e2, 0)) - return true; - return false; -} - -/* 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 -{ - tree v, e; - hashval_t hashcode; -} *val_expr_pair_t; - - -/* 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) -{ - 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 true; - - return false; -} - - -/* Get the value handle of EXPR. This is the only correct way to get - the value handle for a "thing". - Returns NULL if the value handle does not exist. */ - -tree -get_value_handle (tree expr) -{ - /* We should never see these. */ - if (DECL_P (expr)) - abort (); - else if (TREE_CODE (expr) == SSA_NAME) - { - return SSA_NAME_VALUE (expr); - } - else if (TREE_CODE_CLASS (TREE_CODE (expr)) == 'c') - return expr; - else if (EXPR_P (expr)) - { - tree_ann_t ann = tree_ann (expr); - if (ann) - return ann->common.value_handle; - return NULL; - } - abort (); -} - - -/* Set the value handle for expression E to value V */ - -void -set_value_handle (tree e, tree v) -{ - if (DECL_P (e)) - abort (); - else if (TREE_CODE (e) == SSA_NAME) - SSA_NAME_VALUE (e) = v; - else if (EXPR_P (e)) - get_tree_ann (e)->common.value_handle = v; -} - /* A three tuple {e, pred, v} used to cache phi translations in the phi_translate_table. */ @@ -468,7 +358,7 @@ phi_trans_lookup (tree e, basic_block pred) struct expr_pred_trans_d ept; ept.e = e; ept.pred = pred; - ept.hashcode = iterative_hash_expr (e, (unsigned long) pred); + ept.hashcode = vn_compute (e, (unsigned long) pred); slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode, NO_INSERT); if (!slot) @@ -489,7 +379,7 @@ phi_trans_add (tree e, tree v, basic_block pred) new_pair->e = e; new_pair->pred = pred; new_pair->v = v; - new_pair->hashcode = iterative_hash_expr (e, (unsigned long) pred); + new_pair->hashcode = vn_compute (e, (unsigned long) pred); slot = htab_find_slot_with_hash (phi_translate_table, new_pair, new_pair->hashcode, INSERT); if (*slot) @@ -497,31 +387,11 @@ phi_trans_add (tree e, tree v, basic_block pred) *slot = (void *) new_pair; } -/* Search in TABLE for an existing instance of expression E, - and return its value, or NULL if none has been set. */ - -static inline tree -lookup (htab_t table, tree e) -{ - void **slot; - struct val_expr_pair_d vep = {NULL, NULL, 0}; - if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c') - return e; - vep.e = e; - vep.hashcode = iterative_hash_expr (e,0); - slot = htab_find_slot_with_hash (table, &vep, vep.hashcode, NO_INSERT); - if (!slot) - return NULL_TREE; - else - return ((val_expr_pair_t) *slot)->v; -} - /* Add expression E to the expression set of value V. */ -static inline void +void add_to_value (tree v, tree e) { - var_ann_t va; /* For values representing non-CST nodes, but still function invariant things we mark TREE_CONSTANT as true and set the tree chain to the actual constant. This is because unlike values @@ -536,106 +406,40 @@ add_to_value (tree v, tree e) TREE_CHAIN (v) = e; return; } - va = var_ann (v); - if (va->expr_set == NULL) - va->expr_set = set_new (false); - insert_into_set (va->expr_set, e); -} - -/* Insert E into TABLE with value V, and add expression E to the value - set for value V. */ - -static inline void -add (htab_t table, tree e, tree v) -{ - - void **slot; - val_expr_pair_t new_pair = xmalloc (sizeof (struct val_expr_pair_d)); - new_pair->e = e; - new_pair->v = v; - new_pair->hashcode = iterative_hash_expr (e, 0); - slot = htab_find_slot_with_hash (table, new_pair, new_pair->hashcode, - INSERT); - if (*slot) - free (*slot); - *slot = (void *) new_pair; - set_value_handle (e, v); - - add_to_value (v, e); - -} - -/* A unique counter that is incremented every time we create a new - value. */ -static int pre_uid; -/* Create a new value handle for expression EXPR. */ - -static tree -create_new_value (tree expr) -{ - tree a = create_tmp_var_raw (TREE_TYPE (expr), "value"); - create_var_ann (a); - var_ann (a)->uid = pre_uid++; + if (VALUE_HANDLE_EXPR_SET (v) == NULL) + VALUE_HANDLE_EXPR_SET (v) = set_new (false); - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Created value "); - print_generic_expr (dump_file, a, dump_flags); - fprintf (dump_file, " for "); - print_generic_expr (dump_file, expr, dump_flags); - fprintf (dump_file, "\n"); - } - return a; + insert_into_set (VALUE_HANDLE_EXPR_SET (v), e); } -/* Like lookup, but creates a new value for expression E if E doesn't - already have a value. - Return the existing/created value for E. */ - -static inline tree -lookup_or_add (htab_t table, tree e) -{ - tree x = lookup (table, e); - if (x == NULL_TREE) - { - tree v; - v = create_new_value (e); - add (table, e, v); - x = v; - } - set_value_handle (e, x); - return x; -} - /* Return true if value V exists in the bitmap for SET. */ static inline bool value_exists_in_set_bitmap (value_set_t set, tree v) { - if (TREE_CODE (v) != VAR_DECL) - abort (); - if (!set->values) return false; - return bitmap_bit_p (set->values, get_var_ann (v)->uid); + + return bitmap_bit_p (set->values, VALUE_HANDLE_ID (v)); } + /* Remove value V from the bitmap for SET. */ static void value_remove_from_set_bitmap (value_set_t set, tree v) { - if (TREE_CODE (v) != VAR_DECL) - abort (); #ifdef ENABLE_CHECKING if (!set->indexed) abort (); #endif + if (!set->values) return; - bitmap_clear_bit (set->values, get_var_ann (v)->uid); + + bitmap_clear_bit (set->values, VALUE_HANDLE_ID (v)); } @@ -645,20 +449,21 @@ value_remove_from_set_bitmap (value_set_t set, tree v) static inline void value_insert_into_set_bitmap (value_set_t set, tree v) { - if (TREE_CODE (v) != VAR_DECL) - abort (); #ifdef ENABLE_CHECKING if (!set->indexed) abort (); #endif + if (set->values == NULL) { set->values = BITMAP_GGC_ALLOC (); bitmap_clear (set->values); } - bitmap_set_bit (set->values, get_var_ann (v)->uid); + + bitmap_set_bit (set->values, VALUE_HANDLE_ID (v)); } + /* Create a new set. */ static value_set_t @@ -681,8 +486,6 @@ insert_into_set (value_set_t set, tree expr) { value_set_node_t newnode = pool_alloc (value_set_node_pool); tree val = get_value_handle (expr); - if (DECL_P (expr)) - abort (); if (val == NULL) abort (); @@ -873,7 +676,6 @@ value_insert_into_set (value_set_t set, tree expr) { tree val = get_value_handle (expr); - /* Constant and invariant values exist everywhere, and thus, actually keeping them in the sets is pointless. */ if (TREE_CONSTANT (val)) @@ -913,13 +715,16 @@ print_value_set (FILE *outfile, value_set_t set, } /* Print out the expressions that have VAL to OUTFILE. */ + void print_value_expressions (FILE *outfile, tree val) { - var_ann_t va = var_ann (val); - if (va && va->expr_set) - print_value_set (outfile, va->expr_set, - IDENTIFIER_POINTER (DECL_NAME (val)), 0); + if (VALUE_HANDLE_EXPR_SET (val)) + { + char s[10]; + sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val)); + print_value_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0); + } } @@ -983,7 +788,7 @@ phi_translate (tree expr, value_set_t set, basic_block pred, create_tree_ann (newexpr); TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1); TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2); - lookup_or_add (value_table, newexpr); + vn_lookup_or_add (newexpr); expr = newexpr; phi_trans_add (oldexpr, newexpr, pred); } @@ -1010,7 +815,7 @@ phi_translate (tree expr, value_set_t set, basic_block pred, memcpy (newexpr, expr, tree_size (expr)); create_tree_ann (newexpr); TREE_OPERAND (newexpr, 0) = get_value_handle (newop1); - lookup_or_add (value_table, newexpr); + vn_lookup_or_add (newexpr); expr = newexpr; phi_trans_add (oldexpr, newexpr, pred); } @@ -1035,7 +840,7 @@ phi_translate (tree expr, value_set_t set, basic_block pred, tree val; if (is_undefined_value (PHI_ARG_DEF (phi, i))) return NULL; - val = lookup_or_add (value_table, PHI_ARG_DEF (phi, i)); + val = vn_lookup_or_add (PHI_ARG_DEF (phi, i)); return PHI_ARG_DEF (phi, i); } } @@ -1328,15 +1133,6 @@ compute_antic (void) fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations); } -/* Get the expressions represented by value VAL. */ - -static value_set_t -get_expr_set (tree val) -{ - var_ann_t va = var_ann (val); - return va->expr_set; -} - /* Find a leader for an expression, or generate one using create_expression_by_pieces if it's ANTIC but @@ -1364,7 +1160,7 @@ find_or_generate_expression (basic_block block, tree expr, tree stmts) not really . */ if (genop == NULL) { - genop = get_expr_set (expr)->head->expr; + genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr; if (TREE_CODE_CLASS (TREE_CODE (genop)) != '1' && TREE_CODE_CLASS (TREE_CODE (genop)) != '2') abort (); @@ -1445,7 +1241,7 @@ create_expression_by_pieces (basic_block block, tree expr, tree stmts) } v = get_value_handle (expr); - add (value_table, name, v); + vn_add (name, v); insert_into_set (NEW_SETS (block), name); value_insert_into_set (AVAIL_OUT (block), name); if (dump_file && (dump_flags & TDF_DETAILS)) @@ -1610,7 +1406,7 @@ insert_aux (basic_block block) temp = create_tmp_var (type, "prephitmp"); add_referenced_tmp_var (temp); temp = create_phi_node (temp, block); - add (value_table, PHI_RESULT (temp), val); + vn_add (PHI_RESULT (temp), val); #if 0 if (!set_contains_value (AVAIL_OUT (block), val)) @@ -1679,17 +1475,19 @@ insert (void) fprintf (dump_file, "insert required %d iterations\n", num_iterations); } + /* Return true if EXPR has no defining statement in this procedure, *AND* isn't a live-on-entry parameter. */ + static bool is_undefined_value (tree expr) { - #ifdef ENABLE_CHECKING /* We should never be handed DECL's */ if (DECL_P (expr)) abort (); #endif + if (TREE_CODE (expr) == SSA_NAME) { /* XXX: Is this the correct test? */ @@ -1698,6 +1496,7 @@ is_undefined_value (tree expr) if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))) return true; } + return false; } @@ -1731,7 +1530,7 @@ compute_avail (basic_block block) { tree val; tree def = default_def (param); - val = lookup_or_add (value_table, def); + val = vn_lookup_or_add (def); insert_into_set (TMP_GEN (block), def); value_insert_into_set (AVAIL_OUT (block), def); } @@ -1746,6 +1545,7 @@ compute_avail (basic_block block) dom = get_immediate_dominator (CDI_DOMINATORS, block); if (dom) set_copy (AVAIL_OUT (block), AVAIL_OUT (dom)); + for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi)) { /* Ignore virtual PHIs until we can do PRE on expressions @@ -1753,7 +1553,7 @@ compute_avail (basic_block block) if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi)))) continue; - lookup_or_add (value_table, PHI_RESULT (phi)); + vn_lookup_or_add (PHI_RESULT (phi)); value_insert_into_set (AVAIL_OUT (block), PHI_RESULT (phi)); insert_into_set (PHI_GEN (block), PHI_RESULT (phi)); } @@ -1773,7 +1573,7 @@ compute_avail (basic_block block) for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++) { tree def = DEF_OP (STMT_DEF_OPS (stmt), j); - lookup_or_add (value_table, def); + vn_lookup_or_add (def); insert_into_set (TMP_GEN (block), def); value_insert_into_set (AVAIL_OUT (block), def); } @@ -1782,7 +1582,7 @@ compute_avail (basic_block block) tree use = USE_OP (STMT_USE_OPS (stmt), j); if (TREE_CODE (use) == SSA_NAME) { - lookup_or_add (value_table, use); + vn_lookup_or_add (use); insert_into_set (TMP_GEN (block), use); value_insert_into_set (AVAIL_OUT (block), use); } @@ -1801,7 +1601,7 @@ compute_avail (basic_block block) STRIP_USELESS_TYPE_CONVERSION (op1); if (is_gimple_min_invariant (op1)) { - add (value_table, op0, lookup_or_add (value_table, op1)); + vn_add (op0, vn_lookup_or_add (op1)); insert_into_set (TMP_GEN (block), op0); value_insert_into_set (AVAIL_OUT (block), op0); } @@ -1812,15 +1612,15 @@ compute_avail (basic_block block) tree newt; bop1 = TREE_OPERAND (op1, 0); bop2 = TREE_OPERAND (op1, 1); - val1 = lookup_or_add (value_table, bop1); - val2 = lookup_or_add (value_table, bop2); + val1 = vn_lookup_or_add (bop1); + val2 = vn_lookup_or_add (bop2); newt = pool_alloc (binary_node_pool); memcpy (newt, op1, tree_size (op1)); TREE_OPERAND (newt, 0) = val1; TREE_OPERAND (newt, 1) = val2; - val = lookup_or_add (value_table, newt); - add (value_table, op0, val); + val = vn_lookup_or_add (newt); + vn_add (op0, val); if (!is_undefined_value (bop1)) value_insert_into_set (EXP_GEN (block), bop1); if (!is_undefined_value (bop2)) @@ -1836,12 +1636,12 @@ compute_avail (basic_block block) tree val, val1; tree newt; uop = TREE_OPERAND (op1, 0); - val1 = lookup_or_add (value_table, uop); + val1 = vn_lookup_or_add (uop); newt = pool_alloc (unary_node_pool); memcpy (newt, op1, tree_size (op1)); TREE_OPERAND (newt, 0) = val1; - val = lookup_or_add (value_table, newt); - add (value_table, op0, val); + val = vn_lookup_or_add (newt); + vn_add (op0, val); if (!is_undefined_value (uop)) value_insert_into_set (EXP_GEN (block), uop); value_insert_into_set (EXP_GEN (block), newt); @@ -1850,8 +1650,8 @@ compute_avail (basic_block block) } else if (TREE_CODE (op1) == SSA_NAME) { - tree val = lookup_or_add (value_table, op1); - add (value_table, op0, val); + tree val = vn_lookup_or_add (op1); + vn_add (op0, val); if (!is_undefined_value (op1)) value_insert_into_set (EXP_GEN (block), op1); insert_into_set (TMP_GEN (block), op0); @@ -1863,7 +1663,7 @@ compute_avail (basic_block block) for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++) { tree def = DEF_OP (STMT_DEF_OPS (stmt), j); - lookup_or_add (value_table, def); + vn_lookup_or_add (def); insert_into_set (TMP_GEN (block), def); value_insert_into_set (AVAIL_OUT (block), def); if (def != op0) @@ -1874,7 +1674,7 @@ compute_avail (basic_block block) tree use = USE_OP (STMT_USE_OPS (stmt), j); if (TREE_CODE (use) == SSA_NAME) { - lookup_or_add (value_table, use); + vn_lookup_or_add (use); insert_into_set (TMP_GEN (block), use); value_insert_into_set (AVAIL_OUT (block), use); } @@ -1887,7 +1687,7 @@ compute_avail (basic_block block) for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++) { tree def = DEF_OP (STMT_DEF_OPS (stmt), j); - lookup_or_add (value_table, def); + vn_lookup_or_add (def); insert_into_set (TMP_GEN (block), def); value_insert_into_set (AVAIL_OUT (block), def); } @@ -1896,7 +1696,7 @@ compute_avail (basic_block block) tree use = USE_OP (STMT_USE_OPS (stmt), j); if (TREE_CODE (use) == SSA_NAME) { - lookup_or_add (value_table, use); + vn_lookup_or_add (use); insert_into_set (TMP_GEN (block), use); value_insert_into_set (AVAIL_OUT (block), use); } @@ -1904,13 +1704,14 @@ compute_avail (basic_block block) } } } + for (son = first_dom_son (CDI_DOMINATORS, block); son; son = next_dom_son (CDI_DOMINATORS, son)) compute_avail (son); - } + /* Eliminate fully redundant computations. */ static void @@ -1931,6 +1732,7 @@ eliminate (void) || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) || stmt_ann (stmt)->has_volatile_ops) continue; + /* Lookup the RHS of the expression, see if we have an available computation for it. If so, replace the RHS with the available computation. */ @@ -1945,8 +1747,8 @@ eliminate (void) || (TREE_CODE_CLASS (TREE_CODE (expr)) != '2' && TREE_CODE_CLASS (TREE_CODE (expr)) != '1')) continue; - sprime = find_leader (AVAIL_OUT (b), - lookup (value_table, t)); + + sprime = find_leader (AVAIL_OUT (b), vn_lookup (t)); if (sprime && sprime != t && may_propagate_copy (sprime, TREE_OPERAND (stmt, 1))) @@ -1965,11 +1767,11 @@ eliminate (void) modify_stmt (stmt); } } - } } } + /* Main entry point to the SSA-PRE pass. PHASE indicates which dump file from the DUMP_FILES array to use when @@ -1980,7 +1782,6 @@ execute_pre (void) { size_t tsize; basic_block bb; - pre_uid = num_referenced_vars; memset (&pre_stats, 0, sizeof (pre_stats)); FOR_ALL_BB (bb) { @@ -1989,8 +1790,6 @@ execute_pre (void) phi_translate_table = htab_create (511, expr_pred_trans_hash, expr_pred_trans_eq, free); - value_table = htab_create (511, val_expr_pair_hash, - val_expr_pair_expr_eq, free); value_set_pool = create_alloc_pool ("Value sets", sizeof (struct value_set), 30); value_set_node_pool = create_alloc_pool ("Value set nodes", @@ -2048,7 +1847,6 @@ execute_pre (void) free_alloc_pool (value_set_node_pool); free_alloc_pool (binary_node_pool); free_alloc_pool (unary_node_pool); - htab_delete (value_table); htab_delete (phi_translate_table); FOR_ALL_BB (bb) diff --git a/gcc/tree-ssa.c b/gcc/tree-ssa.c index a931d9f7fef..91bfaf54cf8 100644 --- a/gcc/tree-ssa.c +++ b/gcc/tree-ssa.c @@ -497,6 +497,7 @@ init_tree_ssa (void) init_ssa_operands (); init_ssanames (); init_phinodes (); + vn_init (); global_var = NULL_TREE; aliases_computed_p = false; } @@ -527,6 +528,7 @@ delete_tree_ssa (void) fini_ssanames (); fini_phinodes (); fini_ssa_operands (); + vn_delete (); global_var = NULL_TREE; BITMAP_XFREE (call_clobbered_vars); diff --git a/gcc/tree-vn.c b/gcc/tree-vn.c new file mode 100644 index 00000000000..de4c361feb8 --- /dev/null +++ b/gcc/tree-vn.c @@ -0,0 +1,257 @@ +/* Value Numbering routines for tree expressions. + Copyright (C) 2001, 2002, 2003, 2004 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, 59 Temple Place - Suite 330, +Boston, MA 02111-1307, 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 +{ + tree v, e; + 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 or statement P, compute a hash value number using the + code of the expression and its real operands. */ + +hashval_t +vn_compute (tree expr, hashval_t val) +{ + 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_CODE (e2) + && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2)) + && operand_equal_p (e1, e2, 0)) + 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) +{ + 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 true; + + return false; +} + + +/* 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)) + get_tree_ann (e)->common.value_handle = v; + else if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c') + /* Do nothing. Constants are their own value handles. */ + ; + else + abort (); +} + + +/* Insert E into VALUE_TABLE with value V, and add expression E to the + value set for value V. */ + +void +vn_add (tree e, tree v) +{ + void **slot; + val_expr_pair_t new_pair = xmalloc (sizeof (struct val_expr_pair_d)); + new_pair->e = e; + new_pair->v = v; + new_pair->hashcode = vn_compute (e, 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 (e, v); + + add_to_value (v, e); +} + + +/* Search in VALUE_TABLE for an existing instance of expression E, and + return its value, or NULL if none has been set. */ + +tree +vn_lookup (tree e) +{ + void **slot; + struct val_expr_pair_d vep = {NULL, NULL, 0}; + + if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c') + return e; + vep.e = e; + vep.hashcode = vn_compute (e, 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; +} + + +/* Like vn_lookup, but creates a new value for expression E if E doesn't + already have a value. Return the existing/created value for E. */ + +tree +vn_lookup_or_add (tree e) +{ + tree x = vn_lookup (e); + if (x == NULL_TREE) + { + tree v = make_value_handle (TREE_TYPE (e)); + + 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, e, dump_flags); + fprintf (dump_file, "\n"); + } + + vn_add (e, v); + x = v; + } + + set_value_handle (e, x); + + return x; +} + + +/* 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 generates and returns a new one. */ + +tree +get_value_handle (tree expr) +{ + if (TREE_CODE (expr) == SSA_NAME) + return SSA_NAME_VALUE (expr); + else if (TREE_CODE_CLASS (TREE_CODE (expr)) == 'c') + return expr; + else if (EXPR_P (expr) || DECL_P (expr)) + { + tree_ann_t ann = tree_ann (expr); + return ((ann) ? ann->common.value_handle : NULL_TREE); + } + + abort (); +} + + +/* 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); +} + + +/* Delete data used for value numbering. */ + +void +vn_delete (void) +{ + htab_delete (value_table); + value_table = NULL; +} diff --git a/gcc/tree.c b/gcc/tree.c index 716bc35fa70..25431d4495b 100644 --- a/gcc/tree.c +++ b/gcc/tree.c @@ -196,6 +196,7 @@ tree_size (tree node) case STATEMENT_LIST: return sizeof (struct tree_statement_list); case BLOCK: return sizeof (struct tree_block); + case VALUE_HANDLE: return sizeof (struct tree_value_handle); default: return lang_hooks.tree_size (code); @@ -1497,6 +1498,7 @@ tree_node_structure (tree t) case PLACEHOLDER_EXPR: return TS_COMMON; case STATEMENT_LIST: return TS_STATEMENT_LIST; case BLOCK: return TS_BLOCK; + case VALUE_HANDLE: return TS_VALUE_HANDLE; default: abort (); @@ -3851,7 +3853,8 @@ iterative_hash_expr (tree t, hashval_t val) code = TREE_CODE (t); class = TREE_CODE_CLASS (code); - if (class == 'd') + if (class == 'd' + || TREE_CODE (t) == VALUE_HANDLE) { /* Decls we can just compare by pointer. */ val = iterative_hash_object (t, val); diff --git a/gcc/tree.def b/gcc/tree.def index 57596a2b458..f7dabaf46c8 100644 --- a/gcc/tree.def +++ b/gcc/tree.def @@ -899,6 +899,12 @@ DEFTREECODE (EH_FILTER_EXPR, "eh_filter_expr", 's', 2) Use the interface in tree-iterator.h to access this node. */ DEFTREECODE (STATEMENT_LIST, "statement_list", 'x', 0) +/* Value handles. Artificial nodes to represent expressions in + partial redundancy elimination (tree-ssa-pre.c). These nodes are + used for expression canonicalization. If two expressions compute + the same value, they will be assigned the same value handle. */ +DEFTREECODE (VALUE_HANDLE, "value_handle", 'x', 0) + /* Local variables: mode:c diff --git a/gcc/tree.h b/gcc/tree.h index c404b84d1bc..3d3c6f11baa 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -2234,6 +2234,28 @@ struct tree_statement_list struct tree_statement_list_node *head; struct tree_statement_list_node *tail; }; + +#define VALUE_HANDLE_ID(NODE) \ + (VALUE_HANDLE_CHECK (NODE)->value_handle.id) + +#define VALUE_HANDLE_EXPR_SET(NODE) \ + (VALUE_HANDLE_CHECK (NODE)->value_handle.expr_set) + +/* Defined and used in tree-ssa-pre.c. */ +struct value_set; + +struct tree_value_handle GTY(()) +{ + struct tree_common common; + + /* The set of expressions represented by this handle. */ + struct value_set * GTY ((skip)) expr_set; + + /* Unique ID for this value handle. IDs are handed out in a + conveniently dense form starting at 0, so that we can make + bitmaps of value handles. */ + unsigned int id; +}; enum tree_node_structure_enum { TS_COMMON, @@ -2252,6 +2274,7 @@ enum tree_node_structure_enum { TS_PHI_NODE, TS_BLOCK, TS_STATEMENT_LIST, + TS_VALUE_HANDLE, LAST_TS_ENUM }; @@ -2278,6 +2301,7 @@ union tree_node GTY ((ptr_alias (union lang_tree_node), struct tree_phi_node GTY ((tag ("TS_PHI_NODE"))) phi; struct tree_block GTY ((tag ("TS_BLOCK"))) block; struct tree_statement_list GTY ((tag ("TS_STATEMENT_LIST"))) stmt_list; + struct tree_value_handle GTY ((tag ("TS_VALUE_HANDLE"))) value_handle; }; /* Standard named or nameless data types of the C compiler. */ |