------- 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 <zad...@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.p...@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
