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

login
register
mail settings
Submitter Marek Polacek
Date Aug. 28, 2013, 12:15 p.m.
Message ID <20130828121543.GD574@redhat.com>
Download mbox | patch
Permalink /patch/270486/
State New
Headers show

Comments

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


	Marek
Richard Guenther - Aug. 28, 2013, 12:49 p.m.
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
Marek Polacek - Aug. 28, 2013, 12:57 p.m.
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
Jakub Jelinek - Aug. 28, 2013, 1:05 p.m.
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
Richard Guenther - Aug. 28, 2013, 1:28 p.m.
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
Marek Polacek - Aug. 28, 2013, 1:30 p.m.
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
Jakub Jelinek - Aug. 28, 2013, 1:37 p.m.
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

Patch

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