Move df_live and df_md bitmaps to own obstacks

Move df_live and df_md bitmaps to own obstacks

[Jan Hubicka]

Hi,
this patch moves df_live and df_md bitmaps to own obstacks.  I believe those
are all important df problems that depends on bitmap performance?

Bootstrapped/regtested x86_64-linux (with df checking)
OK?

Honza

	* df-problems.c (df_live_problem_data): Add live_bitmaps.
	(df_live_alloc): Initialize problem data and live_osbtacks.
	(df_live_finalize): Remove obstack, problem data; do not
	clear all bitmaps.
	(df_live_top_dump, df_live_bottom_dump): Do not dump old
	data when not allocated.
	(df_live_verify_solution_start): Do not allocate problem data.
	(df_live_verify_solution_end): Check if out is allocated.
	(struct df_md_problem_data): New structure.
	(df_md_alloc): Allocate problem data.
	(df_md_free): Free problem data; do not clear bitmaps.

Index: df-problems.c
===================================================================
--- df-problems.c	(revision 160501)
+++ df-problems.c	(working copy)
@@ -1361,6 +1361,8 @@ struct df_live_problem_data
 {
   bitmap_head *in;
   bitmap_head *out;
+  /* An obstack for the bitmaps we need for this problem.  */
+  bitmap_obstack live_bitmaps;
 };
 
 /* Scratch var used by transfer functions.  This is used to implement
@@ -1406,12 +1408,24 @@ df_live_alloc (bitmap all_blocks ATTRIBU
 {
   unsigned int bb_index;
   bitmap_iterator bi;
+  struct df_live_problem_data *problem_data;
 
   if (!df_live->block_pool)
     df_live->block_pool = create_alloc_pool ("df_live_block pool",
 					   sizeof (struct df_live_bb_info), 100);
+  if (df_live->problem_data)
+    problem_data = (struct df_live_problem_data *) df_live->problem_data;
+  else
+    {
+      problem_data = XNEW (struct df_live_problem_data);
+      df_live->problem_data = problem_data;
+
+      problem_data->out = NULL;
+      problem_data->in = NULL;
+      bitmap_obstack_initialize (&problem_data->live_bitmaps);
+    }
   if (!df_live_scratch)
-    df_live_scratch = BITMAP_ALLOC (NULL);
+    df_live_scratch = BITMAP_ALLOC (&problem_data->live_bitmaps);
 
   df_grow_bb_info (df_live);
 
@@ -1427,10 +1441,10 @@ df_live_alloc (bitmap all_blocks ATTRIBU
 	{
 	  bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
 	  df_live_set_bb_info (bb_index, bb_info);
-	  bitmap_initialize (&bb_info->kill, &bitmap_default_obstack);
-	  bitmap_initialize (&bb_info->gen, &bitmap_default_obstack);
-	  bitmap_initialize (&bb_info->in, &bitmap_default_obstack);
-	  bitmap_initialize (&bb_info->out, &bitmap_default_obstack);
+	  bitmap_initialize (&bb_info->kill, &problem_data->live_bitmaps);
+	  bitmap_initialize (&bb_info->gen, &problem_data->live_bitmaps);
+	  bitmap_initialize (&bb_info->in, &problem_data->live_bitmaps);
+	  bitmap_initialize (&bb_info->out, &problem_data->live_bitmaps);
 	}
     }
   df_live->optional_p = (optimize <= 1);
@@ -1622,25 +1636,14 @@ df_live_finalize (bitmap all_blocks)
 static void
 df_live_free (void)
 {
+  struct df_live_problem_data *problem_data
+    = (struct df_live_problem_data *) df_live->problem_data;
   if (df_live->block_info)
     {
-      unsigned int i;
-
-      for (i = 0; i < df_live->block_info_size; i++)
-	{
-	  struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
-	  if (bb_info)
-	    {
-	      bitmap_clear (&bb_info->gen);
-	      bitmap_clear (&bb_info->kill);
-	      bitmap_clear (&bb_info->in);
-	      bitmap_clear (&bb_info->out);
-	    }
-	}
-
       free_alloc_pool (df_live->block_pool);
       df_live->block_info_size = 0;
       free (df_live->block_info);
+      bitmap_obstack_release (&problem_data->live_bitmaps);
 
       if (df_live_scratch)
 	BITMAP_FREE (df_live_scratch);
@@ -1666,8 +1669,11 @@ df_live_top_dump (basic_block bb, FILE *
   if (df_live->problem_data)
     {
       problem_data = (struct df_live_problem_data *)df_live->problem_data;
-      fprintf (file, ";;  old in  \t");
-      df_print_regset (file, &problem_data->in[bb->index]);
+      if (problem_data->in)
+	{
+	  fprintf (file, ";;  old in  \t");
+	  df_print_regset (file, &problem_data->in[bb->index]);
+	}
     }
   fprintf (file, ";; live  gen \t");
   df_print_regset (file, &bb_info->gen);
@@ -1692,8 +1698,11 @@ df_live_bottom_dump (basic_block bb, FIL
   if (df_live->problem_data)
     {
       problem_data = (struct df_live_problem_data *)df_live->problem_data;
-      fprintf (file, ";;  old out  \t");
-      df_print_regset (file, &problem_data->out[bb->index]);
+      if (problem_data->out)
+	{
+	  fprintf (file, ";;  old out  \t");
+	  df_print_regset (file, &problem_data->out[bb->index]);
+	}
     }
 }
 
@@ -1707,23 +1716,19 @@ df_live_verify_solution_start (void)
   basic_block bb;
   struct df_live_problem_data *problem_data;
   if (df_live->solutions_dirty)
-    {
-      df_live->problem_data = NULL;
-      return;
-    }
+    return;
 
   /* Set it true so that the solution is recomputed.  */
   df_live->solutions_dirty = true;
 
-  problem_data = XNEW (struct df_live_problem_data);
-  df_live->problem_data = problem_data;
+  problem_data = (struct df_live_problem_data *)df_live->problem_data;
   problem_data->in = XNEWVEC (bitmap_head, last_basic_block);
   problem_data->out = XNEWVEC (bitmap_head, last_basic_block);
 
   FOR_ALL_BB (bb)
     {
-      bitmap_initialize (&problem_data->in[bb->index], &bitmap_default_obstack);
-      bitmap_initialize (&problem_data->out[bb->index], &bitmap_default_obstack);
+      bitmap_initialize (&problem_data->in[bb->index], &problem_data->live_bitmaps);
+      bitmap_initialize (&problem_data->out[bb->index], &problem_data->live_bitmaps);
       bitmap_copy (&problem_data->in[bb->index], DF_LIVE_IN (bb));
       bitmap_copy (&problem_data->out[bb->index], DF_LIVE_OUT (bb));
     }
@@ -1739,10 +1744,9 @@ df_live_verify_solution_end (void)
   struct df_live_problem_data *problem_data;
   basic_block bb;
 
-  if (df_live->problem_data == NULL)
-    return;
-
   problem_data = (struct df_live_problem_data *)df_live->problem_data;
+  if (!problem_data->out)
+    return;
 
   FOR_ALL_BB (bb)
     {
@@ -4199,6 +4203,13 @@ df_simulate_one_insn_forwards (basic_blo
     propagating the information to BB3's successors.
    ---------------------------------------------------------------------------*/
 
+/* Private data used to verify the solution for this problem.  */
+struct df_md_problem_data
+{
+  /* An obstack for the bitmaps we need for this problem.  */
+  bitmap_obstack md_bitmaps;
+};
+
 /* Scratch var used by transfer functions.  This is used to do md analysis
    only for live registers.  */
 static bitmap_head df_md_scratch;
@@ -4240,13 +4251,22 @@ df_md_alloc (bitmap all_blocks)
 {
   unsigned int bb_index;
   bitmap_iterator bi;
+  struct df_md_problem_data *problem_data;
 
   if (!df_md->block_pool)
     df_md->block_pool = create_alloc_pool ("df_md_block pool",
                                            sizeof (struct df_md_bb_info), 50);
 
   df_grow_bb_info (df_md);
-  bitmap_initialize (&df_md_scratch, &bitmap_default_obstack);
+  if (df_md->problem_data)
+    problem_data = (struct df_md_problem_data *) df_md->problem_data;
+  else
+    {
+      problem_data = XNEW (struct df_md_problem_data);
+      df_md->problem_data = problem_data;
+      bitmap_obstack_initialize (&problem_data->md_bitmaps);
+    }
+  bitmap_initialize (&df_md_scratch, &problem_data->md_bitmaps);
 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {
@@ -4263,11 +4283,11 @@ df_md_alloc (bitmap all_blocks)
         {
           bb_info = (struct df_md_bb_info *) pool_alloc (df_md->block_pool);
           df_md_set_bb_info (bb_index, bb_info);
-	  bitmap_initialize (&bb_info->init, &bitmap_default_obstack);
-	  bitmap_initialize (&bb_info->gen, &bitmap_default_obstack);
-	  bitmap_initialize (&bb_info->kill, &bitmap_default_obstack);
-	  bitmap_initialize (&bb_info->in, &bitmap_default_obstack);
-	  bitmap_initialize (&bb_info->out, &bitmap_default_obstack);
+	  bitmap_initialize (&bb_info->init, &problem_data->md_bitmaps);
+	  bitmap_initialize (&bb_info->gen, &problem_data->md_bitmaps);
+	  bitmap_initialize (&bb_info->kill, &problem_data->md_bitmaps);
+	  bitmap_initialize (&bb_info->in, &problem_data->md_bitmaps);
+	  bitmap_initialize (&bb_info->out, &problem_data->md_bitmaps);
         }
     }
 
@@ -4520,21 +4540,10 @@ df_md_confluence_n (edge e)
 static void
 df_md_free (void)
 {
-  unsigned int i;
-  for (i = 0; i < df_md->block_info_size; i++)
-    {
-      struct df_md_bb_info *bb_info = df_md_get_bb_info (i);
-      if (bb_info)
-	{
-	  bitmap_clear (&bb_info->kill);
-	  bitmap_clear (&bb_info->gen);
-	  bitmap_clear (&bb_info->init);
-	  bitmap_clear (&bb_info->in);
-	  bitmap_clear (&bb_info->out);
-	}
-    }
+  struct df_md_problem_data *problem_data
+    = (struct df_md_problem_data *) df_md->problem_data;
 
-  bitmap_clear (&df_md_scratch);
+  bitmap_obstack_release (&problem_data->md_bitmaps);
   free_alloc_pool (df_md->block_pool);
 
   df_md->block_info_size = 0;

Re: Move df_live and df_md bitmaps to own obstacks

[Paolo Bonzini]

On 06/10/2010 01:35 PM, Jan Hubicka wrote:
> Hi,
> this patch moves df_live and df_md bitmaps to own obstacks.  I believe those
> are all important df problems that depends on bitmap performance?
>
> Bootstrapped/regtested x86_64-linux (with df checking)
> OK?

Cool, please commit.

Paolo

Re: Move df_live and df_md bitmaps to own obstacks

[H.J. Lu]

On Thu, Jun 10, 2010 at 4:35 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
> Hi,
> this patch moves df_live and df_md bitmaps to own obstacks.  I believe those
> are all important df problems that depends on bitmap performance?
>
> Bootstrapped/regtested x86_64-linux (with df checking)
> OK?
>
> Honza
>
>        * df-problems.c (df_live_problem_data): Add live_bitmaps.
>        (df_live_alloc): Initialize problem data and live_osbtacks.
>        (df_live_finalize): Remove obstack, problem data; do not
>        clear all bitmaps.
>        (df_live_top_dump, df_live_bottom_dump): Do not dump old
>        data when not allocated.
>        (df_live_verify_solution_start): Do not allocate problem data.
>        (df_live_verify_solution_end): Check if out is allocated.
>        (struct df_md_problem_data): New structure.
>        (df_md_alloc): Allocate problem data.
>        (df_md_free): Free problem data; do not clear bitmaps.
>

This caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44498

-- 
H.J.

Re: Move df_live and df_md bitmaps to own obstacks

[H.J. Lu]

On Thu, Jun 10, 2010 at 3:41 PM, H.J. Lu <hjl.tools@gmail.com> wrote:
> On Thu, Jun 10, 2010 at 4:35 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> Hi,
>> this patch moves df_live and df_md bitmaps to own obstacks.  I believe those
>> are all important df problems that depends on bitmap performance?
>>
>> Bootstrapped/regtested x86_64-linux (with df checking)
>> OK?
>>
>> Honza
>>
>>        * df-problems.c (df_live_problem_data): Add live_bitmaps.
>>        (df_live_alloc): Initialize problem data and live_osbtacks.
>>        (df_live_finalize): Remove obstack, problem data; do not
>>        clear all bitmaps.
>>        (df_live_top_dump, df_live_bottom_dump): Do not dump old
>>        data when not allocated.
>>        (df_live_verify_solution_start): Do not allocate problem data.
>>        (df_live_verify_solution_end): Check if out is allocated.
>>        (struct df_md_problem_data): New structure.
>>        (df_md_alloc): Allocate problem data.
>>        (df_md_free): Free problem data; do not clear bitmaps.
>>
>
> This caused:
>
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44498
>

We have


   if (!df_live_scratch)
-    df_live_scratch = BITMAP_ALLOC (NULL);
+    df_live_scratch = BITMAP_ALLOC (&problem_data->live_bitmaps);
...
+      bitmap_obstack_release (&problem_data->live_bitmaps);

       if (df_live_scratch)
        BITMAP_FREE (df_live_scratch);

We are calling bitmap_obstack_free after bitmap_obstack_release is called. Does
this patch make any senses?


Index: df-problems.c
===================================================================
--- df-problems.c	(revision 160549)
+++ df-problems.c	(working copy)
@@ -1645,8 +1645,8 @@ df_live_free (void)
       free (df_live->block_info);
       bitmap_obstack_release (&problem_data->live_bitmaps);

-      if (df_live_scratch)
-	BITMAP_FREE (df_live_scratch);
+      /* df_live_scratch is allocated from problem_data->live_bitmaps.  */
+      df_live_scratch = (bitmap) NULL;
     }
   BITMAP_FREE (df_live->out_of_date_transfer_functions);
   free (df_live);


-- 
H.J.

Re: Move df_live and df_md bitmaps to own obstacks

[Jakub Jelinek]

On Thu, Jun 10, 2010 at 04:23:07PM -0700, H.J. Lu wrote:
> We have
> 
> 
>    if (!df_live_scratch)
> -    df_live_scratch = BITMAP_ALLOC (NULL);
> +    df_live_scratch = BITMAP_ALLOC (&problem_data->live_bitmaps);
> ...
> +      bitmap_obstack_release (&problem_data->live_bitmaps);
> 
>        if (df_live_scratch)
>         BITMAP_FREE (df_live_scratch);
> 
> We are calling bitmap_obstack_free after bitmap_obstack_release is called. Does
> this patch make any senses?
> 
> 
> Index: df-problems.c
> ===================================================================
> --- df-problems.c	(revision 160549)
> +++ df-problems.c	(working copy)
> @@ -1645,8 +1645,8 @@ df_live_free (void)
>        free (df_live->block_info);
>        bitmap_obstack_release (&problem_data->live_bitmaps);
> 
> -      if (df_live_scratch)
> -	BITMAP_FREE (df_live_scratch);
> +      /* df_live_scratch is allocated from problem_data->live_bitmaps.  */
> +      df_live_scratch = (bitmap) NULL;

Wouldn't it be better to move that
if (df_live_scratch)
  BITMAP_FREE (df_live_scratch);
before bitmap_obstack_release?  BITMAP_FREE is pretty cheap operation
and if you don't do it, the statistics won't be updated.

	Jakub

Re: Move df_live and df_md bitmaps to own obstacks

[Paolo Bonzini]

>> Index: df-problems.c
>> ===================================================================
>> --- df-problems.c     (revision 160549)
>> +++ df-problems.c     (working copy)
>> @@ -1645,8 +1645,8 @@ df_live_free (void)
>>        free (df_live->block_info);
>>        bitmap_obstack_release (&problem_data->live_bitmaps);
>>
>> -      if (df_live_scratch)
>> -     BITMAP_FREE (df_live_scratch);
>> +      /* df_live_scratch is allocated from problem_data->live_bitmaps.  */
>> +      df_live_scratch = (bitmap) NULL;
>
> Wouldn't it be better to move that
> if (df_live_scratch)
>  BITMAP_FREE (df_live_scratch);
> before bitmap_obstack_release?  BITMAP_FREE is pretty cheap operation
> and if you don't do it, the statistics won't be updated.

Yes.  Both patches make sense, but Jakub's is better.

Paolo

Re: Move df_live and df_md bitmaps to own obstacks

[Jan Hubicka]

Oops,
I also noticed yesterday that i forgot to free problem_data structures.  I am
testing the following patch and will commit as obvious if it passes.

	* df-problems.c (df_live_free, df_md_free): Free properly the scratch
	bitmaps and free problem_data structure.
Index: df-problems.c
===================================================================
--- df-problems.c	(revision 160555)
+++ df-problems.c	(working copy)
@@ -1643,10 +1643,11 @@ df_live_free (void)
       free_alloc_pool (df_live->block_pool);
       df_live->block_info_size = 0;
       free (df_live->block_info);
-      bitmap_obstack_release (&problem_data->live_bitmaps);
-
       if (df_live_scratch)
 	BITMAP_FREE (df_live_scratch);
+      bitmap_obstack_release (&problem_data->live_bitmaps);
+      free (problem_data);
+      df_live->problem_data = NULL;
     }
   BITMAP_FREE (df_live->out_of_date_transfer_functions);
   free (df_live);
@@ -4543,8 +4544,12 @@ df_md_free (void)
   struct df_md_problem_data *problem_data
     = (struct df_md_problem_data *) df_md->problem_data;
 
+  if (df_md_scratch)
+    BITMAP_FREE (df_md_scratch);
   bitmap_obstack_release (&problem_data->md_bitmaps);
   free_alloc_pool (df_md->block_pool);
+  free (problem_data);
+  df_md->problem_data = NULL;
 
   df_md->block_info_size = 0;
   free (df_md->block_info);

Re: Move df_live and df_md bitmaps to own obstacks

[Jan Hubicka]

Hi,
this is version I finally comitted (bootstrapped/regtested x86_64-linux with df
checking)

I converted df_live_scratch to be bitmap_head, since df_md_scratch is converted
already.  Originally I stopped because df_live_alloc is testing it for non-NULL,
but this test is not needed.  THe bitmap is allocated along with problem_data
and dies with it too.

I am apologize for the breakage, will try to follow more curefully here.

The allocation in df-problems seems overcomplicated, I've run into problem
with it with flattening the datastructures too.  I will post separate mail on
this.

Honza

	* df-problems.c (df_live_scratch): Convert to bitmap_head.
	(df_live_alloc): Initialize df_live_scratch when initializing
	problem_data.
	(df_live_transfer_function): Update uses of df_live_scratch.
	(df_live_free): Free problem_data; clear df_live_scratch before
	releasing the obstack.
	(df_md_free): Free problem data.
Index: df-problems.c
===================================================================
--- df-problems.c	(revision 160555)
+++ df-problems.c	(working copy)
@@ -1368,7 +1368,7 @@ struct df_live_problem_data
 /* Scratch var used by transfer functions.  This is used to implement
    an optimization to reduce the amount of space used to compute the
    combined lr and live analysis.  */
-static bitmap df_live_scratch;
+static bitmap_head df_live_scratch;
 
 /* Set basic block info.  */
 
@@ -1423,9 +1423,8 @@ df_live_alloc (bitmap all_blocks ATTRIBU
       problem_data->out = NULL;
       problem_data->in = NULL;
       bitmap_obstack_initialize (&problem_data->live_bitmaps);
+      bitmap_initialize (&df_live_scratch, &problem_data->live_bitmaps);
     }
-  if (!df_live_scratch)
-    df_live_scratch = BITMAP_ALLOC (&problem_data->live_bitmaps);
 
   df_grow_bb_info (df_live);
 
@@ -1595,12 +1594,12 @@ df_live_transfer_function (int bb_index)
   /* We need to use a scratch set here so that the value returned from this
      function invocation properly reflects whether the sets changed in a
      significant way; i.e. not just because the lr set was anded in.  */
-  bitmap_and (df_live_scratch, gen, &bb_lr_info->out);
+  bitmap_and (&df_live_scratch, gen, &bb_lr_info->out);
   /* No register may reach a location where it is not used.  Thus
      we trim the rr result to the places where it is used.  */
   bitmap_and_into (in, &bb_lr_info->in);
 
-  return bitmap_ior_and_compl (out, df_live_scratch, in, kill);
+  return bitmap_ior_and_compl (out, &df_live_scratch, in, kill);
 }
 
 
@@ -1643,10 +1642,10 @@ df_live_free (void)
       free_alloc_pool (df_live->block_pool);
       df_live->block_info_size = 0;
       free (df_live->block_info);
+      bitmap_clear (&df_live_scratch);
       bitmap_obstack_release (&problem_data->live_bitmaps);
-
-      if (df_live_scratch)
-	BITMAP_FREE (df_live_scratch);
+      free (problem_data);
+      df_live->problem_data = NULL;
     }
   BITMAP_FREE (df_live->out_of_date_transfer_functions);
   free (df_live);
@@ -4545,6 +4544,8 @@ df_md_free (void)
 
   bitmap_obstack_release (&problem_data->md_bitmaps);
   free_alloc_pool (df_md->block_pool);
+  free (problem_data);
+  df_md->problem_data = NULL;
 
   df_md->block_info_size = 0;
   free (df_md->block_info);