From d88f311b6384b7fc22fe799225097782cb502b9d Mon Sep 17 00:00:00 2001 From: =?utf8?q?Martin=20v=2E=20L=C3=B6wis?= Date: Sun, 19 Mar 2000 17:53:38 +0000 Subject: [PATCH] Makefile.in (tree.o): Depend on HASHTAB_H. * Makefile.in (tree.o): Depend on HASHTAB_H. * tree.c: Include hashtab.h. (struct type_hash): Remove next field. (TYPE_HASH_SIZE): Remove. (TYPE_HASH_INITIAL_SIZE): New define. (type_hash_table): Change type to htab_t. (type_hash_eq, type_hash_hash, print_type_hash_statistics, mark_hash_entry): New functions. (init_obstacks): Allocate type hash. (type_hash_lookup): Use htab functions. (type_hash_add, mark_type_hash): Likewise. (dump_tree_statistics): Call print_type_hash_statistics. From-SVN: r32642 --- gcc/ChangeLog | 15 +++++ gcc/Makefile.in | 2 +- gcc/tree.c | 153 +++++++++++++++++++++++++++++++----------------- 3 files changed, 116 insertions(+), 54 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index a875241b0a3..3dce7cf551d 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,18 @@ +2000-03-18 Martin v. Löwis + + * Makefile.in (tree.o): Depend on HASHTAB_H. + * tree.c: Include hashtab.h. + (struct type_hash): Remove next field. + (TYPE_HASH_SIZE): Remove. + (TYPE_HASH_INITIAL_SIZE): New define. + (type_hash_table): Change type to htab_t. + (type_hash_eq, type_hash_hash, print_type_hash_statistics, + mark_hash_entry): New functions. + (init_obstacks): Allocate type hash. + (type_hash_lookup): Use htab functions. + (type_hash_add, mark_type_hash): Likewise. + (dump_tree_statistics): Call print_type_hash_statistics. + 2000-03-19 Kaveh R. Ghazi * rs6000/t-aix41: New file. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index d849adace75..6fa0873584b 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1476,7 +1476,7 @@ prefix.o: prefix.c $(CONFIG_H) system.h Makefile prefix.h convert.o: convert.c $(CONFIG_H) system.h $(TREE_H) flags.h convert.h toplev.h tree.o : tree.c $(CONFIG_H) system.h $(TREE_H) flags.h function.h toplev.h \ - ggc.h + ggc.h $(HASHTAB_H) print-tree.o : print-tree.c $(CONFIG_H) system.h $(TREE_H) ggc.h stor-layout.o : stor-layout.c $(CONFIG_H) system.h $(TREE_H) flags.h \ function.h $(EXPR_H) $(RTL_H) toplev.h ggc.h diff --git a/gcc/tree.c b/gcc/tree.c index 2693995675c..9dbdeea04b3 100644 --- a/gcc/tree.c +++ b/gcc/tree.c @@ -43,6 +43,7 @@ Boston, MA 02111-1307, USA. */ #include "obstack.h" #include "toplev.h" #include "ggc.h" +#include "hashtab.h" #define obstack_chunk_alloc xmalloc #define obstack_chunk_free free @@ -252,30 +253,34 @@ int (*lang_get_alias_set) PARAMS ((tree)); codes are made. */ #define TYPE_HASH(TYPE) ((unsigned long) (TYPE) & 0777777) -/* Each hash table slot is a bucket containing a chain - of these structures. */ +/* Since we cannot rehash a type after it is in the table, we have to + keep the hash code. */ struct type_hash { - struct type_hash *next; /* Next structure in the bucket. */ - unsigned int hashcode; /* Hash code of this type. */ - tree type; /* The type recorded here. */ + unsigned long hash; + tree type; }; -/* Now here is the hash table. When recording a type, it is added - to the slot whose index is the hash code mod the table size. - Note that the hash table is used for several kinds of types - (function types, array types and array index range types, for now). - While all these live in the same table, they are completely independent, - and the hash code is computed differently for each of these. */ +/* Initial size of the hash table (rounded to next prime). */ +#define TYPE_HASH_INITIAL_SIZE 1000 -#define TYPE_HASH_SIZE 59 -struct type_hash *type_hash_table[TYPE_HASH_SIZE]; +/* Now here is the hash table. When recording a type, it is added to + the slot whose index is the hash code. Note that the hash table is + used for several kinds of types (function types, array types and + array index range types, for now). While all these live in the + same table, they are completely independent, and the hash code is + computed differently for each of these. */ + +htab_t type_hash_table; static void build_real_from_int_cst_1 PARAMS ((PTR)); static void set_type_quals PARAMS ((tree, int)); static void append_random_chars PARAMS ((char *)); static void mark_type_hash PARAMS ((void *)); +static int type_hash_eq PARAMS ((const void*, const void*)); +static unsigned int type_hash_hash PARAMS ((const void*)); +static void print_type_hash_statistics PARAMS((void)); /* If non-null, these are language-specific helper functions for unsave_expr_now. If present, LANG_UNSAVE is called before its @@ -328,11 +333,9 @@ init_obstacks () ggc_add_tree_root (hash_table, sizeof hash_table / sizeof (tree)); /* Initialize the hash table of types. */ - bzero ((char *) type_hash_table, - sizeof type_hash_table / sizeof type_hash_table[0]); - ggc_add_root (type_hash_table, - sizeof type_hash_table / sizeof type_hash_table [0], - sizeof type_hash_table[0], mark_type_hash); + type_hash_table = htab_create (TYPE_HASH_INITIAL_SIZE, type_hash_hash, + type_hash_eq, 0); + ggc_add_root (&type_hash_table, 1, sizeof type_hash_table, mark_type_hash); ggc_add_tree_root (global_trees, TI_MAX); ggc_add_tree_root (integer_types, itk_none); } @@ -3963,6 +3966,49 @@ type_hash_list (list) return hashcode; } +/* These are the Hashtable callback functions. */ + +/* Returns true if the types are equal. */ + +static int +type_hash_eq (va, vb) + const void *va; + const void *vb; +{ + const struct type_hash *a = va, *b = vb; + if (a->hash == b->hash + && TREE_CODE (a->type) == TREE_CODE (b->type) + && TREE_TYPE (a->type) == TREE_TYPE (b->type) + && attribute_list_equal (TYPE_ATTRIBUTES (a->type), + TYPE_ATTRIBUTES (b->type)) + && TYPE_ALIGN (a->type) == TYPE_ALIGN (b->type) + && (TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type) + || tree_int_cst_equal (TYPE_MAX_VALUE (a->type), + TYPE_MAX_VALUE (b->type))) + && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type) + || tree_int_cst_equal (TYPE_MIN_VALUE (a->type), + TYPE_MIN_VALUE (b->type))) + /* Note that TYPE_DOMAIN is TYPE_ARG_TYPES for FUNCTION_TYPE. */ + && (TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type) + || (TYPE_DOMAIN (a->type) + && TREE_CODE (TYPE_DOMAIN (a->type)) == TREE_LIST + && TYPE_DOMAIN (b->type) + && TREE_CODE (TYPE_DOMAIN (b->type)) == TREE_LIST + && type_list_equal (TYPE_DOMAIN (a->type), + TYPE_DOMAIN (b->type))))) + return 1; + return 0; +} + +/* Return the cached hash value. */ + +static unsigned int +type_hash_hash (item) + const void *item; +{ + return ((const struct type_hash*)item)->hash; +} + /* Look in the type hash table for a type isomorphic to TYPE. If one is found, return it. Otherwise return 0. */ @@ -3971,36 +4017,19 @@ type_hash_lookup (hashcode, type) unsigned int hashcode; tree type; { - register struct type_hash *h; + struct type_hash *h, in; /* The TYPE_ALIGN field of a type is set by layout_type(), so we must call that routine before comparing TYPE_ALIGNs. */ layout_type (type); - for (h = type_hash_table[hashcode % TYPE_HASH_SIZE]; h; h = h->next) - if (h->hashcode == hashcode - && TREE_CODE (h->type) == TREE_CODE (type) - && TREE_TYPE (h->type) == TREE_TYPE (type) - && attribute_list_equal (TYPE_ATTRIBUTES (h->type), - TYPE_ATTRIBUTES (type)) - && TYPE_ALIGN (h->type) == TYPE_ALIGN (type) - && (TYPE_MAX_VALUE (h->type) == TYPE_MAX_VALUE (type) - || tree_int_cst_equal (TYPE_MAX_VALUE (h->type), - TYPE_MAX_VALUE (type))) - && (TYPE_MIN_VALUE (h->type) == TYPE_MIN_VALUE (type) - || tree_int_cst_equal (TYPE_MIN_VALUE (h->type), - TYPE_MIN_VALUE (type))) - /* Note that TYPE_DOMAIN is TYPE_ARG_TYPES for FUNCTION_TYPE. */ - && (TYPE_DOMAIN (h->type) == TYPE_DOMAIN (type) - || (TYPE_DOMAIN (h->type) - && TREE_CODE (TYPE_DOMAIN (h->type)) == TREE_LIST - && TYPE_DOMAIN (type) - && TREE_CODE (TYPE_DOMAIN (type)) == TREE_LIST - && type_list_equal (TYPE_DOMAIN (h->type), - TYPE_DOMAIN (type))))) - return h->type; + in.hash = hashcode; + in.type = type; - return 0; + h = htab_find_with_hash (type_hash_table, &in, hashcode); + if (h) + return h->type; + return NULL_TREE; } /* Add an entry to the type-hash-table @@ -4011,13 +4040,14 @@ type_hash_add (hashcode, type) unsigned int hashcode; tree type; { - register struct type_hash *h; + struct type_hash *h; + void **loc; h = (struct type_hash *) permalloc (sizeof (struct type_hash)); - h->hashcode = hashcode; + h->hash = hashcode; h->type = type; - h->next = type_hash_table[hashcode % TYPE_HASH_SIZE]; - type_hash_table[hashcode % TYPE_HASH_SIZE] = h; + loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, 1); + *(struct type_hash**)loc = h; } /* Given TYPE, and HASHCODE its hash code, return the canonical @@ -4064,19 +4094,35 @@ type_hash_canon (hashcode, type) return type; } -/* Mark ARG (which is really a struct type_hash **) for GC. */ +/* Callback function for htab_traverse. */ + +static int +mark_hash_entry (entry, param) + void **entry; + void *param ATTRIBUTE_UNUSED; +{ + struct type_hash *p = *(struct type_hash **)entry; + ggc_mark_tree (p->type); + /* Continue scan. */ + return 1; +} + +/* Mark ARG (which is really a htab_t *) for GC. */ static void mark_type_hash (arg) void *arg; { - struct type_hash *t = *(struct type_hash **) arg; + htab_t t = *(htab_t *) arg; + htab_traverse (t, mark_hash_entry, 0); +} - while (t) - { - ggc_mark_tree (t->type); - t = t->next; - } +static void +print_type_hash_statistics () +{ + fprintf (stderr, "Type hash: size %d, %d elements, %f collisions\n", + htab_size (type_hash_table), htab_elements (type_hash_table), + htab_collisions (type_hash_table)); } /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes @@ -5249,6 +5295,7 @@ dump_tree_statistics () print_obstack_statistics ("temporary_obstack", &temporary_obstack); print_obstack_statistics ("momentary_obstack", &momentary_obstack); print_obstack_statistics ("temp_decl_obstack", &temp_decl_obstack); + print_type_hash_statistics (); print_lang_statistics (); } -- 2.30.2