diff options
| -rw-r--r-- | gcc/ChangeLog | 24 | ||||
| -rw-r--r-- | gcc/Makefile.in | 9 | ||||
| -rw-r--r-- | gcc/cgraphunit.c | 14 | ||||
| -rw-r--r-- | gcc/cp/ChangeLog | 8 | ||||
| -rw-r--r-- | gcc/cp/Make-lang.in | 2 | ||||
| -rw-r--r-- | gcc/cp/cp-tree.h | 2 | ||||
| -rw-r--r-- | gcc/cp/pt.c | 17 | ||||
| -rw-r--r-- | gcc/cp/tree.c | 4 | ||||
| -rw-r--r-- | gcc/java/ChangeLog | 5 | ||||
| -rw-r--r-- | gcc/java/lang.c | 6 | ||||
| -rw-r--r-- | gcc/langhooks-def.h | 2 | ||||
| -rw-r--r-- | gcc/langhooks.c | 2 | ||||
| -rw-r--r-- | gcc/langhooks.h | 2 | ||||
| -rw-r--r-- | gcc/pointer-set.c | 167 | ||||
| -rw-r--r-- | gcc/pointer-set.h | 32 | ||||
| -rw-r--r-- | gcc/tree-dfa.c | 9 | ||||
| -rw-r--r-- | gcc/tree-inline.c | 42 | ||||
| -rw-r--r-- | gcc/tree.h | 6 |
18 files changed, 296 insertions, 57 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 2475f9f..55ba888 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,27 @@ +2004-10-14 Matt Austern <austern@apple.com> + + * pointer-set.c: New file, special-purpose hash table. + * pointer-set.h: New file. + * tree.h (struct pointer_set_t): Declare as opaque type. + (tree_walk): Last argument is pointer_set_t* now. + * tree-inline.c (WALK_SUBTREE): Convert from htab to pset. + (walk_type_fields): + (walk_tree): Convert from htab_t to pointer_set_t for keeping + track of which nodes have already been visited. + (walk_tree_without_duplicates): Convert from htab_t to pointer_set_t. + * cgraphunit.c (cgraph_create_edges): Likewise. + (cgraph_characterize_statics_local): Likewise. + * tree-dfa.c (collect_dfa_stats): Likewise. + * langhooks-def.h (lhd_tree_inlining_walk_subtrees): Last arg is + pointer_set_t* now. + * langhooks.c (lhd_tree_inlining_walk_subtrees): Likewise. + * langhooks.h (struct lang_hooks_for_tree_inlining): Last arg type + of walk_subtrees is pointer_set_t* now. + * Makefile.in (OBJS-common): add pointer-set.o + (tree-inline.o): Depends on pointer-set.h + (tree-dfa.o): Likewise + (cgraphunit.o): Likewise + 2004-10-14 Geoffrey Keating <geoffk@apple.com> * config/rs6000/darwin.h (ASM_SPEC): Delete. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 622ecd2..432ce8f 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -914,7 +914,7 @@ OBJS-common = \ params.o postreload.o postreload-gcse.o predict.o \ insn-preds.o integrate.o intl.o jump.o langhooks.o lcm.o lists.o \ local-alloc.o loop.o modulo-sched.o optabs.o options.o opts.o \ - params.o postreload.o postreload-gcse.o predict.o \ + params.o pointer-set.o postreload.o postreload-gcse.o predict.o \ print-rtl.o print-tree.o value-prof.o var-tracking.o \ profile.o ra.o ra-build.o ra-colorize.o ra-debug.o ra-rewrite.o \ real.o recog.o reg-stack.o regclass.o regmove.o regrename.o \ @@ -1592,7 +1592,7 @@ tree-inline.o : tree-inline.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ $(TREE_H) $(RTL_H) $(EXPR_H) $(FLAGS_H) $(PARAMS_H) input.h insn-config.h \ $(INTEGRATE_H) $(VARRAY_H) $(HASHTAB_H) $(SPLAY_TREE_H) toplev.h \ langhooks.h $(C_COMMON_H) tree-inline.h $(CGRAPH_H) intl.h function.h \ - $(TREE_GIMPLE_H) + pointer-set.h $(TREE_GIMPLE_H) print-tree.o : print-tree.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \ $(GGC_H) langhooks.h real.h stor-layout.o : stor-layout.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ @@ -1686,7 +1686,7 @@ tree-iterator.o : tree-iterator.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) \ coretypes.h $(GGC_H) tree-iterator.h tree-gimple.h gt-tree-iterator.h tree-dfa.o : tree-dfa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h diagnostic.h \ - errors.h tree-inline.h $(HASHTAB_H) $(FLAGS_H) function.h $(TIMEVAR_H) \ + errors.h tree-inline.h $(HASHTAB_H) pointer-set.h $(FLAGS_H) function.h $(TIMEVAR_H) \ convert.h $(TM_H) coretypes.h langhooks.h \ $(TREE_DUMP_H) tree-pass.h params.h $(CGRAPH_H) tree-ssa-operands.o : tree-ssa-operands.c $(TREE_FLOW_H) $(CONFIG_H) \ @@ -1923,7 +1923,7 @@ cgraph.o : cgraph.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \ output.h intl.h cgraphunit.o : cgraphunit.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \ langhooks.h tree-inline.h toplev.h $(FLAGS_H) $(GGC_H) $(TARGET_H) $(CGRAPH_H) intl.h \ - function.h $(TREE_GIMPLE_H) $(TREE_FLOW_H) + pointer-set.h function.h $(TREE_GIMPLE_H) $(TREE_FLOW_H) coverage.o : coverage.c gcov-io.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \ $(TM_H) $(RTL_H) $(TREE_H) $(FLAGS_H) output.h $(REGS_H) $(EXPR_H) function.h \ toplev.h $(GGC_H) $(TARGET_H) langhooks.h $(COVERAGE_H) libfuncs.h \ @@ -2172,6 +2172,7 @@ lambda-code.o: lambda-code.c $(LAMBDA_H) $(GGC_H) $(SYSTEM_H) $(CONFIG_H) \ $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) cfgloop.h \ $(TREE_DATA_REF_H) $(SCEV_H) params.o : params.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(PARAMS_H) toplev.h +pointer-set.o: pointer-set.c pointer-set.h $(CONFIG_H) $(SYSTEM_H) hooks.o: hooks.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(HOOKS_H) pretty-print.o: $(CONFIG_H) $(SYSTEM_H) coretypes.h intl.h $(PRETTY_PRINT_H) \ $(TREE_H) diff --git a/gcc/cgraphunit.c b/gcc/cgraphunit.c index 5d0a32f..e942aad 100644 --- a/gcc/cgraphunit.c +++ b/gcc/cgraphunit.c @@ -186,7 +186,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "tree-flow.h" #include "tree-inline.h" #include "langhooks.h" -#include "hashtab.h" +#include "pointer-set.h" #include "toplev.h" #include "flags.h" #include "ggc.h" @@ -223,7 +223,7 @@ static int overall_insns; walk_tree_without_duplicates doesn't guarantee each node is visited once because it gets a new htab upon each recursive call from record_calls_1. */ -static htab_t visited_nodes; +static struct pointer_set_t *visited_nodes; static FILE *cgraph_dump_file; @@ -698,10 +698,9 @@ cgraph_create_edges (struct cgraph_node *node, tree body) { /* The nodes we're interested in are never shared, so walk the tree ignoring duplicates. */ - visited_nodes = htab_create (37, htab_hash_pointer, - htab_eq_pointer, NULL); + visited_nodes = pointer_set_create (); walk_tree (&body, record_call_1, node, visited_nodes); - htab_delete (visited_nodes); + pointer_set_destroy (visited_nodes); visited_nodes = NULL; } @@ -2288,8 +2287,7 @@ cgraph_characterize_statics_local (struct cgraph_node *fn) /* The nodes we're interested in are never shared, so walk the tree ignoring duplicates. */ - visited_nodes = htab_create (37, htab_hash_pointer, - htab_eq_pointer, NULL); + visited_nodes = pointer_set_create (); /* FIXME -- PROFILE-RESTRUCTURE: Remove creation of _decl_uid vars. */ l->statics_read_by_decl_uid = BITMAP_GGC_ALLOC (); @@ -2299,7 +2297,7 @@ cgraph_characterize_statics_local (struct cgraph_node *fn) fprintf (cgraph_dump_file, "\n local analysis of %s", cgraph_node_name (fn)); walk_tree (&DECL_SAVED_TREE (decl), scan_for_static_refs, fn, visited_nodes); - htab_delete (visited_nodes); + pointer_set_destroy (visited_nodes); visited_nodes = NULL; } diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog index 270a4eb..bb8678e 100644 --- a/gcc/cp/ChangeLog +++ b/gcc/cp/ChangeLog @@ -1,3 +1,11 @@ +2004-10-14 Matt Austern <austern@apple.com> + + * Make-lang.in (pt.o): depends on pointer-set.h + * cp-tree.h (cp_walk_subtrees): Last argument is pointer_set_t* now. + * pt.c (struct pair_fn_data): Use pointer_set_t, not htab_t + (for_each_template_parm): Convert from htab_t to pointer_set_t. + * tree.c (cp_walk_subtrees): Last argument is pointer_set_t* now. + 2004-10-13 Andrew Pinski <pinskia@physics.uc.edu> PR c++/17661 diff --git a/gcc/cp/Make-lang.in b/gcc/cp/Make-lang.in index 27ef4f2..891d271 100644 --- a/gcc/cp/Make-lang.in +++ b/gcc/cp/Make-lang.in @@ -260,7 +260,7 @@ cp/except.o: cp/except.c $(CXX_TREE_H) $(TM_H) flags.h $(RTL_H) except.h toplev. cp/expr.o: cp/expr.c $(CXX_TREE_H) $(TM_H) $(RTL_H) flags.h $(EXPR_H) toplev.h \ except.h $(TM_P_H) cp/pt.o: cp/pt.c $(CXX_TREE_H) $(TM_H) cp/decl.h \ - toplev.h $(RTL_H) except.h tree-inline.h gt-cp-pt.h + toplev.h $(RTL_H) except.h tree-inline.h pointer-set.h gt-cp-pt.h cp/error.o: cp/error.c $(CXX_TREE_H) $(TM_H) toplev.h $(DIAGNOSTIC_H) \ flags.h real.h $(LANGHOOKS_DEF_H) $(CXX_PRETTY_PRINT_H) cp/repo.o: cp/repo.c $(CXX_TREE_H) $(TM_H) toplev.h diagnostic.h \ diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h index 6f777b1..2350ab0 100644 --- a/gcc/cp/cp-tree.h +++ b/gcc/cp/cp-tree.h @@ -4215,7 +4215,7 @@ extern void verify_stmt_tree (tree); extern tree find_tree (tree, tree); extern linkage_kind decl_linkage (tree); extern tree cp_walk_subtrees (tree*, int*, walk_tree_fn, - void*, void*); + void*, struct pointer_set_t*); extern int cp_cannot_inline_tree_fn (tree*); extern tree cp_add_pending_fn_decls (void*,tree); extern int cp_is_overload_p (tree); diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c index 36ff89b..18e3c0a 100644 --- a/gcc/cp/pt.c +++ b/gcc/cp/pt.c @@ -32,6 +32,7 @@ Boston, MA 02111-1307, USA. */ #include "tm.h" #include "obstack.h" #include "tree.h" +#include "pointer-set.h" #include "flags.h" #include "cp-tree.h" #include "tree-inline.h" @@ -113,7 +114,8 @@ static tree convert_nontype_argument (tree, tree); static tree convert_template_argument (tree, tree, tree, tsubst_flags_t, int, tree); static tree get_bindings_overload (tree, tree, tree); -static int for_each_template_parm (tree, tree_fn_t, void*, htab_t); +static int for_each_template_parm (tree, tree_fn_t, void*, + struct pointer_set_t*); static tree build_template_parm_index (int, int, int, tree, tree); static int inline_needs_template_parms (tree); static void push_inline_template_parms_recursive (tree, int); @@ -4683,7 +4685,7 @@ struct pair_fn_data { tree_fn_t fn; void *data; - htab_t visited; + struct pointer_set_t *visited; }; /* Called from for_each_template_parm via walk_tree. */ @@ -4865,7 +4867,8 @@ for_each_template_parm_r (tree *tp, int *walk_subtrees, void *d) considered to be the function which always returns 1. */ static int -for_each_template_parm (tree t, tree_fn_t fn, void* data, htab_t visited) +for_each_template_parm (tree t, tree_fn_t fn, void* data, + struct pointer_set_t *visited) { struct pair_fn_data pfd; int result; @@ -4882,8 +4885,7 @@ for_each_template_parm (tree t, tree_fn_t fn, void* data, htab_t visited) if (visited) pfd.visited = visited; else - pfd.visited = htab_create (37, htab_hash_pointer, htab_eq_pointer, - NULL); + pfd.visited = pointer_set_create (); result = walk_tree (&t, for_each_template_parm_r, &pfd, @@ -4891,7 +4893,10 @@ for_each_template_parm (tree t, tree_fn_t fn, void* data, htab_t visited) /* Clean up. */ if (!visited) - htab_delete (pfd.visited); + { + pointer_set_destroy (pfd.visited); + pfd.visited = 0; + } return result; } diff --git a/gcc/cp/tree.c b/gcc/cp/tree.c index b4ced9b..134da23 100644 --- a/gcc/cp/tree.c +++ b/gcc/cp/tree.c @@ -1929,7 +1929,7 @@ cp_build_type_attribute_variant (tree type, tree attributes) tree cp_walk_subtrees (tree *tp, int *walk_subtrees_p, walk_tree_fn func, - void *data, void *htab) + void *data, struct pointer_set_t *pset) { enum tree_code code = TREE_CODE (*tp); location_t save_locus; @@ -1938,7 +1938,7 @@ cp_walk_subtrees (tree *tp, int *walk_subtrees_p, walk_tree_fn func, #define WALK_SUBTREE(NODE) \ do \ { \ - result = walk_tree (&(NODE), func, data, htab); \ + result = walk_tree (&(NODE), func, data, pset); \ if (result) goto out; \ } \ while (0) diff --git a/gcc/java/ChangeLog b/gcc/java/ChangeLog index d599add..126041a 100644 --- a/gcc/java/ChangeLog +++ b/gcc/java/ChangeLog @@ -1,3 +1,8 @@ +2004-10-14 Matt Austern <austern@apple.com> + + * lang.c (java_tree_inlining_walk_subtrees): Last arg is struct + pointer_set_t* now. + 2004-10-13 Tom Tromey <tromey@redhat.com> PR java/15578: diff --git a/gcc/java/lang.c b/gcc/java/lang.c index 3e4ba49..eae51a2 100644 --- a/gcc/java/lang.c +++ b/gcc/java/lang.c @@ -58,7 +58,7 @@ static void put_decl_string (const char *, int); static void put_decl_node (tree); static void java_print_error_function (diagnostic_context *, const char *); static tree java_tree_inlining_walk_subtrees (tree *, int *, walk_tree_fn, - void *, void *); + void *, struct pointer_set_t *); static int merge_init_test_initialization (void * *, void *); static int inline_init_test_initialization (void * *, void *); static bool java_can_use_bit_fields_p (void); @@ -706,7 +706,7 @@ java_tree_inlining_walk_subtrees (tree *tp ATTRIBUTE_UNUSED, int *subtrees ATTRIBUTE_UNUSED, walk_tree_fn func ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED, - void *htab ATTRIBUTE_UNUSED) + struct pointer_set_t *pset ATTRIBUTE_UNUSED) { enum tree_code code; tree result; @@ -714,7 +714,7 @@ java_tree_inlining_walk_subtrees (tree *tp ATTRIBUTE_UNUSED, #define WALK_SUBTREE(NODE) \ do \ { \ - result = walk_tree (&(NODE), func, data, htab); \ + result = walk_tree (&(NODE), func, data, pset); \ if (result) \ return result; \ } \ diff --git a/gcc/langhooks-def.h b/gcc/langhooks-def.h index 8b57a03..d036d84 100644 --- a/gcc/langhooks-def.h +++ b/gcc/langhooks-def.h @@ -73,7 +73,7 @@ extern size_t lhd_tree_size (enum tree_code); /* Declarations of default tree inlining hooks. */ extern tree lhd_tree_inlining_walk_subtrees (tree *, int *, walk_tree_fn, - void *, void *); + void *, struct pointer_set_t*); extern int lhd_tree_inlining_cannot_inline_tree_fn (tree *); extern int lhd_tree_inlining_disregard_inline_limits (tree); extern tree lhd_tree_inlining_add_pending_fn_decls (void *, tree); diff --git a/gcc/langhooks.c b/gcc/langhooks.c index 199c93e..0cf31be 100644 --- a/gcc/langhooks.c +++ b/gcc/langhooks.c @@ -298,7 +298,7 @@ lhd_tree_inlining_walk_subtrees (tree *tp ATTRIBUTE_UNUSED, int *subtrees ATTRIBUTE_UNUSED, walk_tree_fn func ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED, - void *htab ATTRIBUTE_UNUSED) + struct pointer_set_t *pset ATTRIBUTE_UNUSED) { return NULL_TREE; } diff --git a/gcc/langhooks.h b/gcc/langhooks.h index 43749a2..f57f148 100644 --- a/gcc/langhooks.h +++ b/gcc/langhooks.h @@ -35,7 +35,7 @@ struct lang_hooks_for_tree_inlining { tree (*walk_subtrees) (tree *, int *, tree (*) (tree *, int *, void *), - void *, void *); + void *, struct pointer_set_t*); int (*cannot_inline_tree_fn) (tree *); int (*disregard_inline_limits) (tree); tree (*add_pending_fn_decls) (void *, tree); diff --git a/gcc/pointer-set.c b/gcc/pointer-set.c new file mode 100644 index 0000000..510ae43 --- /dev/null +++ b/gcc/pointer-set.c @@ -0,0 +1,167 @@ +/* Set operations on pointers + Copyright (C) 2004 Free Software Foundation, Inc. + +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 "pointer-set.h" + +/* A pointer sets is represented as a simple open-addressing hash + table. Simplifications: The hash code is based on the value of the + pointer, not what it points to. The number of buckets is always a + power of 2. Null pointers are a reserved value. Deletion is not + supported. There is no mechanism for user control of hash + function, equality comparison, initial size, or resizing policy. +*/ + +struct pointer_set_t +{ + size_t log_slots; + size_t n_slots; /* n_slots = 2^log_slots */ + size_t n_elements; + + void **slots; +}; + +/* Use the multiplicative method, as described in Knuth 6.4, to obtain + a hash code for P in the range [0, MAX). MAX == 2^LOGMAX. + + Summary of this method: Multiply p by some number A that's + relatively prime to 2^sizeof(size_t). The result is two words. + Discard the most significant word, and return the most significant + N bits of the least significant word. As suggested by Knuth, our + choice for A is the integer part of 2^32 / phi, where phi is the + golden ratio. + + We don't need to do anything special for full-width multiplication + because we're only interested in the least significant word of the + product, and unsigned arithmetic in C is modulo the word size. */ + +static inline size_t +hash1 (const void *p, unsigned long max, unsigned long logmax) +{ + const unsigned long A = 0x9e3779b9u; + const unsigned long shift = sizeof(unsigned long) * CHAR_BIT - logmax; + + return ((A * (unsigned long) p) >> shift) & (max - 1); +} + +/* Allocate an empty pointer set. */ +struct pointer_set_t * +pointer_set_create (void) +{ + struct pointer_set_t *result = XNEW (struct pointer_set_t); + + result->n_elements = 0; + result->log_slots = 8; + result->n_slots = (size_t) 1 << result->log_slots; + + result->slots = XCNEWVEC (void *, result->n_slots); + return result; +} + +/* Reclaims all memory associated with PSET. */ +void pointer_set_destroy (struct pointer_set_t *pset) +{ + XDELETEVEC (pset->slots); + XDELETE (pset); +} + +/* Returns nonzero if PSET contains P. P must be nonnull. + + Collisions are resolved by linear probing. More complicated + collision management schemes are only useful when the load factor + significatly exceeds 0.5, and we never let that happen. */ +int +pointer_set_contains (struct pointer_set_t *pset, void *p) +{ + size_t n = hash1 (p, pset->n_slots, pset->log_slots); + + while (true) + { + if (pset->slots[n] == p) + return 1; + else if (pset->slots[n] == 0) + return 0; + else + { + ++n; + if (n == pset->n_slots) + n = 0; + } + } +} + +/* Subroutine of pointer_set_insert. Inserts P into an empty + element of SLOTS, an array of length N_SLOTS. Returns nonzero + if P was already present in N_SLOTS. */ +static int +insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots) +{ + size_t n = hash1 (p, n_slots, log_slots); + while (true) + { + if (slots[n] == p) + return 1; + else if (slots[n] == 0) + { + slots[n] = p; + return 0; + } + else + { + ++n; + if (n == n_slots) + n = 0; + } + } +} + +/* Inserts P into PSET if it wasn't already there. Returns nonzero + if it was already there. P must be nonnull. */ +int +pointer_set_insert (struct pointer_set_t *pset, void *p) +{ + if (insert_aux (p, pset->slots, pset->n_slots, pset->log_slots)) + return 1; + + /* We've inserted a new element. Expand the table if necessary to keep + the load factor small. */ + ++pset->n_elements; + if (pset->n_elements > pset->n_slots / 4) + { + size_t new_log_slots = pset->log_slots + 1; + size_t new_n_slots = pset->n_slots * 2; + void **new_slots = XCNEWVEC (void *, new_n_slots); + size_t i; + + for (i = 0; i < pset->n_slots; ++i) + { + if (pset->slots[i]) + insert_aux (pset->slots[i], new_slots, new_n_slots, new_log_slots); + } + + XDELETEVEC (pset->slots); + pset->n_slots = new_n_slots; + pset->log_slots = new_log_slots; + pset->slots = new_slots; + } + + return 0; +} diff --git a/gcc/pointer-set.h b/gcc/pointer-set.h new file mode 100644 index 0000000..65ac9ee --- /dev/null +++ b/gcc/pointer-set.h @@ -0,0 +1,32 @@ +/* Set operations on pointers + Copyright (C) 2004 Free Software Foundation, Inc. + +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. */ + +#ifndef POINTER_SET_H +#define POINTER_SET_H + +struct pointer_set_t; + +struct pointer_set_t *pointer_set_create (void); +void pointer_set_destroy (struct pointer_set_t *pset); + +int pointer_set_contains (struct pointer_set_t *pset, void *p); +int pointer_set_insert (struct pointer_set_t *pset, void *p); + +#endif /* POINTER_SET_H */ diff --git a/gcc/tree-dfa.c b/gcc/tree-dfa.c index 29de670..aa156c2 100644 --- a/gcc/tree-dfa.c +++ b/gcc/tree-dfa.c @@ -24,6 +24,7 @@ Boston, MA 02111-1307, USA. */ #include "coretypes.h" #include "tm.h" #include "hashtab.h" +#include "pointer-set.h" #include "tree.h" #include "rtl.h" #include "tm_p.h" @@ -759,7 +760,7 @@ debug_dfa_stats (void) static void collect_dfa_stats (struct dfa_stats_d *dfa_stats_p) { - htab_t htab; + struct pointer_set_t *pset; basic_block bb; block_stmt_iterator i; @@ -769,13 +770,13 @@ collect_dfa_stats (struct dfa_stats_d *dfa_stats_p) /* Walk all the trees in the function counting references. Start at basic block 0, but don't stop at block boundaries. */ - htab = htab_create (30, htab_hash_pointer, htab_eq_pointer, NULL); + pset = pointer_set_create (); for (i = bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i); bsi_next (&i)) walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p, - (void *) htab); + pset); - htab_delete (htab); + pointer_set_destroy (pset); FOR_EACH_BB (bb) { diff --git a/gcc/tree-inline.c b/gcc/tree-inline.c index 0583eb4..0e2f85a 100644 --- a/gcc/tree-inline.c +++ b/gcc/tree-inline.c @@ -35,6 +35,7 @@ Boston, MA 02111-1307, USA. */ #include "integrate.h" #include "varray.h" #include "hashtab.h" +#include "pointer-set.h" #include "splay-tree.h" #include "langhooks.h" #include "cgraph.h" @@ -1877,7 +1878,7 @@ save_body (tree fn, tree *arg_copy, tree *sc_copy) #define WALK_SUBTREE(NODE) \ do \ { \ - result = walk_tree (&(NODE), func, data, htab); \ + result = walk_tree (&(NODE), func, data, pset); \ if (result) \ return result; \ } \ @@ -1888,7 +1889,8 @@ save_body (tree fn, tree *arg_copy, tree *sc_copy) value are as for walk_tree. */ static tree -walk_type_fields (tree type, walk_tree_fn func, void *data, void *htab) +walk_type_fields (tree type, walk_tree_fn func, void *data, + struct pointer_set_t *pset) { tree result = NULL_TREE; @@ -1906,7 +1908,7 @@ walk_type_fields (tree type, walk_tree_fn func, void *data, void *htab) if (POINTER_TYPE_P (TREE_TYPE (type)) && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type))) && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type)))) - && !htab) + && !pset) { result = walk_tree_without_duplicates (&TREE_TYPE (type), func, data); @@ -1971,13 +1973,12 @@ walk_type_fields (tree type, walk_tree_fn func, void *data, void *htab) /* Apply FUNC to all the sub-trees of TP in a pre-order traversal. FUNC is called with the DATA and the address of each sub-tree. If FUNC returns a non-NULL value, the traversal is aborted, and the value returned by FUNC - is returned. If HTAB is non-NULL it is used to record the nodes visited, + is returned. If PSET is non-NULL it is used to record the nodes visited, and to avoid visiting a node more than once. */ tree -walk_tree (tree *tp, walk_tree_fn func, void *data, void *htab_) +walk_tree (tree *tp, walk_tree_fn func, void *data, struct pointer_set_t *pset) { - htab_t htab = (htab_t) htab_; enum tree_code code; int walk_subtrees; tree result; @@ -1995,17 +1996,10 @@ walk_tree (tree *tp, walk_tree_fn func, void *data, void *htab_) if (!*tp) return NULL_TREE; - if (htab) - { - void **slot; - - /* Don't walk the same tree twice, if the user has requested - that we avoid doing so. */ - slot = htab_find_slot (htab, *tp, INSERT); - if (*slot) - return NULL_TREE; - *slot = *tp; - } + /* Don't walk the same tree twice, if the user has requested + that we avoid doing so. */ + if (pset && pointer_set_insert (pset, *tp)) + return NULL_TREE; /* Call the function. */ walk_subtrees = 1; @@ -2029,7 +2023,7 @@ walk_tree (tree *tp, walk_tree_fn func, void *data, void *htab_) } result = lang_hooks.tree_inlining.walk_subtrees (tp, &walk_subtrees, func, - data, htab); + data, pset); if (result || ! walk_subtrees) return result; @@ -2053,7 +2047,7 @@ walk_tree (tree *tp, walk_tree_fn func, void *data, void *htab_) if (result || !walk_subtrees) return NULL_TREE; - result = walk_type_fields (*type_p, func, data, htab_); + result = walk_type_fields (*type_p, func, data, pset); if (result) return result; @@ -2124,7 +2118,7 @@ walk_tree (tree *tp, walk_tree_fn func, void *data, void *htab_) /* If this is a type, walk the needed fields in the type. */ else if (TYPE_P (*tp)) { - result = walk_type_fields (*tp, func, data, htab_); + result = walk_type_fields (*tp, func, data, pset); if (result) return result; } @@ -2227,11 +2221,11 @@ tree walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data) { tree result; - htab_t htab; + struct pointer_set_t *pset; - htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL); - result = walk_tree (tp, func, data, htab); - htab_delete (htab); + pset = pointer_set_create (); + result = walk_tree (tp, func, data, pset); + pointer_set_destroy (pset); return result; } @@ -3790,10 +3790,14 @@ extern void dwarf2out_return_reg (const char *, unsigned); /* In tree-inline.c */ +/* The type of a set of already-visited pointers. Functions for creating + and manipulating it are declared in pointer-set.h */ +struct pointer_set_t; + /* The type of a callback function for walking over tree structure. */ typedef tree (*walk_tree_fn) (tree *, int *, void *); -extern tree walk_tree (tree*, walk_tree_fn, void*, void*); +extern tree walk_tree (tree*, walk_tree_fn, void*, struct pointer_set_t*); extern tree walk_tree_without_duplicates (tree*, walk_tree_fn, void*); /* In tree-dump.c */ |