[Bug tree-optimization/35805] [ira] error in start_allocno_priorities, at ira-color.c:1806

["zadeck at naturalbridge dot com" <gcc-bugzilla@gcc.gnu.org>]

------- Comment #9 from zadeck at naturalbridge dot com  2009-01-02 15:34 -------
Subject: Re:  [ira] error in start_allocno_priorities,
 at ira-color.c:1806

On looking at the code, there is an issue with the first patch.   I
should have been clearing solutions_dirty flag at the start of the
function.   However, I do not think that this is the issue that you are
complaining about.  

What this corrects is the case where the solution was dirty before the
first call to df_analyze and dce finds nothing to delete.   In that
case, the code would have redone the lr solution for no reason. 

I will test this patch, but we still need to resolve your issues with my
approach.

Kenny


zadeck at naturalbridge dot com wrote:
> ------- Comment #8 from zadeck at naturalbridge dot com  2009-01-02 15:20 -------
> Subject: Re:  [ira] error in start_allocno_priorities,
>  at ira-color.c:1806
>
> Paolo Bonzini wrote:
>   
>>> I think so.   The global changed flag allows it to delete the case:
>>>
>>> loop:
>>>  ... <- x  // This is dead.
>>>  x- <- ...
>>> go to loop
>>>
>>> it just is not going to get rid of it if there is is no kill of x inside
>>> the loop.
>>>     
>>>       
>> I just don't think it's acceptable to load each and every "fast DCE"
>> with the burden of a full df solution.  We need to find a way to limit
>> this to the cases when it is needed, or at least not to be too
>> conservative in ascertaining *when* it is needed.
>>   
>>     
> i am not, i am only doing it for each and every dce, only if the dce
> actually deletes code. 
>
> If there was a faster way to determine if the solution was too
> conservative than redoing it, you would have an effective incremental
> dataflow analysis algorithm.   I strongly believe that such a technique
> does not exist.
>   
>> Hence my first and foremost question is: does it happen that the
>> solution is wrong and global_changed never became true?
>>
>>   
>>     
> The example in the pr exhibits this property.  the problem is that
> deleting the use of pseudo 69 does not cause bit 69 to ever get turned
> off because it was live at the bottom of the loop (since it had been
> propagated around the loop to start with.)  Hence, when you get to the
> top of the loop, there are no changes at all with respect to pseudo 69
> and local_changed would not have been set.  (I do not know if it is
> really true for the example that local_changes is not set, because the
> deletion of the kill on the set side of the insn could have caused that
> to happen.  But the point is that with respect to position 69, the use
> in the deleted insn would not have caused local_changed to be set.)
>
>   
>> If the answer is "definitely no", then an alternative preferrable
>> patch would be to move the code you added to df-problems.c into dce.c,
>> so that the full analysis (including rebuilding the bitmaps and
>> iterating possibly many times) is not run if it was to yield the same
>> answer that was before in the bitmaps.
>>
>> Paolo
>>   
>>     
>
>
>   

Index: ChangeLog
===================================================================
--- ChangeLog   (revision 142954)
+++ ChangeLog   (working copy)
@@ -1,3 +1,10 @@
+2009-01-01  Kenneth Zadeck <zadeck@naturalbridge.com>
+
+       PR rtl-optimization/35805
+       * df-problems.c (df_lr_finalize): Add recursive call to resolve lr
+       problem if fast dce is able to remove any instructions.
+       * dce.c (dce_process_block): Fix dump message.
+       
 2008-12-29  Seongbae Park  <seongbae.park@gmail.com>

        * tree-profile.c (tree_init_ic_make_global_vars): Make static
Index: df-problems.c
===================================================================
--- df-problems.c       (revision 142954)
+++ df-problems.c       (working copy)
@@ -1001,25 +1001,34 @@ df_lr_transfer_function (int bb_index)
 /* Run the fast dce as a side effect of building LR.  */

 static void
-df_lr_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
+df_lr_finalize (bitmap all_blocks)
 {
+  df_lr->solutions_dirty = false;
   if (df->changeable_flags & DF_LR_RUN_DCE)
     {
       run_fast_df_dce ();
-      if (df_lr->problem_data && df_lr->solutions_dirty)
+
+      /* If dce deletes some instructions, we need to recompute the lr
+        solution before proceeding further.  The problem is that fast
+        dce is a pessimestic dataflow algorithm.  In the case where
+        it deletes a statement S inside of a loop, the uses inside of
+        S may not be deleted from the dataflow solution because they
+        were carried around the loop.  While it is conservatively
+        correct to leave these extra bits, the standards of df
+        require that we maintain the best possible (least fixed
+        point) solution.  The only way to do that is to redo the
+        iteration from the beginning.  See PR35805 for an
+        example.  */
+      if (df_lr->solutions_dirty)
        {
-         /* If we are here, then it is because we are both verifying
-         the solution and the dce changed the function.  In that case
-         the verification info built will be wrong.  So we leave the
-         dirty flag true so that the verifier will skip the checking
-         part and just clean up.*/
-         df_lr->solutions_dirty = true;
+         df_clear_flags (DF_LR_RUN_DCE);
+         df_lr_alloc (all_blocks);
+         df_lr_local_compute (all_blocks);
+         df_worklist_dataflow (df_lr, all_blocks, df->postorder,
df->n_blocks);
+         df_lr_finalize (all_blocks);
+         df_set_flags (DF_LR_RUN_DCE);
        }
-      else
-       df_lr->solutions_dirty = false;
     }
-  else
-    df_lr->solutions_dirty = false;
 }


Index: dce.c
===================================================================
--- dce.c       (revision 142954)
+++ dce.c       (working copy)
@@ -601,7 +601,7 @@ dce_process_block (basic_block bb, bool

   if (dump_file)
     {
-      fprintf (dump_file, "processing block %d live out = ", bb->index);
+      fprintf (dump_file, "processing block %d lr out = ", bb->index);
       df_print_regset (dump_file, DF_LR_OUT (bb));
     }



-- 


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