Re: A new gimple pass (LRS: live range shrinking) to reduce register pressure

[Xinliang David Li <davidxl at google dot com>]

On Sat, Jan 3, 2009 at 3:13 AM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> On Sat, Jan 3, 2009 at 1:58 AM, Xinliang David Li <davidxl@google.com> wrote:
>> There are
>> two parts of phase: the analysis and transformation. The analysis part
>> should actually be done early in the pipeline -- the result of which
>> can be used to guide transformations downstream -- as not all
>> transformations that increase register pressure can be undone easily.
>
> OK, if this is your goal, then the analysis and the transformation
> should be clearly separated in your patch.
>

The transformations need to update the result of the dataflow which
makes the integration of the two quite natural. However passing down
the summary of the analysis is possible.

>
>> The code motion part in theory needs to be done as late as possible.
>> However if later phases are made register pressure aware (by using the
>> early estimate), this (putting it late) does not seem that important.
>
> That means you need to expose the results of the analysis somehow to
> the other passes.  What do you have in mind for this, about what this
> interface would look like?

This depends on how downstream clients want it to be. Suggestions are welcome.

>
>
>> Pre-LRS re-association pass is in fact one of the main contributors to
>> register pressure increase due to its unique of way (eager) of code
>> motion -- which can be corrected by LRS -- the corrected results will
>> not likely be undone later.
>
> So the compiler would first eagerly reassociate, and then it would
> undo that.

It does not eagerly reassociation -- but eagerly performs code motion
to avoid possible dependence violation. LRS does not undo all of them.
It mostly tries to find the optimal placement for the statements while
keeping the reassociation results. In rare cases, when the expression
tree is really large, it will be re-reassociated --- even that does
not undo everything -- for instance opportunities for constant
folding.



  Which brings us back to the point made earlier, why this
> LRS reassociation is not just integrated into tree-ssa-reassoc.c.  You
> say you want to make existing passes register pressure aware.  Looks
> to me, then, that you should start by making tree-ssa-reassoc.c
> register pressure aware! ;-)

This won't be as optimal as explained above if
register-pressure-awareness means simply shutting it down when
register pressure is high.  However if register-pressure-aware means
availability of interfaces to tell if a transformation can actually
increase register pressure or not, then it is ideal --- the later can
be very complicated.

What I have in mind is to make post-LRS phases register pressure aware.

  E.g. make the analysis a separate pass,
> expose an interface, and make tree-ssa-reassoc.c use it. I could use
> that analysis myself in some of the patches I've posted for PRE (see
> http://gcc.gnu.org/ml/gcc-patches/2008-12/msg00199.html).

What interfaces would you like to have?

>
>
>> Besides, is it a trend in gcc that more and more passes (machine
>> independent) will be moved up stream (as gimple passes) due to obvious
>> reasons?
>
> This was one of the original ideas behind tree-ssa, but scheduling and
> register allocation were never amongst the candidates to be moved
> upstream.  Some kind of register pressure control measures are
> necessary, but a real live range shrinking pass is so closely related
> to scheduling and register allocation that I don't see any obvious
> reasons why it should be so far upstream in the passes pipeline.
>

Clearly there are tradeoffs. If there are not (or will not be) many
RTL passes (other than sched1) that can mess things up, doing LRS at
the end of gimple passes should be ok.

>
>> sched1 can be problem for LRS (but can be toned down due to
>> high reg pressure).
>
> People have tried and failed :-)
> The biggest issue here for x86 is the special registers that some
> insns need.  You really need to know per-regclass register pressure (a
> good approximation anyway) to make sched1 work on x86.  Your analysis
> would provide that, if ported over to RTL.

Is it not on for x86?

>
>> Existence of ssa and memSSA makes a gimple pass much
>> more attractive.
>
> I don't see you use many SSA properties in the LRS pass.

you do not see the uses of all ssa based UD/DU over over the place? Or
you are saying they can be easily done using RTL based data flow? If
that is the case, then many gimple passes should probably also be
moved down instead -- for instance forward prop can expose more
reassociation opportunities, so ideally it should be moved down to RTL
(also due to the fact that dependence height estimation is more
precise).

  And memSSA
> is about to go away when the alias-improvements branch is merged into
> the trunk.

Are you saying that memory dependencies won't be available in SSA
form, and everything is query based? Are we sure about that compile
time implication of this?

Also, the availability of infrastructure should not be the
> guiding criterion when it comes to deciding where a pass should be in
> the optimization pipeline, IMHO...

It is one of the deciding factor, though not necessariliy the primary one.

David

>
> Gr.
> Steven
>