[Bug middle-end/37448] patch to compute alloc-pool stats correctly

[Bug middle-end/37448] patch to compute alloc-pool stats correctly

[Kenneth Zadeck]

[-- Attachment #1: Type: text/plain, Size: 965 bytes --]

The df-ref problems pointed to by honza with respect to 37448 are
because alloc-pool.c incorrectly computed peak usage statistics.  It did
not compute them properly if pool_free was used to individually free
objects (like we do all over the place in df.)

This patch has been bootstapped on x86-64.

Note that no one owns alloc-pool so if someone with general oversight
could review this, it would be appreciated.

Note that with this patch and an enhancement to the debug dumps that i
am going to add to my previous patch, we now account for all of the
df-refs.  

OK to commit.

Kenny

2008-09-26  Kenneth Zadeck <zadeck@naturalbridge.com>

    PR rtl-optimization/37448
    alloc_pool_desc (elt_size): New field.
    alloc-pool.c (create_alloc_pool, empty_alloc_pool, pool_alloc,
    pool_free): Properly keep track of desc->size.
    (print_statistics, dump_alloc_pool_statistics): Enhance the
    printing of statistics to print the number of elements.

    


[-- Attachment #2: allocpoolstats1.diff --]
[-- Type: text/x-patch, Size: 4869 bytes --]

Index: alloc-pool.c
===================================================================
--- alloc-pool.c	(revision 140690)
+++ alloc-pool.c	(working copy)
@@ -64,14 +64,27 @@ static ALLOC_POOL_ID_TYPE last_id;
 
 #ifdef GATHER_STATISTICS
 
-/* Store information about each particular alloc_pool.  */
+/* Store information about each particular alloc_pool.  Note that this
+   will underestimate the amount the amount of storage used by a small amount:
+   1) The overhead in a pool is not accounted for.
+   2) The unallocated elements in a block are not accounted for.  Note
+   that this can at worst case be one element smaller that the block
+   size for that pool.
+*/
 struct alloc_pool_descriptor
 {
   const char *name;
-  int allocated;
+  /* Number of pools allocated.  */
   int created;
-  int peak;
+
+  /* Gross allocated storage.  */
+  int allocated;
+  /* Amount of currently active storage. */
   int current;
+  /* Peak amount of storage used.  */
+  int peak;
+  /* Size of element in the pool.  */
+  int elt_size;
 };
 
 /* Hashtable mapping alloc_pool names to descriptors.  */
@@ -150,6 +163,7 @@ create_alloc_pool (const char *name, siz
   pool->name = /*xstrdup (name)*/name;
 #ifdef GATHER_STATISTICS
   desc = alloc_pool_descriptor (name);
+  desc->elt_size = size;
   desc->created++;
 #endif
   pool->elt_size = size;
@@ -196,11 +210,11 @@ empty_alloc_pool (alloc_pool pool)
     {
       next_block = block->next;
       free (block);
-#ifdef GATHER_STATISTICS
-      desc->current -= pool->block_size;
-#endif
     }
 
+#ifdef GATHER_STATISTICS
+  desc->current -= (pool->elts_allocated - pool->elts_free) * pool->elt_size;
+#endif
   pool->returned_free_list = NULL;
   pool->virgin_free_list = NULL;
   pool->virgin_elts_remaining = 0;
@@ -242,7 +256,10 @@ pool_alloc (alloc_pool pool)
 #ifdef GATHER_STATISTICS
   struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
 
-  desc->allocated+=pool->elt_size;
+  desc->allocated += pool->elt_size;
+  desc->current += pool->elt_size;
+  if (desc->peak < desc->current)
+    desc->peak = desc->current;
 #endif
 
   gcc_assert (pool);
@@ -259,11 +276,6 @@ pool_alloc (alloc_pool pool)
 	  block = XNEWVEC (char, pool->block_size);
 	  block_header = (alloc_pool_list) block;
 	  block += align_eight (sizeof (struct alloc_pool_list_def));
-#ifdef GATHER_STATISTICS
-	  desc->current += pool->block_size;
-	  if (desc->peak < desc->current)
-	    desc->peak = desc->current;
-#endif
 	  
 	  /* Throw it on the block list.  */
 	  block_header->next = pool->block_list;
@@ -314,6 +326,9 @@ void
 pool_free (alloc_pool pool, void *ptr)
 {
   alloc_pool_list header;
+#ifdef GATHER_STATISTICS
+  struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
+#endif
 
   gcc_assert (ptr);
 
@@ -334,6 +349,11 @@ pool_free (alloc_pool pool, void *ptr)
   header->next = pool->returned_free_list;
   pool->returned_free_list = header;
   pool->elts_free++;
+
+#ifdef GATHER_STATISTICS
+  desc->current -= pool->elt_size;
+#endif
+
 }
 /* Output per-alloc_pool statistics.  */
 #ifdef GATHER_STATISTICS
@@ -355,8 +375,10 @@ print_statistics (void **slot, void *b)
 
   if (d->allocated)
     {
-      fprintf (stderr, "%-21s %6d %10d %10d %10d\n", d->name,
-	       d->created, d->allocated, d->peak, d->current);
+      fprintf (stderr, "%-22s %6d %10d %10d(%10d) %10d(%10d) %10d(%10d)\n", d->name,
+	       d->elt_size, d->created, d->allocated, d->allocated / d->elt_size, 
+	       d->peak, d->peak / d->elt_size, 
+	       d->current, d->current / d->elt_size);
       i->size += d->allocated;
       i->count += d->created;
     }
@@ -374,14 +396,14 @@ dump_alloc_pool_statistics (void)
   if (!alloc_pool_hash)
     return;
 
-  fprintf (stderr, "\nAlloc-pool Kind        Pools  Allocated      Peak        Leak\n");
-  fprintf (stderr, "-------------------------------------------------------------\n");
+  fprintf (stderr, "\nAlloc-pool Kind         Pools  Elt size  Allocated (elts)           Peak (elts)           Leak (elts)\n");
+  fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
   info.count = 0;
   info.size = 0;
   htab_traverse (alloc_pool_hash, print_statistics, &info);
-  fprintf (stderr, "-------------------------------------------------------------\n");
-  fprintf (stderr, "%-20s %7d %10d\n",
+  fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
+  fprintf (stderr, "%-22s           %7d %10d\n",
 	   "Total", info.count, info.size);
-  fprintf (stderr, "-------------------------------------------------------------\n");
+  fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
 #endif
 }

Re: [Bug middle-end/37448] patch to compute alloc-pool stats correctly

[Ian Lance Taylor]

Kenneth Zadeck <zadeck@naturalbridge.com> writes:

> 2008-09-26  Kenneth Zadeck <zadeck@naturalbridge.com>
>
>     PR rtl-optimization/37448
>     alloc_pool_desc (elt_size): New field.
>     alloc-pool.c (create_alloc_pool, empty_alloc_pool, pool_alloc,
>     pool_free): Properly keep track of desc->size.
>     (print_statistics, dump_alloc_pool_statistics): Enhance the
>     printing of statistics to print the number of elements.


> -/* Store information about each particular alloc_pool.  */
> +/* Store information about each particular alloc_pool.  Note that this
> +   will underestimate the amount the amount of storage used by a small amount:
> +   1) The overhead in a pool is not accounted for.
> +   2) The unallocated elements in a block are not accounted for.  Note
> +   that this can at worst case be one element smaller that the block
> +   size for that pool.
> +*/

Please put the */ at the end of the previous line.

I wonder if some of the types in alloc_pool_descriptor should be
size_t rather than int, though it's hard to imagine it making a
difference in real life.

OK with that change.

Thanks.

Ian

Re: [Bug middle-end/37448] patch to compute alloc-pool stats correctly

[Kenneth Zadeck]

Ian Lance Taylor wrote:
> Kenneth Zadeck <zadeck@naturalbridge.com> writes:
>
>   
>> 2008-09-26  Kenneth Zadeck <zadeck@naturalbridge.com>
>>
>>     PR rtl-optimization/37448
>>     alloc_pool_desc (elt_size): New field.
>>     alloc-pool.c (create_alloc_pool, empty_alloc_pool, pool_alloc,
>>     pool_free): Properly keep track of desc->size.
>>     (print_statistics, dump_alloc_pool_statistics): Enhance the
>>     printing of statistics to print the number of elements.
>>     
>
>
>   
>> -/* Store information about each particular alloc_pool.  */
>> +/* Store information about each particular alloc_pool.  Note that this
>> +   will underestimate the amount the amount of storage used by a small amount:
>> +   1) The overhead in a pool is not accounted for.
>> +   2) The unallocated elements in a block are not accounted for.  Note
>> +   that this can at worst case be one element smaller that the block
>> +   size for that pool.
>> +*/
>>     
>
> Please put the */ at the end of the previous line.
>
>   
of course.
> I wonder if some of the types in alloc_pool_descriptor should be
> size_t rather than int, though it's hard to imagine it making a
> difference in real life.
>
>   
I noticed this too, it actually does make a difference in the printing
of the values on the testcase since they overflow.  However, I did not
know how to modify the formats in the printfs to print the size_ts.

Kenny

> OK with that change.
>
> Thanks.
>
> Ian
>   

Re: [Bug middle-end/37448] patch to compute alloc-pool stats correctly

[Ian Lance Taylor]

Kenneth Zadeck <zadeck@naturalbridge.com> writes:

>> I wonder if some of the types in alloc_pool_descriptor should be
>> size_t rather than int, though it's hard to imagine it making a
>> difference in real life.
>>
>>   
> I noticed this too, it actually does make a difference in the printing
> of the values on the testcase since they overflow.  However, I did not
> know how to modify the formats in the printfs to print the size_ts.

The simple way is to use "unsigned long" and "%lu".

Ian

Re: [Bug middle-end/37448] patch to compute alloc-pool stats correctly

[Kenneth Zadeck]

Ian Lance Taylor wrote:
> Kenneth Zadeck <zadeck@naturalbridge.com> writes:
>
>   
>>> I wonder if some of the types in alloc_pool_descriptor should be
>>> size_t rather than int, though it's hard to imagine it making a
>>> difference in real life.
>>>
>>>   
>>>       
>> I noticed this too, it actually does make a difference in the printing
>> of the values on the testcase since they overflow.  However, I did not
>> know how to modify the formats in the printfs to print the size_ts.
>>     
>
> The simple way is to use "unsigned long" and "%lu".
>
> Ian
>   
do you want me to redo the patch with this change?

kenny

Re: [Bug middle-end/37448] patch to compute alloc-pool stats correctly

[Ian Lance Taylor]

Kenneth Zadeck <zadeck@naturalbridge.com> writes:

> Ian Lance Taylor wrote:
>> Kenneth Zadeck <zadeck@naturalbridge.com> writes:
>>
>>   
>>>> I wonder if some of the types in alloc_pool_descriptor should be
>>>> size_t rather than int, though it's hard to imagine it making a
>>>> difference in real life.
>>>>
>>>>   
>>>>       
>>> I noticed this too, it actually does make a difference in the printing
>>> of the values on the testcase since they overflow.  However, I did not
>>> know how to modify the formats in the printfs to print the size_ts.
>>>     
>>
>> The simple way is to use "unsigned long" and "%lu".
>>
>> Ian
>>   
> do you want me to redo the patch with this change?

That change to the patch is preapproved if you want to do it.

Ian

Re: [Bug middle-end/37448] patch to compute alloc-pool stats correctly

[Kenneth Zadeck]

[-- Attachment #1: Type: text/plain, Size: 1618 bytes --]

all done, committed as revision 150960.

2008-10-07  Kenneth Zadeck <zadeck@naturalbridge.com>

    PR rtl-optimization/37448
    alloc_pool_desc (elt_size): New field.
    alloc_pool_desc (created, allocated, current, peak): Make unsigned
    long.
    output_info (count): Renamed total_created and made unsigned long.
    output_info (size): Renamed total_allocated and made unsigned long.
    alloc-pool.c (create_alloc_pool, empty_alloc_pool, pool_alloc,
    pool_free): Properly keep track of desc->size.
    (print_statistics, dump_alloc_pool_statistics): Enhance the
    printing of statistics to print the number of elements and to use
    unsigned longs.
   
Bootstrapped and tested with the testcase in 37448.

Kenny


Ian Lance Taylor wrote:
> Kenneth Zadeck <zadeck@naturalbridge.com> writes:
>
>   
>> Ian Lance Taylor wrote:
>>     
>>> Kenneth Zadeck <zadeck@naturalbridge.com> writes:
>>>
>>>   
>>>       
>>>>> I wonder if some of the types in alloc_pool_descriptor should be
>>>>> size_t rather than int, though it's hard to imagine it making a
>>>>> difference in real life.
>>>>>
>>>>>   
>>>>>       
>>>>>           
>>>> I noticed this too, it actually does make a difference in the printing
>>>> of the values on the testcase since they overflow.  However, I did not
>>>> know how to modify the formats in the printfs to print the size_ts.
>>>>     
>>>>         
>>> The simple way is to use "unsigned long" and "%lu".
>>>
>>> Ian
>>>   
>>>       
>> do you want me to redo the patch with this change?
>>     
>
> That change to the patch is preapproved if you want to do it.
>
> Ian
>   


[-- Attachment #2: allocpoolstats2.diff --]
[-- Type: text/x-patch, Size: 5485 bytes --]

Index: alloc-pool.c
===================================================================
--- alloc-pool.c	(revision 140959)
+++ alloc-pool.c	(working copy)
@@ -64,14 +64,25 @@ static ALLOC_POOL_ID_TYPE last_id;
 
 #ifdef GATHER_STATISTICS
 
-/* Store information about each particular alloc_pool.  */
+/* Store information about each particular alloc_pool.  Note that this
+   will underestimate the amount the amount of storage used by a small amount:
+   1) The overhead in a pool is not accounted for.
+   2) The unallocated elements in a block are not accounted for.  Note
+   that this can at worst case be one element smaller that the block
+   size for that pool.  */
 struct alloc_pool_descriptor
 {
   const char *name;
-  int allocated;
-  int created;
-  int peak;
-  int current;
+  /* Number of pools allocated.  */
+  unsigned long created;
+  /* Gross allocated storage.  */
+  unsigned long allocated;
+  /* Amount of currently active storage. */
+  unsigned long current;
+  /* Peak amount of storage used.  */
+  unsigned long peak;
+  /* Size of element in the pool.  */
+  int elt_size;
 };
 
 /* Hashtable mapping alloc_pool names to descriptors.  */
@@ -150,6 +161,7 @@ create_alloc_pool (const char *name, siz
   pool->name = /*xstrdup (name)*/name;
 #ifdef GATHER_STATISTICS
   desc = alloc_pool_descriptor (name);
+  desc->elt_size = size;
   desc->created++;
 #endif
   pool->elt_size = size;
@@ -196,11 +208,11 @@ empty_alloc_pool (alloc_pool pool)
     {
       next_block = block->next;
       free (block);
-#ifdef GATHER_STATISTICS
-      desc->current -= pool->block_size;
-#endif
     }
 
+#ifdef GATHER_STATISTICS
+  desc->current -= (pool->elts_allocated - pool->elts_free) * pool->elt_size;
+#endif
   pool->returned_free_list = NULL;
   pool->virgin_free_list = NULL;
   pool->virgin_elts_remaining = 0;
@@ -242,7 +254,10 @@ pool_alloc (alloc_pool pool)
 #ifdef GATHER_STATISTICS
   struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
 
-  desc->allocated+=pool->elt_size;
+  desc->allocated += pool->elt_size;
+  desc->current += pool->elt_size;
+  if (desc->peak < desc->current)
+    desc->peak = desc->current;
 #endif
 
   gcc_assert (pool);
@@ -259,11 +274,6 @@ pool_alloc (alloc_pool pool)
 	  block = XNEWVEC (char, pool->block_size);
 	  block_header = (alloc_pool_list) block;
 	  block += align_eight (sizeof (struct alloc_pool_list_def));
-#ifdef GATHER_STATISTICS
-	  desc->current += pool->block_size;
-	  if (desc->peak < desc->current)
-	    desc->peak = desc->current;
-#endif
 	  
 	  /* Throw it on the block list.  */
 	  block_header->next = pool->block_list;
@@ -314,6 +324,9 @@ void
 pool_free (alloc_pool pool, void *ptr)
 {
   alloc_pool_list header;
+#ifdef GATHER_STATISTICS
+  struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
+#endif
 
   gcc_assert (ptr);
 
@@ -334,6 +347,11 @@ pool_free (alloc_pool pool, void *ptr)
   header->next = pool->returned_free_list;
   pool->returned_free_list = header;
   pool->elts_free++;
+
+#ifdef GATHER_STATISTICS
+  desc->current -= pool->elt_size;
+#endif
+
 }
 /* Output per-alloc_pool statistics.  */
 #ifdef GATHER_STATISTICS
@@ -341,8 +359,8 @@ pool_free (alloc_pool pool, void *ptr)
 /* Used to accumulate statistics about alloc_pool sizes.  */
 struct output_info
 {
-  int count;
-  int size;
+  unsigned long total_created;
+  unsigned long total_allocated;
 };
 
 /* Called via htab_traverse.  Output alloc_pool descriptor pointed out by SLOT
@@ -355,10 +373,12 @@ print_statistics (void **slot, void *b)
 
   if (d->allocated)
     {
-      fprintf (stderr, "%-21s %6d %10d %10d %10d\n", d->name,
-	       d->created, d->allocated, d->peak, d->current);
-      i->size += d->allocated;
-      i->count += d->created;
+      fprintf (stderr, "%-22s %6d %10lu %10lu(%10lu) %10lu(%10lu) %10lu(%10lu)\n", d->name,
+	       d->elt_size, d->created, d->allocated, d->allocated / d->elt_size, 
+	       d->peak, d->peak / d->elt_size, 
+	       d->current, d->current / d->elt_size);
+      i->total_allocated += d->allocated;
+      i->total_created += d->created;
     }
   return 1;
 }
@@ -374,14 +394,14 @@ dump_alloc_pool_statistics (void)
   if (!alloc_pool_hash)
     return;
 
-  fprintf (stderr, "\nAlloc-pool Kind        Pools  Allocated      Peak        Leak\n");
-  fprintf (stderr, "-------------------------------------------------------------\n");
-  info.count = 0;
-  info.size = 0;
+  fprintf (stderr, "\nAlloc-pool Kind         Elt size  Pools  Allocated (elts)            Peak (elts)            Leak (elts)\n");
+  fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
+  info.total_created = 0;
+  info.total_allocated = 0;
   htab_traverse (alloc_pool_hash, print_statistics, &info);
-  fprintf (stderr, "-------------------------------------------------------------\n");
-  fprintf (stderr, "%-20s %7d %10d\n",
-	   "Total", info.count, info.size);
-  fprintf (stderr, "-------------------------------------------------------------\n");
+  fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
+  fprintf (stderr, "%-22s           %7lu %10lu\n",
+	   "Total", info.total_created, info.total_allocated);
+  fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
 #endif
 }

Re: [Bug middle-end/37448] patch to compute alloc-pool stats correctly

[Richard Guenther]

On Tue, Oct 7, 2008 at 6:52 PM, Ian Lance Taylor <iant@google.com> wrote:
> Kenneth Zadeck <zadeck@naturalbridge.com> writes:
>
>>> I wonder if some of the types in alloc_pool_descriptor should be
>>> size_t rather than int, though it's hard to imagine it making a
>>> difference in real life.
>>>
>>>
>> I noticed this too, it actually does make a difference in the printing
>> of the values on the testcase since they overflow.  However, I did not
>> know how to modify the formats in the printfs to print the size_ts.
>
> The simple way is to use "unsigned long" and "%lu".

Which probably doesn't work for win64 ... of course there
isn't a portable one for size_t or long long.

Richard.

> Ian
>

Re: [Bug middle-end/37448] patch to compute alloc-pool stats correctly

[Kai Tietz]

gcc-patches-owner@gcc.gnu.org wrote on 08.10.2008 09:33:44:

> On Tue, Oct 7, 2008 at 6:52 PM, Ian Lance Taylor <iant@google.com> 
wrote:
> > Kenneth Zadeck <zadeck@naturalbridge.com> writes:
> >
> >>> I wonder if some of the types in alloc_pool_descriptor should be
> >>> size_t rather than int, though it's hard to imagine it making a
> >>> difference in real life.
> >>>
> >>>
> >> I noticed this too, it actually does make a difference in the 
printing
> >> of the values on the testcase since they overflow.  However, I did 
not
> >> know how to modify the formats in the printfs to print the size_ts.
> >
> > The simple way is to use "unsigned long" and "%lu".
> 
> Which probably doesn't work for win64 ... of course there
> isn't a portable one for size_t or long long.
> 
> Richard.
> 
> > Ian
> >
> 

Well, for size_t scalars a pointer dump could be used via %p, isn't it?

Kai

|  (\_/)  This is Bunny. Copy and paste Bunny
| (='.'=) into your signature to help him gain
| (")_(") world domination.

Re: [Bug middle-end/37448] patch to compute alloc-pool stats correctly

[Kenneth Zadeck]

Kai Tietz wrote:
> gcc-patches-owner@gcc.gnu.org wrote on 08.10.2008 09:33:44:
>
>   
>> On Tue, Oct 7, 2008 at 6:52 PM, Ian Lance Taylor <iant@google.com> 
>>     
> wrote:
>   
>>> Kenneth Zadeck <zadeck@naturalbridge.com> writes:
>>>
>>>       
>>>>> I wonder if some of the types in alloc_pool_descriptor should be
>>>>> size_t rather than int, though it's hard to imagine it making a
>>>>> difference in real life.
>>>>>
>>>>>
>>>>>           
>>>> I noticed this too, it actually does make a difference in the 
>>>>         
> printing
>   
>>>> of the values on the testcase since they overflow.  However, I did 
>>>>         
> not
>   
>>>> know how to modify the formats in the printfs to print the size_ts.
>>>>         
>>> The simple way is to use "unsigned long" and "%lu".
>>>       
>> Which probably doesn't work for win64 ... of course there
>> isn't a portable one for size_t or long long.
>>
>> Richard.
>>
>>     
>>> Ian
>>>
>>>       
>
> Well, for size_t scalars a pointer dump could be used via %p, isn't it?
>
>   
I just did the patch according to iant's preapprovial guidelines.  If
anyone wants to change it, I have no real investment in the code.  
However, what is there now is a distinct upgrade compared to what was
there before.  

Kenny
> Kai
>
> |  (\_/)  This is Bunny. Copy and paste Bunny
> | (='.'=) into your signature to help him gain
> | (")_(") world domination.
>
>   

Re: [Bug middle-end/37448] patch to compute alloc-pool stats correctly

[Ian Lance Taylor]

"Richard Guenther" <richard.guenther@gmail.com> writes:

> On Tue, Oct 7, 2008 at 6:52 PM, Ian Lance Taylor <iant@google.com> wrote:
>> Kenneth Zadeck <zadeck@naturalbridge.com> writes:
>>
>>>> I wonder if some of the types in alloc_pool_descriptor should be
>>>> size_t rather than int, though it's hard to imagine it making a
>>>> difference in real life.
>>>>
>>>>
>>> I noticed this too, it actually does make a difference in the printing
>>> of the values on the testcase since they overflow.  However, I did not
>>> know how to modify the formats in the printfs to print the size_ts.
>>
>> The simple way is to use "unsigned long" and "%lu".
>
> Which probably doesn't work for win64 ... of course there
> isn't a portable one for size_t or long long.

I thought of that, but it does work for win64 in the sense of
operating correctly and being an improvement on what is there now.

If we really want to use size_t on win64, we should just use unsigned
HOST_WIDEST_FAST_INT, create the corresponding print macros, and
update config.host to get win64 to set
use_long_long_for_widest_fast_int.

Ian