[stage,1] Fix bitmap registration of overheads.

Hi.

I've rewritten bitmap memory statistics which abused unsigned
type via register_overhead (map, -((int)sizeof (bitmap_head))).
I come up with a concept that each bitmap has assigned a unique ID
which is used for stats tracking. It's caused by fact that e.g. DF is
heavily reallocating bitmaps that then have a different address.

Survives bootstrap with --enable-gather-detailed-mem-stats.

Ready for next stage1?
Thanks,
Martin

gcc/ChangeLog:

2019-02-26  Martin Liska  <mliska@suse.cz>

	* bitmap.c (bitmap_register): Come up with
	alloc_descriptor_max_uid and assign it for
	a new bitmap.
	(register_overhead): Use get_descriptor as
	a descriptor.
	(release_overhead): New.
	(bitmap_elem_to_freelist): Call it.
	(bitmap_elt_clear_from): Likewise.
	(bitmap_obstack_free): Likewise.
	(bitmap_move): Sensitively release memory.
	* bitmap.h (struct GTY): Add alloc_descriptor.
	(bitmap_initialize): Initialize alloc_descriptor to zero.
	* tree-ssa-pre.c (do_hoist_insertion): Use bitmap_move.
---
 gcc/bitmap.c       | 39 ++++++++++++++++++++++++++++-----------
 gcc/bitmap.h       | 17 ++++++++++++++---
 gcc/tree-ssa-pre.c |  2 +-
 3 files changed, 43 insertions(+), 15 deletions(-)

On Tue, Feb 26, 2019 at 3:30 PM Martin Liška <mliska@suse.cz> wrote:
>
> Hi.
>
> I've rewritten bitmap memory statistics which abused unsigned
> type via register_overhead (map, -((int)sizeof (bitmap_head))).
> I come up with a concept that each bitmap has assigned a unique ID
> which is used for stats tracking. It's caused by fact that e.g. DF is
> heavily reallocating bitmaps that then have a different address.
>
> Survives bootstrap with --enable-gather-detailed-mem-stats.
>
> Ready for next stage1?

+  /* Get bitmap descriptor UID casted to an unsigned integer pointer.  */
+  unsigned *get_descriptor ()
+  {
+    return (unsigned *)(ptrdiff_t)alloc_descriptor;
+  }

this one is a bit ugly and together with

template <typename Type>
inline hashval_t
pointer_hash <Type>::hash (const value_type &candidate)
{
  /* This is a really poor hash function, but it is what the current code uses,
     so I am reusing it to avoid an additional axis in testing.  */
  return (hashval_t) ((intptr_t)candidate >> 3);

will give quite some hash collisions.  So I guess you should shift
the descriptor << 3 at least (and then make it at most 29 bits in
size?).  Not sure what to do about the descriptor wrapping btw.

Richard.

> Thanks,
> Martin
>
> gcc/ChangeLog:
>
> 2019-02-26  Martin Liska  <mliska@suse.cz>
>
>         * bitmap.c (bitmap_register): Come up with
>         alloc_descriptor_max_uid and assign it for
>         a new bitmap.
>         (register_overhead): Use get_descriptor as
>         a descriptor.
>         (release_overhead): New.
>         (bitmap_elem_to_freelist): Call it.
>         (bitmap_elt_clear_from): Likewise.
>         (bitmap_obstack_free): Likewise.
>         (bitmap_move): Sensitively release memory.
>         * bitmap.h (struct GTY): Add alloc_descriptor.
>         (bitmap_initialize): Initialize alloc_descriptor to zero.
>         * tree-ssa-pre.c (do_hoist_insertion): Use bitmap_move.
> ---
>  gcc/bitmap.c       | 39 ++++++++++++++++++++++++++++-----------
>  gcc/bitmap.h       | 17 ++++++++++++++---
>  gcc/tree-ssa-pre.c |  2 +-
>  3 files changed, 43 insertions(+), 15 deletions(-)
>
>

On 2/26/19 4:02 PM, Richard Biener wrote:
> On Tue, Feb 26, 2019 at 3:30 PM Martin Liška <mliska@suse.cz> wrote:
>>
>> Hi.
>>
>> I've rewritten bitmap memory statistics which abused unsigned
>> type via register_overhead (map, -((int)sizeof (bitmap_head))).
>> I come up with a concept that each bitmap has assigned a unique ID
>> which is used for stats tracking. It's caused by fact that e.g. DF is
>> heavily reallocating bitmaps that then have a different address.
>>
>> Survives bootstrap with --enable-gather-detailed-mem-stats.
>>
>> Ready for next stage1?
> 
> +  /* Get bitmap descriptor UID casted to an unsigned integer pointer.  */
> +  unsigned *get_descriptor ()
> +  {
> +    return (unsigned *)(ptrdiff_t)alloc_descriptor;
> +  }
> 
> this one is a bit ugly and together with

I know it's not perfect.

> 
> template <typename Type>
> inline hashval_t
> pointer_hash <Type>::hash (const value_type &candidate)
> {
>   /* This is a really poor hash function, but it is what the current code uses,
>      so I am reusing it to avoid an additional axis in testing.  */
>   return (hashval_t) ((intptr_t)candidate >> 3);
> 
> will give quite some hash collisions.  So I guess you should shift
> the descriptor << 3 at least (and then make it at most 29 bits in
> size?).

That's easily doable.

> Not sure what to do about the descriptor wrapping btw.

Question is whether we want to invest in our internal scaffolding more time?
Or can we live with the ugly casting?

Martin

> 
> Richard.
> 
>> Thanks,
>> Martin
>>
>> gcc/ChangeLog:
>>
>> 2019-02-26  Martin Liska  <mliska@suse.cz>
>>
>>         * bitmap.c (bitmap_register): Come up with
>>         alloc_descriptor_max_uid and assign it for
>>         a new bitmap.
>>         (register_overhead): Use get_descriptor as
>>         a descriptor.
>>         (release_overhead): New.
>>         (bitmap_elem_to_freelist): Call it.
>>         (bitmap_elt_clear_from): Likewise.
>>         (bitmap_obstack_free): Likewise.
>>         (bitmap_move): Sensitively release memory.
>>         * bitmap.h (struct GTY): Add alloc_descriptor.
>>         (bitmap_initialize): Initialize alloc_descriptor to zero.
>>         * tree-ssa-pre.c (do_hoist_insertion): Use bitmap_move.
>> ---
>>  gcc/bitmap.c       | 39 ++++++++++++++++++++++++++++-----------
>>  gcc/bitmap.h       | 17 ++++++++++++++---
>>  gcc/tree-ssa-pre.c |  2 +-
>>  3 files changed, 43 insertions(+), 15 deletions(-)
>>
>>

On February 26, 2019 6:50:13 PM GMT+01:00, "Martin Liška" <mliska@suse.cz> wrote:
>On 2/26/19 4:02 PM, Richard Biener wrote:
>> On Tue, Feb 26, 2019 at 3:30 PM Martin Liška <mliska@suse.cz> wrote:
>>>
>>> Hi.
>>>
>>> I've rewritten bitmap memory statistics which abused unsigned
>>> type via register_overhead (map, -((int)sizeof (bitmap_head))).
>>> I come up with a concept that each bitmap has assigned a unique ID
>>> which is used for stats tracking. It's caused by fact that e.g. DF
>is
>>> heavily reallocating bitmaps that then have a different address.
>>>
>>> Survives bootstrap with --enable-gather-detailed-mem-stats.
>>>
>>> Ready for next stage1?
>> 
>> +  /* Get bitmap descriptor UID casted to an unsigned integer
>pointer.  */
>> +  unsigned *get_descriptor ()
>> +  {
>> +    return (unsigned *)(ptrdiff_t)alloc_descriptor;
>> +  }
>> 
>> this one is a bit ugly and together with
>
>I know it's not perfect.
>
>> 
>> template <typename Type>
>> inline hashval_t
>> pointer_hash <Type>::hash (const value_type &candidate)
>> {
>>   /* This is a really poor hash function, but it is what the current
>code uses,
>>      so I am reusing it to avoid an additional axis in testing.  */
>>   return (hashval_t) ((intptr_t)candidate >> 3);
>> 
>> will give quite some hash collisions.  So I guess you should shift
>> the descriptor << 3 at least (and then make it at most 29 bits in
>> size?).
>
>That's easily doable.
>
>> Not sure what to do about the descriptor wrapping btw.
>
>Question is whether we want to invest in our internal scaffolding more
>time?
>Or can we live with the ugly casting?

I guess we can live with it if we can avoid the hash collisions. 

Richard. 

>Martin
>
>> 
>> Richard.
>> 
>>> Thanks,
>>> Martin
>>>
>>> gcc/ChangeLog:
>>>
>>> 2019-02-26  Martin Liska  <mliska@suse.cz>
>>>
>>>         * bitmap.c (bitmap_register): Come up with
>>>         alloc_descriptor_max_uid and assign it for
>>>         a new bitmap.
>>>         (register_overhead): Use get_descriptor as
>>>         a descriptor.
>>>         (release_overhead): New.
>>>         (bitmap_elem_to_freelist): Call it.
>>>         (bitmap_elt_clear_from): Likewise.
>>>         (bitmap_obstack_free): Likewise.
>>>         (bitmap_move): Sensitively release memory.
>>>         * bitmap.h (struct GTY): Add alloc_descriptor.
>>>         (bitmap_initialize): Initialize alloc_descriptor to zero.
>>>         * tree-ssa-pre.c (do_hoist_insertion): Use bitmap_move.
>>> ---
>>>  gcc/bitmap.c       | 39 ++++++++++++++++++++++++++++-----------
>>>  gcc/bitmap.h       | 17 ++++++++++++++---
>>>  gcc/tree-ssa-pre.c |  2 +-
>>>  3 files changed, 43 insertions(+), 15 deletions(-)
>>>
>>>

On 2/26/19 7:48 PM, Richard Biener wrote:
> On February 26, 2019 6:50:13 PM GMT+01:00, "Martin Liška" <mliska@suse.cz> wrote:
>> On 2/26/19 4:02 PM, Richard Biener wrote:
>>> On Tue, Feb 26, 2019 at 3:30 PM Martin Liška <mliska@suse.cz> wrote:
>>>>
>>>> Hi.
>>>>
>>>> I've rewritten bitmap memory statistics which abused unsigned
>>>> type via register_overhead (map, -((int)sizeof (bitmap_head))).
>>>> I come up with a concept that each bitmap has assigned a unique ID
>>>> which is used for stats tracking. It's caused by fact that e.g. DF
>> is
>>>> heavily reallocating bitmaps that then have a different address.
>>>>
>>>> Survives bootstrap with --enable-gather-detailed-mem-stats.
>>>>
>>>> Ready for next stage1?
>>>
>>> +  /* Get bitmap descriptor UID casted to an unsigned integer
>> pointer.  */
>>> +  unsigned *get_descriptor ()
>>> +  {
>>> +    return (unsigned *)(ptrdiff_t)alloc_descriptor;
>>> +  }
>>>
>>> this one is a bit ugly and together with
>>
>> I know it's not perfect.
>>
>>>
>>> template <typename Type>
>>> inline hashval_t
>>> pointer_hash <Type>::hash (const value_type &candidate)
>>> {
>>>   /* This is a really poor hash function, but it is what the current
>> code uses,
>>>      so I am reusing it to avoid an additional axis in testing.  */
>>>   return (hashval_t) ((intptr_t)candidate >> 3);
>>>
>>> will give quite some hash collisions.  So I guess you should shift
>>> the descriptor << 3 at least (and then make it at most 29 bits in
>>> size?).
>>
>> That's easily doable.
>>
>>> Not sure what to do about the descriptor wrapping btw.
>>
>> Question is whether we want to invest in our internal scaffolding more
>> time?
>> Or can we live with the ugly casting?
> 
> I guess we can live with it if we can avoid the hash collisions. 

Great.

Then there's updated version of the patch for next stage1.

Martin

> 
> Richard. 
> 
>> Martin
>>
>>>
>>> Richard.
>>>
>>>> Thanks,
>>>> Martin
>>>>
>>>> gcc/ChangeLog:
>>>>
>>>> 2019-02-26  Martin Liska  <mliska@suse.cz>
>>>>
>>>>         * bitmap.c (bitmap_register): Come up with
>>>>         alloc_descriptor_max_uid and assign it for
>>>>         a new bitmap.
>>>>         (register_overhead): Use get_descriptor as
>>>>         a descriptor.
>>>>         (release_overhead): New.
>>>>         (bitmap_elem_to_freelist): Call it.
>>>>         (bitmap_elt_clear_from): Likewise.
>>>>         (bitmap_obstack_free): Likewise.
>>>>         (bitmap_move): Sensitively release memory.
>>>>         * bitmap.h (struct GTY): Add alloc_descriptor.
>>>>         (bitmap_initialize): Initialize alloc_descriptor to zero.
>>>>         * tree-ssa-pre.c (do_hoist_insertion): Use bitmap_move.
>>>> ---
>>>>  gcc/bitmap.c       | 39 ++++++++++++++++++++++++++++-----------
>>>>  gcc/bitmap.h       | 17 ++++++++++++++---
>>>>  gcc/tree-ssa-pre.c |  2 +-
>>>>  3 files changed, 43 insertions(+), 15 deletions(-)
>>>>
>>>>
>
From 52615d17cc7f598855b647a70be5fafff9e56eba Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Tue, 19 Feb 2019 14:59:46 +0100
Subject: [PATCH] Fix bitmap registration of overheads.

gcc/ChangeLog:

2019-02-26  Martin Liska  <mliska@suse.cz>

	* bitmap.c (bitmap_register): Come up with
	alloc_descriptor_max_uid and assign it for
	a new bitmap.
	(register_overhead): Use get_descriptor as
	a descriptor.
	(release_overhead): New.
	(bitmap_elem_to_freelist): Call it.
	(bitmap_elt_clear_from): Likewise.
	(bitmap_obstack_free): Likewise.
	(bitmap_move): Sensitively release memory.
	* bitmap.h (struct GTY): Add alloc_descriptor.
	(bitmap_initialize): Initialize alloc_descriptor to zero.
	* tree-ssa-pre.c (do_hoist_insertion): Use bitmap_move.
---
 gcc/bitmap.c       | 39 ++++++++++++++++++++++++++++-----------
 gcc/bitmap.h       | 17 ++++++++++++++---
 gcc/tree-ssa-pre.c |  2 +-
 3 files changed, 43 insertions(+), 15 deletions(-)

diff --git a/gcc/bitmap.c b/gcc/bitmap.c
index 5a8236de750..894aefa13de 100644
--- a/gcc/bitmap.c
+++ b/gcc/bitmap.c
@@ -36,18 +36,33 @@ static bitmap_element *bitmap_tree_listify_from (bitmap, bitmap_element *);
 void
 bitmap_register (bitmap b MEM_STAT_DECL)
 {
-  bitmap_mem_desc.register_descriptor (b, BITMAP_ORIGIN, false
-				       FINAL_PASS_MEM_STAT);
+  static unsigned alloc_descriptor_max_uid = 1;
+  gcc_assert (b->alloc_descriptor == 0);
+  b->alloc_descriptor = alloc_descriptor_max_uid++;
+
+  bitmap_mem_desc.register_descriptor (b->get_descriptor (), BITMAP_ORIGIN,
+				       false FINAL_PASS_MEM_STAT);
 }
 
 /* Account the overhead.  */
 static void
 register_overhead (bitmap b, size_t amount)
 {
-  if (bitmap_mem_desc.contains_descriptor_for_instance (b))
-    bitmap_mem_desc.register_instance_overhead (amount, b);
+  unsigned *d = b->get_descriptor ();
+  if (bitmap_mem_desc.contains_descriptor_for_instance (d))
+    bitmap_mem_desc.register_instance_overhead (amount, d);
+}
+
+/* Release the overhead.  */
+static void
+release_overhead (bitmap b, size_t amount, bool remove_from_map)
+{
+  unsigned *d = b->get_descriptor ();
+  if (bitmap_mem_desc.contains_descriptor_for_instance (d))
+    bitmap_mem_desc.release_instance_overhead (d, amount, remove_from_map);
 }
 
+
 /* Global data */
 bitmap_element bitmap_zero_bits;  /* An element of all zero bits.  */
 bitmap_obstack bitmap_default_obstack;    /* The default bitmap obstack.  */
@@ -65,7 +80,7 @@ bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
   bitmap_obstack *bit_obstack = head->obstack;
 
   if (GATHER_STATISTICS)
-    register_overhead (head, -((int)sizeof (bitmap_element)));
+    release_overhead (head, sizeof (bitmap_element), false);
 
   elt->next = NULL;
   elt->indx = -1;
@@ -153,7 +168,7 @@ bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
       int n = 0;
       for (prev = elt; prev; prev = prev->next)
 	n++;
-      register_overhead (head, -sizeof (bitmap_element) * n);
+      release_overhead (head, sizeof (bitmap_element) * n, false);
     }
 
   prev = elt->prev;
@@ -798,7 +813,7 @@ bitmap_obstack_free (bitmap map)
       map->first = (bitmap_element *) map->obstack->heads;
 
       if (GATHER_STATISTICS)
-	register_overhead (map, -((int)sizeof (bitmap_head)));
+	release_overhead (map, sizeof (bitmap_head), true);
 
       map->obstack->heads = map;
     }
@@ -872,16 +887,18 @@ bitmap_move (bitmap to, bitmap from)
 
   bitmap_clear (to);
 
-  *to = *from;
-
+  size_t sz = 0;
   if (GATHER_STATISTICS)
     {
-      size_t sz = 0;
       for (bitmap_element *e = to->first; e; e = e->next)
 	sz += sizeof (bitmap_element);
       register_overhead (to, sz);
-      register_overhead (from, -sz);
     }
+
+  *to = *from;
+
+  if (GATHER_STATISTICS)
+    release_overhead (from, sz, false);
 }
 
 /* Clear a single bit in a bitmap.  Return true if the bit changed.  */
diff --git a/gcc/bitmap.h b/gcc/bitmap.h
index ed25c1ee5da..b0813ebb1c2 100644
--- a/gcc/bitmap.h
+++ b/gcc/bitmap.h
@@ -325,14 +325,16 @@ struct GTY(()) bitmap_head {
   static bitmap_obstack crashme;
   /* Poison obstack to not make it not a valid initialized GC bitmap.  */
   CONSTEXPR bitmap_head()
-    : indx(0), tree_form(false), first(NULL), current(NULL),
-      obstack (&crashme)
+    : indx (0), tree_form (false), alloc_descriptor (0), first (NULL),
+      current (NULL), obstack (&crashme)
   {}
   /* Index of last element looked at.  */
   unsigned int indx;
   /* False if the bitmap is in list form; true if the bitmap is in tree form.
      Bitmap iterators only work on bitmaps in list form.  */
-  bool tree_form;
+  unsigned tree_form: 1;
+  /* Bitmap UID used for memory allocation statistics.  */
+  unsigned alloc_descriptor: 29;
   /* In list form, the first element in the linked list;
      in tree form, the root of the tree.   */
   bitmap_element *first;
@@ -340,7 +342,15 @@ struct GTY(()) bitmap_head {
   bitmap_element * GTY((skip(""))) current;
   /* Obstack to allocate elements from.  If NULL, then use GGC allocation.  */
   bitmap_obstack * GTY((skip(""))) obstack;
+
+  /* Dump bitmap.  */
   void dump ();
+
+  /* Get bitmap descriptor UID casted to an unsigned integer pointer.  */
+  unsigned *get_descriptor ()
+  {
+    return (unsigned *)(ptrdiff_t)(alloc_descriptor << 3);
+  }
 };
 
 /* Global data */
@@ -441,6 +451,7 @@ bitmap_initialize (bitmap head, bitmap_obstack *obstack CXX_MEM_STAT_INFO)
 {
   head->first = head->current = NULL;
   head->indx = head->tree_form = 0;
+  head->alloc_descriptor = 0;
   head->obstack = obstack;
   if (GATHER_STATISTICS)
     bitmap_register (head PASS_MEM_STAT);
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 3f38371cb21..7d6d9dee48a 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -3531,7 +3531,7 @@ do_hoist_insertion (basic_block block)
     return false;
 
   /* Hack hoitable_set in-place so we can use sorted_array_from_bitmap_set.  */
-  hoistable_set.values = availout_in_some;
+  bitmap_move (&hoistable_set.values, &availout_in_some);
   hoistable_set.expressions = ANTIC_IN (block)->expressions;
 
   /* Now finally construct the topological-ordered expression set.  */

On Wed, Feb 27, 2019 at 9:01 AM Martin Liška <mliska@suse.cz> wrote:
>
> On 2/26/19 7:48 PM, Richard Biener wrote:
> > On February 26, 2019 6:50:13 PM GMT+01:00, "Martin Liška" <mliska@suse.cz> wrote:
> >> On 2/26/19 4:02 PM, Richard Biener wrote:
> >>> On Tue, Feb 26, 2019 at 3:30 PM Martin Liška <mliska@suse.cz> wrote:
> >>>>
> >>>> Hi.
> >>>>
> >>>> I've rewritten bitmap memory statistics which abused unsigned
> >>>> type via register_overhead (map, -((int)sizeof (bitmap_head))).
> >>>> I come up with a concept that each bitmap has assigned a unique ID
> >>>> which is used for stats tracking. It's caused by fact that e.g. DF
> >> is
> >>>> heavily reallocating bitmaps that then have a different address.
> >>>>
> >>>> Survives bootstrap with --enable-gather-detailed-mem-stats.
> >>>>
> >>>> Ready for next stage1?
> >>>
> >>> +  /* Get bitmap descriptor UID casted to an unsigned integer
> >> pointer.  */
> >>> +  unsigned *get_descriptor ()
> >>> +  {
> >>> +    return (unsigned *)(ptrdiff_t)alloc_descriptor;
> >>> +  }
> >>>
> >>> this one is a bit ugly and together with
> >>
> >> I know it's not perfect.
> >>
> >>>
> >>> template <typename Type>
> >>> inline hashval_t
> >>> pointer_hash <Type>::hash (const value_type &candidate)
> >>> {
> >>>   /* This is a really poor hash function, but it is what the current
> >> code uses,
> >>>      so I am reusing it to avoid an additional axis in testing.  */
> >>>   return (hashval_t) ((intptr_t)candidate >> 3);
> >>>
> >>> will give quite some hash collisions.  So I guess you should shift
> >>> the descriptor << 3 at least (and then make it at most 29 bits in
> >>> size?).
> >>
> >> That's easily doable.
> >>
> >>> Not sure what to do about the descriptor wrapping btw.
> >>
> >> Question is whether we want to invest in our internal scaffolding more
> >> time?
> >> Or can we live with the ugly casting?
> >
> > I guess we can live with it if we can avoid the hash collisions.
>
> Great.
>
> Then there's updated version of the patch for next stage1.

LGTM.  The << 3 in get_descriptor deserves a comment though.

Also leaving two bits in the bitfield uninitialized may generate
awkward code (you might want to check), explicitely having
a pad : 2 and initializing that to zero might allow better code
generation here (guarding the member and init with
#if might also be possible).

Richard.

> Martin
>
> >
> > Richard.
> >
> >> Martin
> >>
> >>>
> >>> Richard.
> >>>
> >>>> Thanks,
> >>>> Martin
> >>>>
> >>>> gcc/ChangeLog:
> >>>>
> >>>> 2019-02-26  Martin Liska  <mliska@suse.cz>
> >>>>
> >>>>         * bitmap.c (bitmap_register): Come up with
> >>>>         alloc_descriptor_max_uid and assign it for
> >>>>         a new bitmap.
> >>>>         (register_overhead): Use get_descriptor as
> >>>>         a descriptor.
> >>>>         (release_overhead): New.
> >>>>         (bitmap_elem_to_freelist): Call it.
> >>>>         (bitmap_elt_clear_from): Likewise.
> >>>>         (bitmap_obstack_free): Likewise.
> >>>>         (bitmap_move): Sensitively release memory.
> >>>>         * bitmap.h (struct GTY): Add alloc_descriptor.
> >>>>         (bitmap_initialize): Initialize alloc_descriptor to zero.
> >>>>         * tree-ssa-pre.c (do_hoist_insertion): Use bitmap_move.
> >>>> ---
> >>>>  gcc/bitmap.c       | 39 ++++++++++++++++++++++++++++-----------
> >>>>  gcc/bitmap.h       | 17 ++++++++++++++---
> >>>>  gcc/tree-ssa-pre.c |  2 +-
> >>>>  3 files changed, 43 insertions(+), 15 deletions(-)
> >>>>
> >>>>
> >
>

On 2/27/19 11:45 AM, Richard Biener wrote:
> On Wed, Feb 27, 2019 at 9:01 AM Martin Liška <mliska@suse.cz> wrote:
>>
>> On 2/26/19 7:48 PM, Richard Biener wrote:
>>> On February 26, 2019 6:50:13 PM GMT+01:00, "Martin Liška" <mliska@suse.cz> wrote:
>>>> On 2/26/19 4:02 PM, Richard Biener wrote:
>>>>> On Tue, Feb 26, 2019 at 3:30 PM Martin Liška <mliska@suse.cz> wrote:
>>>>>>
>>>>>> Hi.
>>>>>>
>>>>>> I've rewritten bitmap memory statistics which abused unsigned
>>>>>> type via register_overhead (map, -((int)sizeof (bitmap_head))).
>>>>>> I come up with a concept that each bitmap has assigned a unique ID
>>>>>> which is used for stats tracking. It's caused by fact that e.g. DF
>>>> is
>>>>>> heavily reallocating bitmaps that then have a different address.
>>>>>>
>>>>>> Survives bootstrap with --enable-gather-detailed-mem-stats.
>>>>>>
>>>>>> Ready for next stage1?
>>>>>
>>>>> +  /* Get bitmap descriptor UID casted to an unsigned integer
>>>> pointer.  */
>>>>> +  unsigned *get_descriptor ()
>>>>> +  {
>>>>> +    return (unsigned *)(ptrdiff_t)alloc_descriptor;
>>>>> +  }
>>>>>
>>>>> this one is a bit ugly and together with
>>>>
>>>> I know it's not perfect.
>>>>
>>>>>
>>>>> template <typename Type>
>>>>> inline hashval_t
>>>>> pointer_hash <Type>::hash (const value_type &candidate)
>>>>> {
>>>>>   /* This is a really poor hash function, but it is what the current
>>>> code uses,
>>>>>      so I am reusing it to avoid an additional axis in testing.  */
>>>>>   return (hashval_t) ((intptr_t)candidate >> 3);
>>>>>
>>>>> will give quite some hash collisions.  So I guess you should shift
>>>>> the descriptor << 3 at least (and then make it at most 29 bits in
>>>>> size?).
>>>>
>>>> That's easily doable.
>>>>
>>>>> Not sure what to do about the descriptor wrapping btw.
>>>>
>>>> Question is whether we want to invest in our internal scaffolding more
>>>> time?
>>>> Or can we live with the ugly casting?
>>>
>>> I guess we can live with it if we can avoid the hash collisions.
>>
>> Great.
>>
>> Then there's updated version of the patch for next stage1.
> 
> LGTM.  The << 3 in get_descriptor deserves a comment though.
> 
> Also leaving two bits in the bitfield uninitialized may generate
> awkward code (you might want to check), explicitely having
> a pad : 2 and initializing that to zero might allow better code
> generation here (guarding the member and init with
> #if might also be possible).
> 
> Richard.
> 
>> Martin
>>
>>>
>>> Richard.
>>>
>>>> Martin
>>>>
>>>>>
>>>>> Richard.
>>>>>
>>>>>> Thanks,
>>>>>> Martin
>>>>>>
>>>>>> gcc/ChangeLog:
>>>>>>
>>>>>> 2019-02-26  Martin Liska  <mliska@suse.cz>
>>>>>>
>>>>>>         * bitmap.c (bitmap_register): Come up with
>>>>>>         alloc_descriptor_max_uid and assign it for
>>>>>>         a new bitmap.
>>>>>>         (register_overhead): Use get_descriptor as
>>>>>>         a descriptor.
>>>>>>         (release_overhead): New.
>>>>>>         (bitmap_elem_to_freelist): Call it.
>>>>>>         (bitmap_elt_clear_from): Likewise.
>>>>>>         (bitmap_obstack_free): Likewise.
>>>>>>         (bitmap_move): Sensitively release memory.
>>>>>>         * bitmap.h (struct GTY): Add alloc_descriptor.
>>>>>>         (bitmap_initialize): Initialize alloc_descriptor to zero.
>>>>>>         * tree-ssa-pre.c (do_hoist_insertion): Use bitmap_move.
>>>>>> ---
>>>>>>  gcc/bitmap.c       | 39 ++++++++++++++++++++++++++++-----------
>>>>>>  gcc/bitmap.h       | 17 ++++++++++++++---
>>>>>>  gcc/tree-ssa-pre.c |  2 +-
>>>>>>  3 files changed, 43 insertions(+), 15 deletions(-)
>>>>>>
>>>>>>
>>>
>>

I'm sending updated version of the patch.

Martin
From db6f30e63d5b739375821d89791735acffeae380 Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Tue, 19 Feb 2019 14:59:46 +0100
Subject: [PATCH] Fix bitmap registration of overheads.

gcc/ChangeLog:

2019-02-26  Martin Liska  <mliska@suse.cz>

	* bitmap.c (bitmap_register): Come up with
	alloc_descriptor_max_uid and assign it for
	a new bitmap.
	(register_overhead): Use get_descriptor as
	a descriptor.
	(release_overhead): New.
	(bitmap_elem_to_freelist): Call it.
	(bitmap_elt_clear_from): Likewise.
	(bitmap_obstack_free): Likewise.
	(bitmap_move): Sensitively release memory.
	* bitmap.h (struct GTY): Add alloc_descriptor and padding.
	(bitmap_initialize): Initialize alloc_descriptor to zero.
	* tree-ssa-pre.c (do_hoist_insertion): Use bitmap_move.
---
 gcc/bitmap.c       | 39 ++++++++++++++++++++++++++++-----------
 gcc/bitmap.h       | 22 +++++++++++++++++++---
 gcc/tree-ssa-pre.c |  2 +-
 3 files changed, 48 insertions(+), 15 deletions(-)

diff --git a/gcc/bitmap.c b/gcc/bitmap.c
index 5a8236de750..894aefa13de 100644
--- a/gcc/bitmap.c
+++ b/gcc/bitmap.c
@@ -36,18 +36,33 @@ static bitmap_element *bitmap_tree_listify_from (bitmap, bitmap_element *);
 void
 bitmap_register (bitmap b MEM_STAT_DECL)
 {
-  bitmap_mem_desc.register_descriptor (b, BITMAP_ORIGIN, false
-				       FINAL_PASS_MEM_STAT);
+  static unsigned alloc_descriptor_max_uid = 1;
+  gcc_assert (b->alloc_descriptor == 0);
+  b->alloc_descriptor = alloc_descriptor_max_uid++;
+
+  bitmap_mem_desc.register_descriptor (b->get_descriptor (), BITMAP_ORIGIN,
+				       false FINAL_PASS_MEM_STAT);
 }
 
 /* Account the overhead.  */
 static void
 register_overhead (bitmap b, size_t amount)
 {
-  if (bitmap_mem_desc.contains_descriptor_for_instance (b))
-    bitmap_mem_desc.register_instance_overhead (amount, b);
+  unsigned *d = b->get_descriptor ();
+  if (bitmap_mem_desc.contains_descriptor_for_instance (d))
+    bitmap_mem_desc.register_instance_overhead (amount, d);
+}
+
+/* Release the overhead.  */
+static void
+release_overhead (bitmap b, size_t amount, bool remove_from_map)
+{
+  unsigned *d = b->get_descriptor ();
+  if (bitmap_mem_desc.contains_descriptor_for_instance (d))
+    bitmap_mem_desc.release_instance_overhead (d, amount, remove_from_map);
 }
 
+
 /* Global data */
 bitmap_element bitmap_zero_bits;  /* An element of all zero bits.  */
 bitmap_obstack bitmap_default_obstack;    /* The default bitmap obstack.  */
@@ -65,7 +80,7 @@ bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
   bitmap_obstack *bit_obstack = head->obstack;
 
   if (GATHER_STATISTICS)
-    register_overhead (head, -((int)sizeof (bitmap_element)));
+    release_overhead (head, sizeof (bitmap_element), false);
 
   elt->next = NULL;
   elt->indx = -1;
@@ -153,7 +168,7 @@ bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
       int n = 0;
       for (prev = elt; prev; prev = prev->next)
 	n++;
-      register_overhead (head, -sizeof (bitmap_element) * n);
+      release_overhead (head, sizeof (bitmap_element) * n, false);
     }
 
   prev = elt->prev;
@@ -798,7 +813,7 @@ bitmap_obstack_free (bitmap map)
       map->first = (bitmap_element *) map->obstack->heads;
 
       if (GATHER_STATISTICS)
-	register_overhead (map, -((int)sizeof (bitmap_head)));
+	release_overhead (map, sizeof (bitmap_head), true);
 
       map->obstack->heads = map;
     }
@@ -872,16 +887,18 @@ bitmap_move (bitmap to, bitmap from)
 
   bitmap_clear (to);
 
-  *to = *from;
-
+  size_t sz = 0;
   if (GATHER_STATISTICS)
     {
-      size_t sz = 0;
       for (bitmap_element *e = to->first; e; e = e->next)
 	sz += sizeof (bitmap_element);
       register_overhead (to, sz);
-      register_overhead (from, -sz);
     }
+
+  *to = *from;
+
+  if (GATHER_STATISTICS)
+    release_overhead (from, sz, false);
 }
 
 /* Clear a single bit in a bitmap.  Return true if the bit changed.  */
diff --git a/gcc/bitmap.h b/gcc/bitmap.h
index ed25c1ee5da..39f509db611 100644
--- a/gcc/bitmap.h
+++ b/gcc/bitmap.h
@@ -325,14 +325,18 @@ struct GTY(()) bitmap_head {
   static bitmap_obstack crashme;
   /* Poison obstack to not make it not a valid initialized GC bitmap.  */
   CONSTEXPR bitmap_head()
-    : indx(0), tree_form(false), first(NULL), current(NULL),
-      obstack (&crashme)
+    : indx (0), tree_form (false), padding (0), alloc_descriptor (0), first (NULL),
+      current (NULL), obstack (&crashme)
   {}
   /* Index of last element looked at.  */
   unsigned int indx;
   /* False if the bitmap is in list form; true if the bitmap is in tree form.
      Bitmap iterators only work on bitmaps in list form.  */
-  bool tree_form;
+  unsigned tree_form: 1;
+  /* Next integer is shifted, so padding is needed.  */
+  unsigned padding: 2;
+  /* Bitmap UID used for memory allocation statistics.  */
+  unsigned alloc_descriptor: 29;
   /* In list form, the first element in the linked list;
      in tree form, the root of the tree.   */
   bitmap_element *first;
@@ -340,7 +344,17 @@ struct GTY(()) bitmap_head {
   bitmap_element * GTY((skip(""))) current;
   /* Obstack to allocate elements from.  If NULL, then use GGC allocation.  */
   bitmap_obstack * GTY((skip(""))) obstack;
+
+  /* Dump bitmap.  */
   void dump ();
+
+  /* Get bitmap descriptor UID casted to an unsigned integer pointer.
+     Shift the descriptor because pointer_hash<Type>::hash is
+     doing >> 3 shift operation.  */
+  unsigned *get_descriptor ()
+  {
+    return (unsigned *)(ptrdiff_t)(alloc_descriptor << 3);
+  }
 };
 
 /* Global data */
@@ -441,6 +455,8 @@ bitmap_initialize (bitmap head, bitmap_obstack *obstack CXX_MEM_STAT_INFO)
 {
   head->first = head->current = NULL;
   head->indx = head->tree_form = 0;
+  head->padding = 0;
+  head->alloc_descriptor = 0;
   head->obstack = obstack;
   if (GATHER_STATISTICS)
     bitmap_register (head PASS_MEM_STAT);
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 3f38371cb21..7d6d9dee48a 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -3531,7 +3531,7 @@ do_hoist_insertion (basic_block block)
     return false;
 
   /* Hack hoitable_set in-place so we can use sorted_array_from_bitmap_set.  */
-  hoistable_set.values = availout_in_some;
+  bitmap_move (&hoistable_set.values, &availout_in_some);
   hoistable_set.expressions = ANTIC_IN (block)->expressions;
 
   /* Now finally construct the topological-ordered expression set.  */