[ubsan] Use pointer map instead of hash table.

[ubsan] Use pointer map instead of hash table.

[Marek Polacek]

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.

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

Re: [ubsan] Use pointer map instead of hash table.

[Richard Biener]

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

Re: [ubsan] Use pointer map instead of hash table.

[Marek Polacek]

On Wed, Aug 28, 2013 at 12:40:50PM +0200, Richard Biener wrote:
> 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).

Thanks, done with the following.  Please let me know if you see
something wrong in this; otherwise I'll commit it if the
bootstrap-ubsan passes.

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

	* ubsan.c: Use pointer_map<tree> instead of pointer_map_t.
	(insert_decl_for_type): Adjust.
	(lookup_decl_for_type): Likewise.

--- gcc/ubsan.c.mp	2013-08-28 12:54:17.778383224 +0200
+++ gcc/ubsan.c	2013-08-28 14:09:42.400105470 +0200
@@ -31,16 +31,14 @@ along with GCC; see the file COPYING3.
 #include "c-family/c-common.h"
 
 /* Map a TYPE to an ubsan type descriptor VAR_DECL for that type.  */
-static pointer_map_t *typedesc_map;
+static pointer_map<tree> *typedesc_map;
 
 /* Insert DECL as the VAR_DECL for TYPE in the TYPEDESC_MAP.  */
 
 static void
 insert_decl_for_type (tree decl, tree type)
 {
-  void **slot = pointer_map_insert (typedesc_map, type);
-  gcc_assert (*slot == NULL);
-  *slot = decl;
+  *typedesc_map->insert (type) = decl;
 }
 
 /* Find the VAR_DECL for TYPE in TYPEDESC_MAP.  If TYPE does not
@@ -52,9 +50,13 @@ lookup_decl_for_type (tree type)
 {
   /* 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;
+    {
+      typedesc_map = new pointer_map<tree>;
+      /* That also means we don't have to bother with the lookup.  */
+      return NULL_TREE;
+    }
+  tree *t = typedesc_map->contains (type);
+  return t ? *t : NULL_TREE;
 }
 
 /* Helper routine, which encodes a value in the pointer_sized_int_node.

	Marek

Re: [ubsan] Use pointer map instead of hash table.

[Richard Biener]

On Wed, Aug 28, 2013 at 2:15 PM, Marek Polacek <polacek@redhat.com> wrote:
> On Wed, Aug 28, 2013 at 12:40:50PM +0200, Richard Biener wrote:
>> 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).
>
> Thanks, done with the following.  Please let me know if you see
> something wrong in this; otherwise I'll commit it if the
> bootstrap-ubsan passes.

Probably misses freeing of the pointer-map using 'delete' somewhere.

Richard.

> 2013-08-28  Marek Polacek  <polacek@redhat.com>
>
>         * ubsan.c: Use pointer_map<tree> instead of pointer_map_t.
>         (insert_decl_for_type): Adjust.
>         (lookup_decl_for_type): Likewise.
>
> --- gcc/ubsan.c.mp      2013-08-28 12:54:17.778383224 +0200
> +++ gcc/ubsan.c 2013-08-28 14:09:42.400105470 +0200
> @@ -31,16 +31,14 @@ along with GCC; see the file COPYING3.
>  #include "c-family/c-common.h"
>
>  /* Map a TYPE to an ubsan type descriptor VAR_DECL for that type.  */
> -static pointer_map_t *typedesc_map;
> +static pointer_map<tree> *typedesc_map;
>
>  /* Insert DECL as the VAR_DECL for TYPE in the TYPEDESC_MAP.  */
>
>  static void
>  insert_decl_for_type (tree decl, tree type)
>  {
> -  void **slot = pointer_map_insert (typedesc_map, type);
> -  gcc_assert (*slot == NULL);
> -  *slot = decl;
> +  *typedesc_map->insert (type) = decl;
>  }
>
>  /* Find the VAR_DECL for TYPE in TYPEDESC_MAP.  If TYPE does not
> @@ -52,9 +50,13 @@ lookup_decl_for_type (tree type)
>  {
>    /* 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;
> +    {
> +      typedesc_map = new pointer_map<tree>;
> +      /* That also means we don't have to bother with the lookup.  */
> +      return NULL_TREE;
> +    }
> +  tree *t = typedesc_map->contains (type);
> +  return t ? *t : NULL_TREE;
>  }
>
>  /* Helper routine, which encodes a value in the pointer_sized_int_node.
>
>         Marek

Re: [ubsan] Use pointer map instead of hash table.

[Marek Polacek]

On Wed, Aug 28, 2013 at 02:49:54PM +0200, Richard Biener wrote:
> On Wed, Aug 28, 2013 at 2:15 PM, Marek Polacek <polacek@redhat.com> wrote:
> > On Wed, Aug 28, 2013 at 12:40:50PM +0200, Richard Biener wrote:
> >> 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).
> >
> > Thanks, done with the following.  Please let me know if you see
> > something wrong in this; otherwise I'll commit it if the
> > bootstrap-ubsan passes.
> 
> Probably misses freeing of the pointer-map using 'delete' somewhere.

That's a problem, since ubsan is not a pass, we can't simply delete
the map at the end of the pass when it's not needed anymore...

Perhaps some GTY(()) stuff could do it, but I don't know which one.

	Marek

Re: [ubsan] Use pointer map instead of hash table.

[Jakub Jelinek]

On Wed, Aug 28, 2013 at 02:57:01PM +0200, Marek Polacek wrote:
> On Wed, Aug 28, 2013 at 02:49:54PM +0200, Richard Biener wrote:
> > On Wed, Aug 28, 2013 at 2:15 PM, Marek Polacek <polacek@redhat.com> wrote:
> > > On Wed, Aug 28, 2013 at 12:40:50PM +0200, Richard Biener wrote:
> > >> 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).
> > >
> > > Thanks, done with the following.  Please let me know if you see
> > > something wrong in this; otherwise I'll commit it if the
> > > bootstrap-ubsan passes.
> > 
> > Probably misses freeing of the pointer-map using 'delete' somewhere.
> 
> That's a problem, since ubsan is not a pass, we can't simply delete
> the map at the end of the pass when it's not needed anymore...
> 
> Perhaps some GTY(()) stuff could do it, but I don't know which one.

You basically want to keep the pointer map for as long as you can
lookup types, which is done now from both FEs and
middle-end?  I guess it is the same category as say
debug_expr_for_decl or value_expr_for_decl map tables, which we never free
either.  But for those we indeed
GTY ((if_marked ("tree_decl_map_marked_p"), param_is (struct tree_decl_map)))
and thus remove items if the original decl is not referenced from anywhere
else; but pointer_map doesn't allow item removal; do we walk it for GC at
all?  If so, it might prevent some types from being GC collected, on the
other side right now it isn't expected that too many types will be put into
the map.

	Jakub

Re: [ubsan] Use pointer map instead of hash table.

[Richard Biener]

On Wed, Aug 28, 2013 at 3:05 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> On Wed, Aug 28, 2013 at 02:57:01PM +0200, Marek Polacek wrote:
>> On Wed, Aug 28, 2013 at 02:49:54PM +0200, Richard Biener wrote:
>> > On Wed, Aug 28, 2013 at 2:15 PM, Marek Polacek <polacek@redhat.com> wrote:
>> > > On Wed, Aug 28, 2013 at 12:40:50PM +0200, Richard Biener wrote:
>> > >> 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).
>> > >
>> > > Thanks, done with the following.  Please let me know if you see
>> > > something wrong in this; otherwise I'll commit it if the
>> > > bootstrap-ubsan passes.
>> >
>> > Probably misses freeing of the pointer-map using 'delete' somewhere.
>>
>> That's a problem, since ubsan is not a pass, we can't simply delete
>> the map at the end of the pass when it's not needed anymore...
>>
>> Perhaps some GTY(()) stuff could do it, but I don't know which one.
>
> You basically want to keep the pointer map for as long as you can
> lookup types, which is done now from both FEs and
> middle-end?  I guess it is the same category as say
> debug_expr_for_decl or value_expr_for_decl map tables, which we never free
> either.  But for those we indeed
> GTY ((if_marked ("tree_decl_map_marked_p"), param_is (struct tree_decl_map)))
> and thus remove items if the original decl is not referenced from anywhere
> else; but pointer_map doesn't allow item removal; do we walk it for GC at
> all?  If so, it might prevent some types from being GC collected, on the
> other side right now it isn't expected that too many types will be put into
> the map.

pointer-map is not GC enabled.

Richard.

>         Jakub

Re: [ubsan] Use pointer map instead of hash table.

[Marek Polacek]

On Wed, Aug 28, 2013 at 03:05:37PM +0200, Jakub Jelinek wrote:
> On Wed, Aug 28, 2013 at 02:57:01PM +0200, Marek Polacek wrote:
> > On Wed, Aug 28, 2013 at 02:49:54PM +0200, Richard Biener wrote:
> > > On Wed, Aug 28, 2013 at 2:15 PM, Marek Polacek <polacek@redhat.com> wrote:
> > > > On Wed, Aug 28, 2013 at 12:40:50PM +0200, Richard Biener wrote:
> > > >> 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).
> > > >
> > > > Thanks, done with the following.  Please let me know if you see
> > > > something wrong in this; otherwise I'll commit it if the
> > > > bootstrap-ubsan passes.
> > > 
> > > Probably misses freeing of the pointer-map using 'delete' somewhere.
> > 
> > That's a problem, since ubsan is not a pass, we can't simply delete
> > the map at the end of the pass when it's not needed anymore...
> > 
> > Perhaps some GTY(()) stuff could do it, but I don't know which one.
> 
> You basically want to keep the pointer map for as long as you can
> lookup types, which is done now from both FEs and
> middle-end?  

Yes, I think so.

> I guess it is the same category as say
> debug_expr_for_decl or value_expr_for_decl map tables, which we never free
> either.  But for those we indeed
> GTY ((if_marked ("tree_decl_map_marked_p"), param_is (struct tree_decl_map)))
> and thus remove items if the original decl is not referenced from anywhere
> else; but pointer_map doesn't allow item removal; do we walk it for GC at
> all?

From a quick look, it doesn't seem like we do.  (I was searching for
something about pointer_map in ggc* and gen* files.)

> If so, it might prevent some types from being GC collected, on the
> other side right now it isn't expected that too many types will be put into
> the map.

That's right.  I expect that typically there will be no more than,
say, 10 types in the map.

	Marek

Re: [ubsan] Use pointer map instead of hash table.

[Jakub Jelinek]

On Wed, Aug 28, 2013 at 03:30:46PM +0200, Marek Polacek wrote:
> >From a quick look, it doesn't seem like we do.  (I was searching for
> something about pointer_map in ggc* and gen* files.)

If we can't make it GC aware easily, I'm afraid we need to revert that change to
pointer_map.  Now, the question is if the if_marked stuff can be easily done
for the previous implementation with C++ish hash table, or if we should just
use something similar to what tree.c uses for value_expr_for_decl and
similar (of course, with minor adjustments, because we want to map from
TYPE_UID rather than DECL_UID of the key to tree).  Or with pointer_map we'd
need to push both the keys (types) and what they map to into (decls) into
some GC vector in addition to the pointer_map.

	Jakub

Re: [ubsan] Use pointer map instead of hash table.

[Marek Polacek]

On Wed, Aug 28, 2013 at 03:37:31PM +0200, Jakub Jelinek wrote:
> On Wed, Aug 28, 2013 at 03:30:46PM +0200, Marek Polacek wrote:
> > >From a quick look, it doesn't seem like we do.  (I was searching for
> > something about pointer_map in ggc* and gen* files.)
> 
> If we can't make it GC aware easily, I'm afraid we need to revert that change to
> pointer_map.  Now, the question is if the if_marked stuff can be easily done
> for the previous implementation with C++ish hash table, or if we should just
> use something similar to what tree.c uses for value_expr_for_decl and
> similar (of course, with minor adjustments, because we want to map from
> TYPE_UID rather than DECL_UID of the key to tree).  Or with pointer_map we'd
> need to push both the keys (types) and what they map to into (decls) into
> some GC vector in addition to the pointer_map.

This is an attempt to convert the pointer_map into C style hash map;
it mimics value_expr_for_decl stuff in tree.[ch].  I've built a bunch of
build_distinct_type_copy's that are in fact unused and in the final assembly
I see only the really used ones, so hopefully it works ;).

Tested x86_64-linux, ran bootstrap-ubsan and stage2/3 comparison looks
ok.  Though, I'd appreciate if either of you could take a peek at it
before I commit it.  Thanks,

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

	* Makefile.in (ubsan.o): Add HASH_TABLE_H and gt-ubsan.h
	dependencies.  Remove pointer-set.h dependency.
	* ubsan.c: Convert to C style hash table.

--- gcc/Makefile.in.mp	2013-08-29 14:24:49.839578625 +0200
+++ gcc/Makefile.in	2013-08-29 14:54:39.354258737 +0200
@@ -2273,7 +2273,7 @@ tsan.o : $(CONFIG_H) $(SYSTEM_H) $(TREE_
    intl.h cfghooks.h output.h options.h $(C_COMMON_H) tsan.h asan.h \
    tree-ssa-propagate.h
 ubsan.o : ubsan.c ubsan.h $(CONFIG_H) $(SYSTEM_H) $(GIMPLE_H) \
-   output.h coretypes.h $(TREE_H) $(CGRAPH_H) pointer-set.h \
+   output.h coretypes.h $(TREE_H) $(CGRAPH_H) $(HASH_TABLE_H) gt-ubsan.h \
    toplev.h $(C_COMMON_H)
 tree-ssa-tail-merge.o: tree-ssa-tail-merge.c \
    $(SYSTEM_H) $(CONFIG_H) coretypes.h $(TM_H) $(BITMAP_H) \
--- gcc/ubsan.c.mp	2013-08-29 14:24:49.840578629 +0200
+++ gcc/ubsan.c	2013-08-29 14:24:54.848597440 +0200
@@ -24,39 +24,71 @@ along with GCC; see the file COPYING3.
 #include "tree.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"
 
-/* Map a TYPE to an ubsan type descriptor VAR_DECL for that type.  */
-static pointer_map<tree> *typedesc_map;
+/* Map from a tree to a VAR_DECL tree.  */
 
-/* Insert DECL as the VAR_DECL for TYPE in the TYPEDESC_MAP.  */
+struct GTY(()) tree_type_map {
+  struct tree_map_base type;
+  unsigned int hash;
+  tree decl;
+};
+
+#define tree_type_map_eq tree_map_base_eq
+#define tree_type_map_marked_p tree_map_base_marked_p
+
+static GTY ((if_marked ("tree_type_map_marked_p"), param_is (struct tree_type_map)))
+     htab_t decl_tree_for_type;
+
+/* Initialize the hash table.  */
 
 static void
-insert_decl_for_type (tree decl, tree type)
+init_hash_table (void)
 {
-  *typedesc_map->insert (type) = decl;
+  decl_tree_for_type = htab_create_ggc (512, tree_decl_map_hash,
+					tree_decl_map_eq, 0);
 }
 
-/* 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.  */
+/* Lookup a VAR_DECL for TYPE, and return it if we find one.  */
 
-static tree
-lookup_decl_for_type (tree type)
+tree
+decl_for_type_lookup (tree type)
 {
-  /* If the pointer map is not initialized yet, create it now.  */
-  if (typedesc_map == NULL)
+  /* If the hash table is not initialized yet, create it now.  */
+  if (decl_tree_for_type == NULL)
     {
-      typedesc_map = new pointer_map<tree>;
+      init_hash_table ();
       /* That also means we don't have to bother with the lookup.  */
       return NULL_TREE;
     }
-  tree *t = typedesc_map->contains (type);
-  return t ? *t : NULL_TREE;
+
+  struct tree_type_map *h, in;
+  in.type.from = type;
+
+  h = (struct tree_type_map *)
+      htab_find_with_hash (decl_tree_for_type, &in, TYPE_UID (type));
+  return h ? h->decl : NULL_TREE;
+}
+
+/* Insert a mapping TYPE->DECL in the VAR_DECL for type hashtable.  */
+
+void
+decl_for_type_insert (tree type, tree decl)
+{
+  struct tree_type_map *h;
+  void **slot;
+
+  h = ggc_alloc_tree_type_map ();
+  h->type.from = type;
+  h->decl = decl;
+  slot = htab_find_slot_with_hash (decl_tree_for_type, h, TYPE_UID (type),
+                                  INSERT);
+  *(struct tree_type_map **) slot = h;
 }
 
 /* Helper routine, which encodes a value in the pointer_sized_int_node.
@@ -226,7 +258,7 @@ ubsan_type_descriptor (tree type)
   /* See through any typedefs.  */
   type = TYPE_MAIN_VARIANT (type);
 
-  tree decl = lookup_decl_for_type (type);
+  tree decl = decl_for_type_lookup (type);
   if (decl != NULL_TREE)
     return decl;
 
@@ -282,7 +314,7 @@ ubsan_type_descriptor (tree type)
 
   /* Save the address of the VAR_DECL into the pointer map.  */
   decl = build_fold_addr_expr (decl);
-  insert_decl_for_type (decl, type);
+  decl_for_type_insert (type, decl);
 
   return decl;
 }
@@ -388,3 +420,5 @@ is_ubsan_builtin_p (tree t)
   return strncmp (IDENTIFIER_POINTER (DECL_NAME (t)),
 		  "__builtin___ubsan_", 18) == 0;
 }
+
+#include "gt-ubsan.h"

	Marek

Re: [ubsan] Use pointer map instead of hash table.

[Jakub Jelinek]

On Thu, Aug 29, 2013 at 02:56:58PM +0200, Marek Polacek wrote:
> --- gcc/Makefile.in.mp	2013-08-29 14:24:49.839578625 +0200
> +++ gcc/Makefile.in	2013-08-29 14:54:39.354258737 +0200
> @@ -2273,7 +2273,7 @@ tsan.o : $(CONFIG_H) $(SYSTEM_H) $(TREE_
>     intl.h cfghooks.h output.h options.h $(C_COMMON_H) tsan.h asan.h \
>     tree-ssa-propagate.h
>  ubsan.o : ubsan.c ubsan.h $(CONFIG_H) $(SYSTEM_H) $(GIMPLE_H) \
> -   output.h coretypes.h $(TREE_H) $(CGRAPH_H) pointer-set.h \
> +   output.h coretypes.h $(TREE_H) $(CGRAPH_H) $(HASH_TABLE_H) gt-ubsan.h \
>     toplev.h $(C_COMMON_H)
>  tree-ssa-tail-merge.o: tree-ssa-tail-merge.c \
>     $(SYSTEM_H) $(CONFIG_H) coretypes.h $(TM_H) $(BITMAP_H) \
> --- gcc/ubsan.c.mp	2013-08-29 14:24:49.840578629 +0200
> +++ gcc/ubsan.c	2013-08-29 14:24:54.848597440 +0200
> @@ -24,39 +24,71 @@ along with GCC; see the file COPYING3.
>  #include "tree.h"
>  #include "cgraph.h"
>  #include "gimple.h"
> +#include "hash-table.h"

Why not #include "hashtab.h" instead (and corresponding change in
Makefile.in ?

>  #include "pointer-set.h"
>  #include "output.h"
>  #include "toplev.h"
>  #include "ubsan.h"
>  #include "c-family/c-common.h"
>  
> -/* Map a TYPE to an ubsan type descriptor VAR_DECL for that type.  */
> -static pointer_map<tree> *typedesc_map;
> +/* Map from a tree to a VAR_DECL tree.  */
>  
> -/* Insert DECL as the VAR_DECL for TYPE in the TYPEDESC_MAP.  */
> +struct GTY(()) tree_type_map {
> +  struct tree_map_base type;
> +  unsigned int hash;

You use TYPE_UID as hash, and never use hash field, so why you are adding
it?

> +#define tree_type_map_eq tree_map_base_eq
> +#define tree_type_map_marked_p tree_map_base_marked_p
> +
> +static GTY ((if_marked ("tree_type_map_marked_p"), param_is (struct tree_type_map)))
> +     htab_t decl_tree_for_type;
> +
> +/* Initialize the hash table.  */
>  
>  static void
> -insert_decl_for_type (tree decl, tree type)
> +init_hash_table (void)
>  {
> -  *typedesc_map->insert (type) = decl;
> +  decl_tree_for_type = htab_create_ggc (512, tree_decl_map_hash,
> +					tree_decl_map_eq, 0);

tree_type_map_hash and tree_type_map_eq here, right?
You could also just manually inline init_hash_table into the single caller, after
all, it is just one statement.
512 might be too much, how many types we put there typically?  10, 20?

> -/* 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.  */
> +/* Lookup a VAR_DECL for TYPE, and return it if we find one.  */
>  
> -static tree
> -lookup_decl_for_type (tree type)
> +tree
> +decl_for_type_lookup (tree type)

Why are you dropping the static here?

> +/* Insert a mapping TYPE->DECL in the VAR_DECL for type hashtable.  */
> +
> +void
> +decl_for_type_insert (tree type, tree decl)

Again, can't this be static?

Otherwise looks good.

	Jakub

Re: [ubsan] Use pointer map instead of hash table.

[Marek Polacek]

On Thu, Aug 29, 2013 at 03:05:59PM +0200, Jakub Jelinek wrote:
> On Thu, Aug 29, 2013 at 02:56:58PM +0200, Marek Polacek wrote:
> > --- gcc/Makefile.in.mp	2013-08-29 14:24:49.839578625 +0200
> > +++ gcc/Makefile.in	2013-08-29 14:54:39.354258737 +0200
> > @@ -2273,7 +2273,7 @@ tsan.o : $(CONFIG_H) $(SYSTEM_H) $(TREE_
> >     intl.h cfghooks.h output.h options.h $(C_COMMON_H) tsan.h asan.h \
> >     tree-ssa-propagate.h
> >  ubsan.o : ubsan.c ubsan.h $(CONFIG_H) $(SYSTEM_H) $(GIMPLE_H) \
> > -   output.h coretypes.h $(TREE_H) $(CGRAPH_H) pointer-set.h \
> > +   output.h coretypes.h $(TREE_H) $(CGRAPH_H) $(HASH_TABLE_H) gt-ubsan.h \
> >     toplev.h $(C_COMMON_H)
> >  tree-ssa-tail-merge.o: tree-ssa-tail-merge.c \
> >     $(SYSTEM_H) $(CONFIG_H) coretypes.h $(TM_H) $(BITMAP_H) \
> > --- gcc/ubsan.c.mp	2013-08-29 14:24:49.840578629 +0200
> > +++ gcc/ubsan.c	2013-08-29 14:24:54.848597440 +0200
> > @@ -24,39 +24,71 @@ along with GCC; see the file COPYING3.
> >  #include "tree.h"
> >  #include "cgraph.h"
> >  #include "gimple.h"
> > +#include "hash-table.h"
> 
> Why not #include "hashtab.h" instead (and corresponding change in
> Makefile.in ?

Fixed.

> >  #include "pointer-set.h"
> >  #include "output.h"
> >  #include "toplev.h"
> >  #include "ubsan.h"
> >  #include "c-family/c-common.h"
> >  
> > -/* Map a TYPE to an ubsan type descriptor VAR_DECL for that type.  */
> > -static pointer_map<tree> *typedesc_map;
> > +/* Map from a tree to a VAR_DECL tree.  */
> >  
> > -/* Insert DECL as the VAR_DECL for TYPE in the TYPEDESC_MAP.  */
> > +struct GTY(()) tree_type_map {
> > +  struct tree_map_base type;
> > +  unsigned int hash;
> 
> You use TYPE_UID as hash, and never use hash field, so why you are adding
> it?

Removed the hash field.

> > +#define tree_type_map_eq tree_map_base_eq
> > +#define tree_type_map_marked_p tree_map_base_marked_p
> > +
> > +static GTY ((if_marked ("tree_type_map_marked_p"), param_is (struct tree_type_map)))
> > +     htab_t decl_tree_for_type;
> > +
> > +/* Initialize the hash table.  */
> >  
> >  static void
> > -insert_decl_for_type (tree decl, tree type)
> > +init_hash_table (void)
> >  {
> > -  *typedesc_map->insert (type) = decl;
> > +  decl_tree_for_type = htab_create_ggc (512, tree_decl_map_hash,
> > +					tree_decl_map_eq, 0);
> 
> tree_type_map_hash and tree_type_map_eq here, right?

Yeah.  Fixed.

> You could also just manually inline init_hash_table into the single caller, after
> all, it is just one statement.

Done.

> 512 might be too much, how many types we put there typically?  10, 20?

Of course, 10 should be enough.

> > -/* 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.  */
> > +/* Lookup a VAR_DECL for TYPE, and return it if we find one.  */
> >  
> > -static tree
> > -lookup_decl_for_type (tree type)
> > +tree
> > +decl_for_type_lookup (tree type)
> 
> Why are you dropping the static here?

:( No clue.  Fixed.

> > +/* Insert a mapping TYPE->DECL in the VAR_DECL for type hashtable.  */
> > +
> > +void
> > +decl_for_type_insert (tree type, tree decl)
> 
> Again, can't this be static?

Fixed.

> Otherwise looks good.

Thanks, will give it another bootstrap-ubsan round and if that's fine,
I'll commit the following.

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

	* Makefile.in (ubsan.o): Add HASHAB_H and gt-ubsan.h
	dependencies.  Remove pointer-set.h dependency.
	* ubsan.c: Convert to C style hash table.

--- gcc/Makefile.in.mp	2013-08-29 14:24:49.839578625 +0200
+++ gcc/Makefile.in	2013-08-29 15:13:16.538323950 +0200
@@ -2273,7 +2273,7 @@ tsan.o : $(CONFIG_H) $(SYSTEM_H) $(TREE_
    intl.h cfghooks.h output.h options.h $(C_COMMON_H) tsan.h asan.h \
    tree-ssa-propagate.h
 ubsan.o : ubsan.c ubsan.h $(CONFIG_H) $(SYSTEM_H) $(GIMPLE_H) \
-   output.h coretypes.h $(TREE_H) $(CGRAPH_H) pointer-set.h \
+   output.h coretypes.h $(TREE_H) $(CGRAPH_H) $(HASHTAB_H) gt-ubsan.h \
    toplev.h $(C_COMMON_H)
 tree-ssa-tail-merge.o: tree-ssa-tail-merge.c \
    $(SYSTEM_H) $(CONFIG_H) coretypes.h $(TM_H) $(BITMAP_H) \
--- gcc/ubsan.c.mp	2013-08-29 14:24:49.840578629 +0200
+++ gcc/ubsan.c	2013-08-29 15:22:42.368445186 +0200
@@ -24,39 +24,63 @@ along with GCC; see the file COPYING3.
 #include "tree.h"
 #include "cgraph.h"
 #include "gimple.h"
+#include "hashtab.h"
 #include "pointer-set.h"
 #include "output.h"
 #include "toplev.h"
 #include "ubsan.h"
 #include "c-family/c-common.h"
 
-/* Map a TYPE to an ubsan type descriptor VAR_DECL for that type.  */
-static pointer_map<tree> *typedesc_map;
+/* Map from a tree to a VAR_DECL tree.  */
 
-/* Insert DECL as the VAR_DECL for TYPE in the TYPEDESC_MAP.  */
+struct GTY(()) tree_type_map {
+  struct tree_map_base type;
+  tree decl;
+};
 
-static void
-insert_decl_for_type (tree decl, tree type)
-{
-  *typedesc_map->insert (type) = decl;
-}
+#define tree_type_map_eq tree_map_base_eq
+#define tree_type_map_hash tree_map_base_hash
+#define tree_type_map_marked_p tree_map_base_marked_p
+
+static GTY ((if_marked ("tree_type_map_marked_p"), param_is (struct tree_type_map)))
+     htab_t decl_tree_for_type;
 
-/* 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.  */
+/* Lookup a VAR_DECL for TYPE, and return it if we find one.  */
 
 static tree
-lookup_decl_for_type (tree type)
+decl_for_type_lookup (tree type)
 {
-  /* If the pointer map is not initialized yet, create it now.  */
-  if (typedesc_map == NULL)
+  /* If the hash table is not initialized yet, create it now.  */
+  if (decl_tree_for_type == NULL)
     {
-      typedesc_map = new pointer_map<tree>;
+      decl_tree_for_type = htab_create_ggc (10, tree_type_map_hash,
+					    tree_type_map_eq, 0);
       /* That also means we don't have to bother with the lookup.  */
       return NULL_TREE;
     }
-  tree *t = typedesc_map->contains (type);
-  return t ? *t : NULL_TREE;
+
+  struct tree_type_map *h, in;
+  in.type.from = type;
+
+  h = (struct tree_type_map *)
+      htab_find_with_hash (decl_tree_for_type, &in, TYPE_UID (type));
+  return h ? h->decl : NULL_TREE;
+}
+
+/* Insert a mapping TYPE->DECL in the VAR_DECL for type hashtable.  */
+
+static void
+decl_for_type_insert (tree type, tree decl)
+{
+  struct tree_type_map *h;
+  void **slot;
+
+  h = ggc_alloc_tree_type_map ();
+  h->type.from = type;
+  h->decl = decl;
+  slot = htab_find_slot_with_hash (decl_tree_for_type, h, TYPE_UID (type),
+                                  INSERT);
+  *(struct tree_type_map **) slot = h;
 }
 
 /* Helper routine, which encodes a value in the pointer_sized_int_node.
@@ -226,7 +250,7 @@ ubsan_type_descriptor (tree type)
   /* See through any typedefs.  */
   type = TYPE_MAIN_VARIANT (type);
 
-  tree decl = lookup_decl_for_type (type);
+  tree decl = decl_for_type_lookup (type);
   if (decl != NULL_TREE)
     return decl;
 
@@ -282,7 +306,7 @@ ubsan_type_descriptor (tree type)
 
   /* Save the address of the VAR_DECL into the pointer map.  */
   decl = build_fold_addr_expr (decl);
-  insert_decl_for_type (decl, type);
+  decl_for_type_insert (type, decl);
 
   return decl;
 }
@@ -388,3 +412,5 @@ is_ubsan_builtin_p (tree t)
   return strncmp (IDENTIFIER_POINTER (DECL_NAME (t)),
 		  "__builtin___ubsan_", 18) == 0;
 }
+
+#include "gt-ubsan.h"

	Marek