Re: [Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[Kenneth Zadeck <zadeck at naturalbridge dot com>]

seongbae dot park at gmail dot com wrote:
> ------- Comment #52 from seongbae dot park at gmail dot com  2008-01-17 22:31 -------
> Subject: Re:  [4.3 regression] bad interaction between DF and SJLJ exceptions
>
> I just talked to Kenny on the phone, and my suggestion is wrong
> since it changes the return value - doing my naive suggestion
> would lead to infinite loop, as the transfer function will almost always
> return true, even when the out set didn't change.
> Can you add a comment to that effect there ?
> Also please add a comment above df_live_scratch definition
> that this is an optimization to reduce memory allocation overhead
> for the scratch.
>
> Can you explain why the hunk in df_live_bb_local_compute() is correct ?
> As this seems to change what DF_REF_AT_TOP means for artificial defs...
>
> Seongbae
>
> On Jan 17, 2008 1:31 PM, Seongbae Park (¹Ú¼º¹è, ÚÓà÷ÛÆ)
> <seongbae.park@gmail.com> wrote:
>   
>> In df_live_transfer_function:
>>
>> Doesn't look like we need df_live_scratch - can't we do:
>>
>> bitmap_and (out, gen, bb_lr_info->out);
>> bitmap_and_into (in, bb_lr_info->in);
>> return bitmap_ior_and_compl_into (out, in, kill);
>>
>> ?
>>
>> Seongbae
>>
>>
>> On Jan 17, 2008 1:05 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
>>     
>>> This is the second of three patches to fix 34400.  This patch also makes
>>> some progress on 26854 but more work is required that is not going to be
>>> done in 4.3 to fix the problems here.
>>>
>>> This patch uses the output of the df_lr problem to make the df_live
>>> problem converge faster.
>>> This not only saves time but also space since the size of the df_live
>>> bitmaps never grows and the space of our bitmaps is proportional to the
>>> number of 1 bits.
>>>
>>> This has been tested on several platforms and along with the patch just
>>> committed cuts the time on the 34400 problems significantly.  I believe
>>> that this patch also has some modest improvement on bootstrap time, i.e
>>> regular programs.
>>>
>>> The change to df_live_reset is a slightly related latent bug fix.
>>>
>>> Ok to commit?
>>>
>>> Kenny
>>>
>>>
>>> 2008-01-17  Kenneth Zadeck  <zadeck@naturalbridge.com>
>>>         Steven Bosscher  <stevenb.gcc@gmail.com>
>>>
>>>     PR rtl-optimization/26854
>>>     PR rtl-optimization/34400
>>>     * df-problems.c (df_live_scratch): New scratch bitmap.
>>>     (df_live_alloc): Allocate df_live_scratch when doing df_live.
>>>     (df_live_reset): Clear the proper bitmaps.
>>>     (df_live_bb_local_compute): Only process the artificial defs once
>>>     since the order is not important.
>>>     (df_live_init): Init the df_live sets only with the variables
>>>     found live by df_lr.
>>>     (df_live_transfer_function): Use the df_lr sets to prune the
>>>     df_live sets as they are being computed.
>>>     (df_live_free): Free df_live_scratch.
>>>
>>>
>>>       
>>     
committed as revision 131649.
>> --
>> #pragma ident "Seongbae Park, compiler, http://seongbae.blogspot.com";
>>
>>     
>
>
>   

Index: df-problems.c
===================================================================
--- df-problems.c	(revision 131648)
+++ df-problems.c	(working copy)
@@ -1329,6 +1329,10 @@ struct df_live_problem_data
   bitmap *out;
 };
 
+/* 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;
 
 /* Set basic block info.  */
 
@@ -1372,6 +1376,8 @@ df_live_alloc (bitmap all_blocks ATTRIBU
   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_scratch)
+    df_live_scratch = BITMAP_ALLOC (NULL);
 
   df_grow_bb_info (df_live);
 
@@ -1407,7 +1413,7 @@ df_live_reset (bitmap all_blocks)
 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {
-      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
+      struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
       gcc_assert (bb_info);
       bitmap_clear (bb_info->in);
       bitmap_clear (bb_info->out);
@@ -1426,13 +1432,6 @@ df_live_bb_local_compute (unsigned int b
   struct df_ref **def_rec;
   int luid = 0;
 
-  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
-    {
-      struct df_ref *def = *def_rec;
-      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
-	bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
-    }
-
   FOR_BB_INSNS (bb, insn)
     {
       unsigned int uid = INSN_UID (insn);
@@ -1473,8 +1472,7 @@ df_live_bb_local_compute (unsigned int b
   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
     {
       struct df_ref *def = *def_rec;
-      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
-	bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
+      bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
     }
 }
 
@@ -1510,8 +1508,11 @@ df_live_init (bitmap all_blocks)
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {
       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
+      struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
 
-      bitmap_copy (bb_info->out, bb_info->gen);
+      /* 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 (bb_info->out, bb_info->gen, bb_lr_info->out);
       bitmap_clear (bb_info->in);
     }
 }
@@ -1537,12 +1538,22 @@ static bool
 df_live_transfer_function (int bb_index)
 {
   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
+  struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
   bitmap in = bb_info->in;
   bitmap out = bb_info->out;
   bitmap gen = bb_info->gen;
   bitmap kill = bb_info->kill;
 
-  return bitmap_ior_and_compl (out, gen, in, kill);
+  /* We need to use a scratch set here so that the value returned from
+     this function invocation properly reflects if 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);
+  /* 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);
 }
 
 
@@ -1597,6 +1608,9 @@ df_live_free (void)
       free_alloc_pool (df_live->block_pool);
       df_live->block_info_size = 0;
       free (df_live->block_info);
+
+      if (df_live_scratch)
+	BITMAP_FREE (df_live_scratch);
     }
   BITMAP_FREE (df_live->out_of_date_transfer_functions);
   free (df_live);