Patchwork [ubsan] Use pointer map instead of hash table.

login
register
mail settings
Submitter Marek Polacek
Date Aug. 27, 2013, 12:33 p.m.
Message ID <20130827123338.GA574@redhat.com>
Download mbox | patch
Permalink /patch/270099/
State New
Headers show

Comments

Marek Polacek - Aug. 27, 2013, 12:33 p.m.
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.

2013-08-27  Marek Polacek  <polacek@redhat.com>

	* ubsan.c: Use pointer map instead of hash table.


	Marek
Richard Guenther - Aug. 28, 2013, 10:40 a.m.
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

Patch

--- 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;
 }