Message ID | 20130827123338.GA574@redhat.com |
---|---|
State | New |
Headers | show |
On Tue, Aug 27, 2013 at 2:33 PM, Marek Polacek <polacek@redhat.com> wrote: > It turned out that for tree -> tree mapping we don't need the hash > table at all; pointer map is much more convenient. So this patch > weeds out the hash table out of ubsan and introduces pointer map > instead. Quite a lot of code could go away--no need to set the > alloc pools up etc. > > Regtested, ran bootstrap-ubsan on x86_64-linux. Applying to the > ubsan branch. You can use the type-safe pointer_map <tree> now (ok, only the data type is type safe, the pointer is still void). Richard. > 2013-08-27 Marek Polacek <polacek@redhat.com> > > * ubsan.c: Use pointer map instead of hash table. > > --- gcc/ubsan.c.mp 2013-08-27 12:31:04.136213922 +0200 > +++ gcc/ubsan.c 2013-08-27 12:31:10.361236456 +0200 > @@ -22,109 +22,42 @@ along with GCC; see the file COPYING3. > #include "system.h" > #include "coretypes.h" > #include "tree.h" > -#include "alloc-pool.h" > #include "cgraph.h" > #include "gimple.h" > -#include "hash-table.h" > +#include "pointer-set.h" > #include "output.h" > #include "toplev.h" > #include "ubsan.h" > #include "c-family/c-common.h" > > -/* This type represents an entry in the hash table; this hash table > - maps from a TYPE to a ubsan type descriptor VAR_DECL for that type. */ > -struct ubsan_typedesc > -{ > - /* This represents the type of a variable. */ > - tree type; > - > - /* This is the VAR_DECL of the type. */ > - tree decl; > -}; > - > -static alloc_pool ubsan_typedesc_alloc_pool; > - > -/* Hash table for type descriptors. */ > -struct ubsan_typedesc_hasher > - : typed_noop_remove <ubsan_typedesc> > -{ > - typedef ubsan_typedesc value_type; > - typedef ubsan_typedesc compare_type; > - > - static inline hashval_t hash (const value_type *); > - static inline bool equal (const value_type *, const compare_type *); > -}; > - > -/* Hash a memory reference. */ > - > -inline hashval_t > -ubsan_typedesc_hasher::hash (const ubsan_typedesc *data) > -{ > - return iterative_hash_object (TYPE_UID (data->type), 0); > -} > - > -/* Compare two data types. */ > - > -inline bool > -ubsan_typedesc_hasher::equal (const ubsan_typedesc *d1, > - const ubsan_typedesc *d2) > -{ > - /* Here, the types should have identical __typekind, > - __typeinfo and __typename. */ > - return d1->type == d2->type; > -} > - > -static hash_table <ubsan_typedesc_hasher> ubsan_typedesc_ht; > +/* Map a TYPE to an ubsan type descriptor VAR_DECL for that type. */ > +static pointer_map_t *typedesc_map; > > -/* Initializes an instance of ubsan_typedesc. */ > +/* Insert DECL as the VAR_DECL for TYPE in the TYPEDESC_MAP. */ > > static void > -ubsan_typedesc_init (ubsan_typedesc *data, tree type, tree decl) > +insert_decl_for_type (tree decl, tree type) > { > - data->type = type; > - data->decl = decl; > + void **slot = pointer_map_insert (typedesc_map, type); > + gcc_assert (*slot == NULL); > + *slot = decl; > } > > -/* This creates the alloc pool used to store the instances of > - ubsan_typedesc that are stored in the hash table ubsan_typedesc_ht. */ > +/* Find the VAR_DECL for TYPE in TYPEDESC_MAP. If TYPE does not > + exist in the map, return NULL_TREE, otherwise, return the VAR_DECL > + we found. */ > > -static alloc_pool > -ubsan_typedesc_get_alloc_pool () > -{ > - if (ubsan_typedesc_alloc_pool == NULL) > - ubsan_typedesc_alloc_pool = create_alloc_pool ("ubsan_typedesc", > - sizeof (ubsan_typedesc), > - 10); > - return ubsan_typedesc_alloc_pool; > -} > - > -/* Returns a reference to the hash table containing data type. > - This function ensures that the hash table is created. */ > - > -static hash_table <ubsan_typedesc_hasher> & > -get_typedesc_hash_table () > -{ > - if (!ubsan_typedesc_ht.is_created ()) > - ubsan_typedesc_ht.create (10); > - > - return ubsan_typedesc_ht; > -} > - > -/* Allocates memory for an instance of ubsan_typedesc into the memory > - pool returned by ubsan_typedesc_get_alloc_pool and initialize it. > - TYPE describes a particular type, DECL is its VAR_DECL. */ > - > -static ubsan_typedesc * > -ubsan_typedesc_new (tree type, tree decl) > +static tree > +lookup_decl_for_type (tree type) > { > - ubsan_typedesc *desc = > - (ubsan_typedesc *) pool_alloc (ubsan_typedesc_get_alloc_pool ()); > - > - ubsan_typedesc_init (desc, type, decl); > - return desc; > + /* If the pointer map is not initialized yet, create it now. */ > + if (typedesc_map == NULL) > + typedesc_map = pointer_map_create (); > + void **slot = pointer_map_contains (typedesc_map, type); > + return slot ? (tree) *slot : NULL_TREE; > } > > -/* Helper routine, which encodes a value in the uptr type. > +/* Helper routine, which encodes a value in the pointer_sized_int_node. > Arguments with precision <= POINTER_SIZE are passed directly, > the rest is passed by reference. T is a value we are to encode. */ > > @@ -281,24 +214,19 @@ get_ubsan_type_info_for_type (tree type) > } > > /* Helper routine that returns ADDR_EXPR of a VAR_DECL of a type > - descriptor. It first looks into the hash table; if not found, > - create the VAR_DECL, put it into the hash table and return the > + descriptor. It first looks into the pointer map; if not found, > + create the VAR_DECL, put it into the pointer map and return the > ADDR_EXPR of it. TYPE describes a particular type. */ > > tree > ubsan_type_descriptor (tree type) > { > - hash_table <ubsan_typedesc_hasher> ht = get_typedesc_hash_table (); > - ubsan_typedesc d; > - > /* See through any typedefs. */ > type = TYPE_MAIN_VARIANT (type); > > - ubsan_typedesc_init (&d, type, NULL); > - ubsan_typedesc **slot = ht.find_slot (&d, INSERT); > - if (*slot != NULL) > - /* We have the VAR_DECL in the table. Return it. */ > - return (*slot)->decl; > + tree decl = lookup_decl_for_type (type); > + if (decl != NULL_TREE) > + return decl; > > tree dtype = ubsan_type_descriptor_type (); > const char *tname; > @@ -326,7 +254,7 @@ ubsan_type_descriptor (tree type) > char tmp_name[32]; > static unsigned int type_var_id_num; > ASM_GENERATE_INTERNAL_LABEL (tmp_name, "Lubsan_type", type_var_id_num++); > - tree decl = build_decl (UNKNOWN_LOCATION, VAR_DECL, get_identifier (tmp_name), > + decl = build_decl (UNKNOWN_LOCATION, VAR_DECL, get_identifier (tmp_name), > dtype); > TREE_STATIC (decl) = 1; > TREE_PUBLIC (decl) = 0; > @@ -350,9 +278,9 @@ ubsan_type_descriptor (tree type) > DECL_INITIAL (decl) = ctor; > rest_of_decl_compilation (decl, 1, 0); > > - /* Save the address of the VAR_DECL into the hash table. */ > + /* Save the address of the VAR_DECL into the pointer map. */ > decl = build_fold_addr_expr (decl); > - *slot = ubsan_typedesc_new (type, decl); > + insert_decl_for_type (decl, type); > > return decl; > } > > Marek
--- gcc/ubsan.c.mp 2013-08-27 12:31:04.136213922 +0200 +++ gcc/ubsan.c 2013-08-27 12:31:10.361236456 +0200 @@ -22,109 +22,42 @@ along with GCC; see the file COPYING3. #include "system.h" #include "coretypes.h" #include "tree.h" -#include "alloc-pool.h" #include "cgraph.h" #include "gimple.h" -#include "hash-table.h" +#include "pointer-set.h" #include "output.h" #include "toplev.h" #include "ubsan.h" #include "c-family/c-common.h" -/* This type represents an entry in the hash table; this hash table - maps from a TYPE to a ubsan type descriptor VAR_DECL for that type. */ -struct ubsan_typedesc -{ - /* This represents the type of a variable. */ - tree type; - - /* This is the VAR_DECL of the type. */ - tree decl; -}; - -static alloc_pool ubsan_typedesc_alloc_pool; - -/* Hash table for type descriptors. */ -struct ubsan_typedesc_hasher - : typed_noop_remove <ubsan_typedesc> -{ - typedef ubsan_typedesc value_type; - typedef ubsan_typedesc compare_type; - - static inline hashval_t hash (const value_type *); - static inline bool equal (const value_type *, const compare_type *); -}; - -/* Hash a memory reference. */ - -inline hashval_t -ubsan_typedesc_hasher::hash (const ubsan_typedesc *data) -{ - return iterative_hash_object (TYPE_UID (data->type), 0); -} - -/* Compare two data types. */ - -inline bool -ubsan_typedesc_hasher::equal (const ubsan_typedesc *d1, - const ubsan_typedesc *d2) -{ - /* Here, the types should have identical __typekind, - __typeinfo and __typename. */ - return d1->type == d2->type; -} - -static hash_table <ubsan_typedesc_hasher> ubsan_typedesc_ht; +/* Map a TYPE to an ubsan type descriptor VAR_DECL for that type. */ +static pointer_map_t *typedesc_map; -/* Initializes an instance of ubsan_typedesc. */ +/* Insert DECL as the VAR_DECL for TYPE in the TYPEDESC_MAP. */ static void -ubsan_typedesc_init (ubsan_typedesc *data, tree type, tree decl) +insert_decl_for_type (tree decl, tree type) { - data->type = type; - data->decl = decl; + void **slot = pointer_map_insert (typedesc_map, type); + gcc_assert (*slot == NULL); + *slot = decl; } -/* This creates the alloc pool used to store the instances of - ubsan_typedesc that are stored in the hash table ubsan_typedesc_ht. */ +/* Find the VAR_DECL for TYPE in TYPEDESC_MAP. If TYPE does not + exist in the map, return NULL_TREE, otherwise, return the VAR_DECL + we found. */ -static alloc_pool -ubsan_typedesc_get_alloc_pool () -{ - if (ubsan_typedesc_alloc_pool == NULL) - ubsan_typedesc_alloc_pool = create_alloc_pool ("ubsan_typedesc", - sizeof (ubsan_typedesc), - 10); - return ubsan_typedesc_alloc_pool; -} - -/* Returns a reference to the hash table containing data type. - This function ensures that the hash table is created. */ - -static hash_table <ubsan_typedesc_hasher> & -get_typedesc_hash_table () -{ - if (!ubsan_typedesc_ht.is_created ()) - ubsan_typedesc_ht.create (10); - - return ubsan_typedesc_ht; -} - -/* Allocates memory for an instance of ubsan_typedesc into the memory - pool returned by ubsan_typedesc_get_alloc_pool and initialize it. - TYPE describes a particular type, DECL is its VAR_DECL. */ - -static ubsan_typedesc * -ubsan_typedesc_new (tree type, tree decl) +static tree +lookup_decl_for_type (tree type) { - ubsan_typedesc *desc = - (ubsan_typedesc *) pool_alloc (ubsan_typedesc_get_alloc_pool ()); - - ubsan_typedesc_init (desc, type, decl); - return desc; + /* If the pointer map is not initialized yet, create it now. */ + if (typedesc_map == NULL) + typedesc_map = pointer_map_create (); + void **slot = pointer_map_contains (typedesc_map, type); + return slot ? (tree) *slot : NULL_TREE; } -/* Helper routine, which encodes a value in the uptr type. +/* Helper routine, which encodes a value in the pointer_sized_int_node. Arguments with precision <= POINTER_SIZE are passed directly, the rest is passed by reference. T is a value we are to encode. */ @@ -281,24 +214,19 @@ get_ubsan_type_info_for_type (tree type) } /* Helper routine that returns ADDR_EXPR of a VAR_DECL of a type - descriptor. It first looks into the hash table; if not found, - create the VAR_DECL, put it into the hash table and return the + descriptor. It first looks into the pointer map; if not found, + create the VAR_DECL, put it into the pointer map and return the ADDR_EXPR of it. TYPE describes a particular type. */ tree ubsan_type_descriptor (tree type) { - hash_table <ubsan_typedesc_hasher> ht = get_typedesc_hash_table (); - ubsan_typedesc d; - /* See through any typedefs. */ type = TYPE_MAIN_VARIANT (type); - ubsan_typedesc_init (&d, type, NULL); - ubsan_typedesc **slot = ht.find_slot (&d, INSERT); - if (*slot != NULL) - /* We have the VAR_DECL in the table. Return it. */ - return (*slot)->decl; + tree decl = lookup_decl_for_type (type); + if (decl != NULL_TREE) + return decl; tree dtype = ubsan_type_descriptor_type (); const char *tname; @@ -326,7 +254,7 @@ ubsan_type_descriptor (tree type) char tmp_name[32]; static unsigned int type_var_id_num; ASM_GENERATE_INTERNAL_LABEL (tmp_name, "Lubsan_type", type_var_id_num++); - tree decl = build_decl (UNKNOWN_LOCATION, VAR_DECL, get_identifier (tmp_name), + decl = build_decl (UNKNOWN_LOCATION, VAR_DECL, get_identifier (tmp_name), dtype); TREE_STATIC (decl) = 1; TREE_PUBLIC (decl) = 0; @@ -350,9 +278,9 @@ ubsan_type_descriptor (tree type) DECL_INITIAL (decl) = ctor; rest_of_decl_compilation (decl, 1, 0); - /* Save the address of the VAR_DECL into the hash table. */ + /* Save the address of the VAR_DECL into the pointer map. */ decl = build_fold_addr_expr (decl); - *slot = ubsan_typedesc_new (type, decl); + insert_decl_for_type (decl, type); return decl; }