Hi Richard!
On 2024-06-28T17:48:30+0100, Richard Sandiford <richard.sandif...@arm.com>
wrote:
> Richard Sandiford <richard.sandif...@arm.com> writes:
>> Thomas Schwinge <tschwi...@baylibre.com> writes:
>>> On 2024-06-27T23:20:18+0200, I wrote:
>>>> On 2024-06-27T22:27:21+0200, I wrote:
>>>>> On 2024-06-27T18:49:17+0200, I wrote:
>>>>>> On 2023-10-24T19:49:10+0100, Richard Sandiford
>>>>>> <richard.sandif...@arm.com> wrote:
>>>>>>> This patch adds a combine pass that runs late in the pipeline.
>>>>>
>>>>> [After sending, I realized I replied to a previous thread of this work.]
>>>>>
>>>>>> I've beek looking a bit through recent nvptx target code generation
>>>>>> changes for GCC target libraries, and thought I'd also share here my
>>>>>> findings for the "late-combine" changes in isolation, for nvptx target.
>>>>>>
>>>>>> First the unexpected thing:
>>>>>
>>>>> So much for "unexpected thing" -- next level of unexpected here...
>>>>> Appreciated if anyone feels like helping me find my way through this, but
>>>>> I totally understand if you've got other things to do.
>>>>
>>>> OK, I found something already. (Unexpectedly quickly...) ;-)
>>>>
>>>>>> there are a few cases where we now see unused
>>>>>> registers get declared
>>>
>>>> But in fact, for both cases
>>>
>>> Now tested: 's%both%all'. :-)
>>>
>>>> the unexpected difference goes away if after
>>>> 'pass_late_combine' I inject a 'pass_fast_rtl_dce'. That's normally run
>>>> as part of 'PUSH_INSERT_PASSES_WITHIN (pass_postreload)' -- but that's
>>>> all not active for nvptx target given '!reload_completed', given nvptx is
>>>> 'targetm.no_register_allocation'. Maybe we need to enable a few more
>>>> passes, or is there anything in 'pass_late_combine' to change, so that we
>>>> don't run into this? Does it inadvertently mark registers live or
>>>> something like that?
>>>
>>> Basically, is 'pass_late_combine' potentionally doing things that depend
>>> on later clean-up? (..., or shouldn't it be doing these things in the
>>> first place?)
>>
>> It's possible that late-combine could expose dead code, but I imagine
>> it's a niche case.
>>
>> I had a look at the nvptx logs from my comparison, and the cases in
>> which I saw this seemed to be those where late-combine doesn't find
>> anything to do. Does that match your examples? Specifically,
>> the effect should be the same with -fdbg-cnt=late_combine:0-0
>>
>> I think what's happening is that:
>>
>> - combine exposes dead code
>>
>> - ce2 previously ran df_analyze with DF_LR_RUN_DCE set, and so cleared
>> up the dead code
>>
>> - late-combine instead runs df_analyze without that flag (since late-combine
>> itself doesn't really care whether dead code is present)
>>
>> - if late-combine doesn't do anything, ce2's df_analyze call has nothing
>> to do, and skips even the DCE
>>
>> The easiest fix would be to add:
>>
>> df_set_flags (DF_LR_RUN_DCE);
>>
>> before df_analyze in late-combine.cc, so that it behaves like ce2.
>> But the arrangement feels wrong. I would have expected DF_LR_RUN_DCE
>> to depend on whether df_analyze had been called since the last DCE pass
>> (whether DF_LR_RUN_DCE or a full DCE).
>
> I'm testing the attached patch to do that. I'll submit it properly if
> testing passes, but it seems to fix the extra-register problem for me.
> Give fast DCE a separate dirty flag
Thanks, and yes, your analysis makes sense to me (to the extent that I
only superficially understand these parts of GCC) -- and I confirm that
your proposed change to "Give fast DCE a separate dirty flag" does
address the issue for nvptx target.
Grüße
Thomas
> Thomas pointed out that we sometimes failed to eliminate some dead code
> (specifically clobbers of otherwise unused registers) on nvptx when
> late-combine is enabled. This happens because:
>
> - combine is able to optimise the function in a way that exposes dead code.
> This leaves the df information in a "dirty" state.
>
> - late_combine calls df_analyze without DF_LR_RUN_DCE run set.
> This updates the df information and clears the "dirty" state.
>
> - late_combine doesn't find any extra optimisations, and so leaves
> the df information up-to-date.
>
> - if_after_combine (ce2) calls df_analyze with DF_LR_RUN_DCE set.
> Because the df information is already up-to-date, fast DCE is
> not run.
>
> The upshot is that running late-combine has the effect of suppressing
> a DCE opportunity that would have been noticed without late_combine.
>
> I think this shows that we should track the state of the DCE separately
> from the LR problem. Every pass updates the latter, but not all passes
> update the former.
>
> gcc/
> * df.h (DF_LR_DCE): New df_problem_id.
> (df_lr_dce): New macro.
> * df-core.cc (rest_of_handle_df_finish): Check for a null free_fun.
> * df-problems.cc (df_lr_finalize): Split out fast DCE handling to...
> (df_lr_dce_finalize): ...this new function.
> (problem_LR_DCE): New df_problem.
> (df_lr_add_problem): Register LR_DCE rather than LR itself.
> * dce.cc (fast_dce): Clear df_lr_dce->solutions_dirty.
> ---
> gcc/dce.cc | 3 ++
> gcc/df-core.cc | 3 +-
> gcc/df-problems.cc | 96 ++++++++++++++++++++++++++++++++--------------
> gcc/df.h | 2 +
> 4 files changed, 74 insertions(+), 30 deletions(-)
>
> diff --git a/gcc/dce.cc b/gcc/dce.cc
> index be1a2a87732..04e8d98818d 100644
> --- a/gcc/dce.cc
> +++ b/gcc/dce.cc
> @@ -1182,6 +1182,9 @@ fast_dce (bool word_level)
> BITMAP_FREE (processed);
> BITMAP_FREE (redo_out);
> BITMAP_FREE (all_blocks);
> +
> + /* Both forms of DCE should make further DCE unnecessary. */
> + df_lr_dce->solutions_dirty = false;
> }
>
>
> diff --git a/gcc/df-core.cc b/gcc/df-core.cc
> index b0e8a88d433..8fd778a8618 100644
> --- a/gcc/df-core.cc
> +++ b/gcc/df-core.cc
> @@ -806,7 +806,8 @@ rest_of_handle_df_finish (void)
> for (i = 0; i < df->num_problems_defined; i++)
> {
> struct dataflow *dflow = df->problems_in_order[i];
> - dflow->problem->free_fun ();
> + if (dflow->problem->free_fun)
> + dflow->problem->free_fun ();
> }
>
> free (df->postorder);
> diff --git a/gcc/df-problems.cc b/gcc/df-problems.cc
> index 88ee0dd67fc..bfd24bd1e86 100644
> --- a/gcc/df-problems.cc
> +++ b/gcc/df-problems.cc
> @@ -1054,37 +1054,10 @@ 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)
> +df_lr_finalize (bitmap)
> {
> df_lr->solutions_dirty = false;
> - if (df->changeable_flags & DF_LR_RUN_DCE)
> - {
> - run_fast_df_dce ();
> -
> - /* 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)
> - {
> - 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);
> - }
> - }
> }
>
>
> @@ -1266,6 +1239,69 @@ static const struct df_problem problem_LR =
> false /* Reset blocks on dropping out of
> blocks_to_analyze. */
> };
>
> +/* Run the fast DCE after building LR. This is a separate problem so that
> + the "dirty" flag is only cleared after a DCE pass is actually run. */
> +
> +static void
> +df_lr_dce_finalize (bitmap all_blocks)
> +{
> + if (!(df->changeable_flags & DF_LR_RUN_DCE))
> + return;
> +
> + /* Also clears df_lr_dce->solutions_dirty. */
> + run_fast_df_dce ();
> +
> + /* 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)
> + {
> + 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);
> + }
> +}
> +
> +static const struct df_problem problem_LR_DCE
> +{
> + DF_LR_DCE, /* Problem id. */
> + DF_BACKWARD, /* Direction (arbitrary). */
> + NULL, /* Allocate the problem specific data. */
> + NULL, /* Reset global information. */
> + NULL, /* Free basic block info. */
> + NULL, /* Local compute function. */
> + NULL, /* Init the solution specific data. */
> + NULL, /* Worklist solver. */
> + NULL, /* Confluence operator 0. */
> + NULL, /* Confluence operator n. */
> + NULL, /* Transfer function. */
> + df_lr_dce_finalize, /* Finalize function. */
> + NULL, /* Free all of the problem information. */
> + NULL, /* Remove this problem from the stack of
> dataflow problems. */
> + NULL, /* Debugging. */
> + NULL, /* Debugging start block. */
> + NULL, /* Debugging end block. */
> + NULL, /* Debugging start insn. */
> + NULL, /* Debugging end insn. */
> + NULL, /* Incremental solution verify start. */
> + NULL, /* Incremental solution verify end. */
> + &problem_LR, /* Dependent problem. */
> + 0, /* Size of entry of block_info array. */
> + TV_DF_LR, /* Timing variable. */
> + false /* Reset blocks on dropping out of
> blocks_to_analyze. */
> +};
> +
>
> /* Create a new DATAFLOW instance and add it to an existing instance
> of DF. The returned structure is what is used to get at the
> @@ -1274,7 +1310,9 @@ static const struct df_problem problem_LR =
> void
> df_lr_add_problem (void)
> {
> - df_add_problem (&problem_LR);
> + /* Also add the fast DCE problem. It is then conditionally enabled by
> + the DF_LR_RUN_DCE flag. */
> + df_add_problem (&problem_LR_DCE);
> /* These will be initialized when df_scan_blocks processes each
> block. */
> df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
> diff --git a/gcc/df.h b/gcc/df.h
> index c4e690b40cf..bbb4f297b47 100644
> --- a/gcc/df.h
> +++ b/gcc/df.h
> @@ -47,6 +47,7 @@ enum df_problem_id
> {
> DF_SCAN,
> DF_LR, /* Live Registers backward. */
> + DF_LR_DCE, /* Dead code elimination post-pass for LR. */
> DF_LIVE, /* Live Registers & Uninitialized Registers */
> DF_RD, /* Reaching Defs. */
> DF_CHAIN, /* Def-Use and/or Use-Def Chains. */
> @@ -940,6 +941,7 @@ extern class df_d *df;
> #define df_scan (df->problems_by_index[DF_SCAN])
> #define df_rd (df->problems_by_index[DF_RD])
> #define df_lr (df->problems_by_index[DF_LR])
> +#define df_lr_dce (df->problems_by_index[DF_LR_DCE])
> #define df_live (df->problems_by_index[DF_LIVE])
> #define df_chain (df->problems_by_index[DF_CHAIN])
> #define df_word_lr (df->problems_by_index[DF_WORD_LR])
> --
> 2.25.1
