Re: [00/23] Make fwprop use an on-the-side RTL SSA representation

[Richard Sandiford <richard.sandiford@arm.com>]

Jeff Law <law@redhat.com> writes:
> On 11/26/20 9:03 AM, Richard Sandiford wrote:
>> Thanks for the reviews.
>>
>> Jeff Law via Gcc-patches <gcc-patches@gcc.gnu.org> writes:
>>> On 11/13/20 1:10 AM, Richard Sandiford via Gcc-patches wrote:
>>>> Just after GCC 10 stage 1 closed (oops), I posted a patch to add a new
>>>> combine pass.  One of its main aims was to allow instructions to move
>>>> around where necessary in order to make a combination possible.
>>>> It also tried to parallelise instructions that use the same resource.
>>>>
>>>> That pass contained its own code for maintaining limited def-use chains.
>>>> When I posted the patch, Segher asked why we wanted yet another piece
>>>> of pass-specific code to do that.  Although I had specific reasons
>>>> (which I explained at the time) I've gradually come round to agreeing
>>>> that that was a flaw.
>>>>
>>>> This series of patches is the result of a Covid-time project to add
>>>> a more general, pass-agnostic framework.  There are two parts:
>>>> adding the framework itself, and using it to make fwprop.c faster.
>>>>
>>>> The framework part
>>>> ------------------
>>>>
>>>> The framework provides an optional, on-the-side SSA view of existing
>>>> RTL instructions.  Each instruction gets a list of definitions and a
>>>> list of uses, with each use having a single definition.  Phi nodes
>>>> handle cases in which there are multiple possible definitions of a
>>>> register on entry to a basic block.  There are also routines for
>>>> updating instructions while keeping the SSA representation intact.
>>>>
>>>> The aim is only to provide a different view of existing RTL instructions.
>>>> Unlike gimple, and unlike (IIRC) the old RTL SSA project from way back,
>>>> the new framework isn't a “native” SSA representation.  This means that
>>>> all inputs to a phi node for a register R are also definitions of
>>>> register R; no move operation is “hidden” in the phi node.
>>> Hmm, I'm trying to parse what the last phrase means.  Does it mean that
>>> the "hidden copy" problem for out-of-ssa is avoided?  And if so, how is
>>> that maintained over time.  Things like copy-prop will tend to introduce
>>> those issues even if they didn't originally exist.
>> Yeah, the phi nodes simply say which definition of register R provides
>> the value of R on a particular incoming edge.  That definition will
>> itself be a phi node for R, an artificial definition of R created by DF
>> (e.g. for incoming function arguments or for EH data registers), or an
>> actual instruction that sets R.
>>
>> In other words, the SSA form is a purely on-the-side thing and the
>> underlying RTL instructions are maintained in the same way as normal.
>> The SSA form can be deleted at any time without performing a separate
>> out-of-ssa step.  In that respect it's different from cfglayout,
>> for example.
>>
>> One of the goals was to allow the SSA form to be used even after RA,
>> where invisible copies would be more problematic.
> Right.  But what I'm struggling a bit with is whether or not we have to
> put restrictions on what passes can do with that on-the-side data
> structure.  While I think we can have that on-the-side data structure be
> conservatively correct, I think we have to make sure that we don't allow
> changes to the on-the-side data structure to occur that ultimately we
> can't reflect into RTL.

Right.  Passes have no way of changing the phi nodes directly.  If we
allowed them to do that in future, it would need to be under controlled
cirumstances.

I think the way to think about it is that these “phis” are really just
an alternative way of representing reaching definitions.  Both describe
something that is already (independently) true.  The same goes for
DF liveness information.  It doesn't really make sense to change the
DF live-in or live-out sets directly: you can't independently make
something live or dead just by twiddling bits in the bitmap.

In other words, liveness and reaching definitions are purely reactive:
they change in response to changes to the RTL instructions.  The same is
true for this on-the-side SSA form.

I think that's the trade-off with using this kind of representation
instead of a native SSA one: you can do SSA-style analysis at any stage
of compilation (even after RA), but the result of the transformation
always has to be represented directly as RTL instructions.

>>> It's unfortunately that there's no DCE passes abutting
>>> fwprop as DCE is really easy in an SSA world.
>> fwprop.c calls delete_trivially_dead_insns, so it does some light DCE.
>> One thing I wanted to do (but ran out of time to do) was get the main
>> SSA insn-change routine (rtl_ssa::change_insns) to record when an
>> instruction becomes dead, and then perform DCE as part of the later
>> rtl_ssa::perform_pending_updates step.  This would be much cheaper
>> than doing another full scan of the instruction stream (which is what
>> delete_trivially_dead_insns needs needs to do).
>>
>> Unfortunately, I suspect we're relying on this delete_trivially_dead_insns
>> call to delete instructions that became dead during earlier passes, not just
>> those that become dead during fwprop.c.  So I guess we would need a full
>> DCE at some point: making fwprop.c clean up its own mess might not be
>> enough.
> Oh, yea, if it's using delete_trivially_dead_insns, then, yea, it's got
> a mini-DCE and using the SSA algorithm would seem to be a step forward.
>
> I don't necessarily see that incoming dead code is that big of a
> problem.  Ultimately it's still going to look like SSA definition with
> no uses, in the on-the-side data structure, right?  So an SSA based DCE
> should be able to clean up the mess from fwprop as well as any incoming
> dead code.

Yeah, it's easy to do.  But deleting dead code created by fwprop would
come “for free”: the rtl_ssa:: code that changes the instructions could
just record which instructions become dead as a result of the
transformations, and then use those to populate the worklist.

If we deal with incoming dead code then we need to look at every
instruction individually to see whether it's already dead.  Although
that's easy to do, I don't think it would be a significant saving over
delete_trivially_dead_insns.

Thanks,
Richard