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

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

[mstein dot lists at googlemail dot com]

Hi,
gcc  930523-1.c -c -fira -O1 -m32
fails with
930523-1.c: In function 'f':
930523-1.c:54: internal compiler error: in start_allocno_priorities, at
ira-color.c:1806
Please submit a full bug report,

rev: 133765


-- 
           Summary: [ira] error in start_allocno_priorities, at ira-
                    color.c:1806
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: mstein dot lists at googlemail dot com
GCC target triplet: i386


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

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

[vmakarov at redhat dot com]

------- Comment #1 from vmakarov at redhat dot com  2008-04-02 18:34 -------
I've just fixed it on ira branch.  The problem was in an assert requiring
nonzero number of references for an allocno.  I permitted to have zero number
of references.

I've just realized that such situations are possible in a region but something
is wrong with this particular case.  The pseudo-register 69 lives at the
start/end of each basic block there is no such pseduo-register in RTL.  It is
removed in ce2.  Either the live info was not updated or something wrong with
the updating itself.

Therefore I am not closing IRA and I am adding Ken to the list.  I think the
problem can be reproduced on the mainline because I've merged the trunk into
the branch recently.


-- 

vmakarov at redhat dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |Kenneth dot Zadeck at
                   |                            |NaturalBridge dot com


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

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

[reichelt at gcc dot gnu dot org]

------- Comment #2 from reichelt at gcc dot gnu dot org  2008-12-29 22:37 -------
What's the status of this bug?
If it's not an IRA related problem as comment #1 suggests,
then the summary should be updated accordingly.


-- 

reichelt at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |reichelt at gcc dot gnu dot
                   |                            |org


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

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

[zadeck at naturalbridge dot com]

------- Comment #3 from zadeck at naturalbridge dot com  2008-12-29 23:40 -------
additional info.

gcc.c-torture/compile/930523-1.c

on x86-32.


-- 


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

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

[zadeck at naturalbridge dot com]

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

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.

This patch fixes the problem.  The comment in the patch describes the
issue.    Since this was not really a failure, it would be hard to make
this issue into a testcase.

Ok to commit?

Bootstrapped and regression tested on x86*.

Kenny
Index: df-problems.c
===================================================================
--- df-problems.c       (revision 142954)
+++ df-problems.c       (working copy)
@@ -1001,22 +1001,32 @@ 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)
 {
   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

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

[bonzini at gnu dot org]

------- Comment #5 from bonzini at gnu dot org  2009-01-02 08:17 -------
Subject: Re:  [ira] error in start_allocno_priorities,
 at ira-color.c:1806

Kenneth Zadeck wrote:
> 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.
>    
> This patch fixes the problem.  The comment in the patch describes the
> issue.    Since this was not really a failure, it would be hard to make
> this issue into a testcase.

IIUC the bugzilla comment trail, this caused
gcc.c-torture/compile/930523-1.c to fail with --enable-checking=df;
that's already a testcase.

> Ok to commit?

Hmmm... I am not sure I like this patch, for two reasons.

1) it might incur a compile-time penalty for the sake of verification,
even with df checking disabled.  OTOH having possibly different code for
checking and non-checking compilation is even worse.

2) there are already provisions in dce.c to redo the analysis.  But they
do not get to the least fixed point because they just rebuild the local
bitmaps and iterate from the existing solution.  Instead of iterating
"while (global_changed)", we could try doing only one iteration (it's a
fast DCE after all, and the pessimistic dataflow makes me guess that
subsequent DCE iterations won't find much?) and zap the solution there.
 This has the advantage that we can skip the recomputation if
global_changed is false.

Did I miss anything?

Paolo


-- 


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

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

[zadeck at naturalbridge dot com]

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

Paolo Bonzini wrote:
> Kenneth Zadeck wrote:
>   
>> 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.
>>    
>> This patch fixes the problem.  The comment in the patch describes the
>> issue.    Since this was not really a failure, it would be hard to make
>> this issue into a testcase.
>>     
>
> IIUC the bugzilla comment trail, this caused
> gcc.c-torture/compile/930523-1.c to fail with --enable-checking=df;
> that's already a testcase.
>
>   
>> Ok to commit?
>>     
>
> Hmmm... I am not sure I like this patch, for two reasons.
>
> 1) it might incur a compile-time penalty for the sake of verification,
> even with df checking disabled.  OTOH having possibly different code for
> checking and non-checking compilation is even worse.
>
>   
There is a compile time penalty here but it is not for the sake of
verification.   It is for the sake of getting the best answer going
forward, into the computation of live.

There was a deeper bug here.   The code that was removed which cleared
the solutions_dirty flag is really wrong, because it lets the
conservative solution go forward and the next call to df_analyze will
not even try to redo anything and thus improve the solution. That was
how vlad saw the extra bits even though he was calling df_analyze before
using the bits.

 On the other hand, if you do not clear that flag in the old way, the
verifier will fail.
> 2) there are already provisions in dce.c to redo the analysis.  But they
> do not get to the least fixed point because they just rebuild the local
> bitmaps and iterate from the existing solution.  Instead of iterating
> "while (global_changed)", we could try doing only one iteration (it's a
> fast DCE after all, and the pessimistic dataflow makes me guess that
> subsequent DCE iterations won't find much?) and zap the solution there.
>  This has the advantage that we can skip the recomputation if
> global_changed is false.
>
> Did I miss anything?
>
>   
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.

Anyway. the loop inside the fast dce code will only cause one extra
iteration of the blocks, and because of that it is still pessimistic.
>   


> Paolo
>   


-- 


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

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

[bonzini at gnu dot org]

------- Comment #7 from bonzini at gnu dot org  2009-01-02 14:26 -------
Subject: Re:  [ira] error in start_allocno_priorities, at ira-color.c:1806

> 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.

Hence my first and foremost question is: does it happen that the
solution is wrong and global_changed never became true?

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


-- 


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

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

[zadeck at naturalbridge dot com]

------- 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
>   


-- 


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

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

[zadeck at naturalbridge dot com]

------- 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

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

[bonzini at gnu dot org]

------- Comment #10 from bonzini at gnu dot org  2009-01-02 16:33 -------
Subject: Re:  [ira] error in start_allocno_priorities,
  at ira-color.c:1806

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

The problem is that you're really doubling the cost of computing the
live registers.  I know that previously it was wrong, but at this point
there's no difference with the full-blown pass...  Despite the idea of
DF_LR_RUN_DCE being that it was "free", now it would do the same work as
a pass_fast_rtl_dce modulo some O(#bbs) work.

At this point, if your patch costs say 0.3%, and removing all traces of
DF_LR_RUN_DCE (instead scheduling a dozen more pass_fast_rtl_dce in
passes.c) costs 0.5%, I'd rather see the latter, at least it's easier to
look for opportunities to remove some useless DCE.

If it wasn't for verification, we could just decide that DF_LR_RUN_DCE
is only for passes that can tolerate a little inaccurate info...

Paolo


-- 


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

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

[zadeck at naturalbridge dot com]

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

Paolo Bonzini wrote:
>> I will test this patch, but we still need to resolve your issues with my
>> approach.
>>     
>
> The problem is that you're really doubling the cost of computing the
> live registers.  I know that previously it was wrong, but at this point
> there's no difference with the full-blown pass...  Despite the idea of
> DF_LR_RUN_DCE being that it was "free", now it would do the same work as
> a pass_fast_rtl_dce modulo some O(#bbs) work.
>   
you are being too pessimistic.  most of the time, dce finds nothing.  
If DCE finds nothing, then the second pass does not run.

I considered just fixing the verification part (not clearing the
solutions_dirty flag) and letting the next call to df_analyze clean
things up.  In this way it would be like every other pass and leave
things dirty until the next pass that needed the info. 

StevenB talked me out of this because he considered it wrong to have the
client pass get conservative info.  I agreed with him but I am willing
to change my mind if you really want to push your case.  

> At this point, if your patch costs say 0.3%, and removing all traces of
> DF_LR_RUN_DCE (instead scheduling a dozen more pass_fast_rtl_dce in
> passes.c) costs 0.5%, I'd rather see the latter, at least it's easier to
> look for opportunities to remove some useless DCE.
>
> If it wasn't for verification, we could just decide that DF_LR_RUN_DCE
> is only for passes that can tolerate a little inaccurate info...
>
>   
This was in fact my argument to stevenb.  The point is that the live
info which is run after it will generally hide this conservativeness. 
On the other hand we do have standards that we always use the best info
.... As i pointed out on irc, the only reason that vlad noticed this at
all was that he uses the wrong sets in his code (and he was running at
O1 in this case.)  At O2 and above he should be using the DF_LIVE sets.

Kenny

> Paolo
>   


-- 


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

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

[bonzini at gnu dot org]

------- Comment #12 from bonzini at gnu dot org  2009-01-02 18:38 -------
Subject: Re:  [ira] error in start_allocno_priorities,
 at ira-color.c:1806


> StevenB talked me out of this because he considered it wrong to have
> the client pass get conservative info.  I agreed with him but I am
> willing to change my mind if you really want to push your case.

If there was preexisting discussion outside bugzilla, it's of course
okay for me, and I'll not push my opinion beyond, but I'd still like to
see some numbers.  You can commit the second patch either before or
after, I don't care.

>> At this point, if your patch costs say 0.3%, and removing all traces 
>> DF_LR_RUN_DCE (instead scheduling a dozen more pass_fast_rtl_dce in
>> passes.c) costs 0.5%, I'd rather see the latter, at least it's easier to
>> look for opportunities to remove some useless DCE.

I'll try to do this for 4.5.

Paolo


-- 


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

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

[stevenb dot gcc at gmail dot com]

------- Comment #13 from stevenb dot gcc at gmail dot com  2009-01-02 18:45 -------
Subject: Re:  [ira] error in start_allocno_priorities, at ira-color.c:1806

On Fri, Jan 2, 2009 at 7:37 PM, Paolo Bonzini <bonzini@gnu.org> wrote:
>>> At this point, if your patch costs say 0.3%, and removing all traces
>>> DF_LR_RUN_DCE (instead scheduling a dozen more pass_fast_rtl_dce in
>>> passes.c) costs 0.5%, I'd rather see the latter, at least it's easier to
>>> look for opportunities to remove some useless DCE.
>
> I'll try to do this for 4.5.

It might be more worthwhile to just "fix" IRA to use DF_LIVE (which
Vlad should have done in the first place). Then we wouldn't need
Kenny's patch and DF_LR_RUN_DCE would still be essentially free.

Gr.
Steven


-- 


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

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

[zadeck at naturalbridge dot com]

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

Steven Bosscher wrote:
> On Fri, Jan 2, 2009 at 7:37 PM, Paolo Bonzini <bonzini@gnu.org> wrote:
>   
>>>> At this point, if your patch costs say 0.3%, and removing all traces
>>>> DF_LR_RUN_DCE (instead scheduling a dozen more pass_fast_rtl_dce in
>>>> passes.c) costs 0.5%, I'd rather see the latter, at least it's easier to
>>>> look for opportunities to remove some useless DCE.
>>>>         
>> I'll try to do this for 4.5.
>>     
>
> It might be more worthwhile to just "fix" IRA to use DF_LIVE (which
> Vlad should have done in the first place). Then we wouldn't need
> Kenny's patch and DF_LR_RUN_DCE would still be essentially free.
>
> Gr.
> Steven
There is the issue of correctness vs rot.   I actually think that one of
the reasons that flow was so bad was that people went down this long
slippery slope of well it is good enough here ... and we really can get
away with it not being right here ... and after a while, all you have is
garbage.

The problem with this game is that it is not maintainable.   Those kinds
of decisions tend to get forgotten and lost as the personnel supporting
the compiler changes.    Even if it is a fractional percentage slower,
the fact that you do not have to reason about it as the compiler evolves
is actually quite important.  

Thus, I plan to both fix this bug and add another one for vlad to fix
the sets that he uses. 

Kenny


-- 


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

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

[zadeck at gcc dot gnu dot org]

------- Comment #15 from zadeck at gcc dot gnu dot org  2009-01-03 00:33 -------
Subject: Bug 35805

Author: zadeck
Date: Sat Jan  3 00:31:39 2009
New Revision: 143027

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=143027
Log:
2009-01-02  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.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/dce.c
    trunk/gcc/df-problems.c


-- 


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

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

[zadeck at naturalbridge dot com]

------- Comment #16 from zadeck at naturalbridge dot com  2009-01-03 00:35 -------
Subject: Re:  [ira] error in start_allocno_priorities,
 at ira-color.c:1806

Kenneth Zadeck wrote:
> Steven Bosscher wrote:
>   
>> On Fri, Jan 2, 2009 at 7:37 PM, Paolo Bonzini <bonzini@gnu.org> wrote:
>>   
>>     
>>>>> At this point, if your patch costs say 0.3%, and removing all traces
>>>>> DF_LR_RUN_DCE (instead scheduling a dozen more pass_fast_rtl_dce in
>>>>> passes.c) costs 0.5%, I'd rather see the latter, at least it's easier to
>>>>> look for opportunities to remove some useless DCE.
>>>>>         
>>>>>           
>>> I'll try to do this for 4.5.
>>>     
>>>       
>> It might be more worthwhile to just "fix" IRA to use DF_LIVE (which
>> Vlad should have done in the first place). Then we wouldn't need
>> Kenny's patch and DF_LR_RUN_DCE would still be essentially free.
>>
>> Gr.
>> Steven
>>     
> There is the issue of correctness vs rot.   I actually think that one of
> the reasons that flow was so bad was that people went down this long
> slippery slope of well it is good enough here ... and we really can get
> away with it not being right here ... and after a while, all you have is
> garbage.
>
> The problem with this game is that it is not maintainable.   Those kinds
> of decisions tend to get forgotten and lost as the personnel supporting
> the compiler changes.    Even if it is a fractional percentage slower,
> the fact that you do not have to reason about it as the compiler evolves
> is actually quite important.  
>
> Thus, I plan to both fix this bug and add another one for vlad to fix
> the sets that he uses. 
>
> Kenny
>   
2009-01-02  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.

Rebootstrapped and regression tested on x86*.

Committed as revision 143027.

Kenny
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

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

[zadeck at naturalbridge dot com]

------- Comment #17 from zadeck at naturalbridge dot com  2009-01-03 01:05 -------
patch committed to fix this.


-- 

zadeck at naturalbridge dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |FIXED


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

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

[hjl dot tools at gmail dot com]

------- Comment #18 from hjl dot tools at gmail dot com  2009-01-04 18:23 -------
Subject: Re:  [ira] error in start_allocno_priorities, at ira-color.c:1806

On Fri, Jan 2, 2009 at 4:34 PM, Kenneth Zadeck <zadeck@naturalbridge.com>
wrote:
> Kenneth Zadeck wrote:
>> Steven Bosscher wrote:
>>
>>> On Fri, Jan 2, 2009 at 7:37 PM, Paolo Bonzini <bonzini@gnu.org> wrote:
>>>
>>>
>>>>>> At this point, if your patch costs say 0.3%, and removing all traces
>>>>>> DF_LR_RUN_DCE (instead scheduling a dozen more pass_fast_rtl_dce in
>>>>>> passes.c) costs 0.5%, I'd rather see the latter, at least it's easier to
>>>>>> look for opportunities to remove some useless DCE.
>>>>>>
>>>>>>
>>>> I'll try to do this for 4.5.
>>>>
>>>>
>>> It might be more worthwhile to just "fix" IRA to use DF_LIVE (which
>>> Vlad should have done in the first place). Then we wouldn't need
>>> Kenny's patch and DF_LR_RUN_DCE would still be essentially free.
>>>
>>> Gr.
>>> Steven
>>>
>> There is the issue of correctness vs rot.   I actually think that one of
>> the reasons that flow was so bad was that people went down this long
>> slippery slope of well it is good enough here ... and we really can get
>> away with it not being right here ... and after a while, all you have is
>> garbage.
>>
>> The problem with this game is that it is not maintainable.   Those kinds
>> of decisions tend to get forgotten and lost as the personnel supporting
>> the compiler changes.    Even if it is a fractional percentage slower,
>> the fact that you do not have to reason about it as the compiler evolves
>> is actually quite important.
>>
>> Thus, I plan to both fix this bug and add another one for vlad to fix
>> the sets that he uses.
>>
>> Kenny
>>
> 2009-01-02  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.
>
> Rebootstrapped and regression tested on x86*.
>
> Committed as revision 143027.
>

Hi,

This caused:

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


-- 


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