[Bug rtl-optimization/64164] [4.9/5/6 Regression] one more stack slot used due to one less inlining level

rguenth at gcc dot gnu.org gcc-bugzilla@gcc.gnu.org
Wed Apr 1 07:51:00 GMT 2015


https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64164

--- Comment #34 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jeffrey A. Law from comment #33)
> On 03/31/2015 05:25 AM, rguenth at gcc dot gnu.org wrote:
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64164
> >
> > --- Comment #30 from Richard Biener <rguenth at gcc dot gnu.org> ---
> > (In reply to Jeffrey A. Law from comment #28)
> >> So I've been thinking about how to integrate life/conflict analysis into the
> >> uncprop code and it may not be that bad, both from an implementation and
> >> computation standpoint.
> >>
> >> Most importantly, we don't have to compute full life information.  We really
> >> just need to compute the life of the equivalence.  Given the life of the
> >> equivalence, if the equivalence is live in any block that contains the
> >> defining statement for an SSA_NAME appearing in the target PHI, then the
> >> equivalence conflicts and we don't want to unpropagate it.
> >>
> >> Computing the life of the equivalence is pretty easy and should be
> >> reasonably quick.  This is a cost we'd have to pay regardless of whether or
> >> not we integrate uncprop with out-of-ssa since we won't have life
> >> information for the expression.
> >>
> >> Collecting the SSA_NAMEs appearing on the RHS of the PHI so that we don't
> >> test for conflicts multiple times if an SSA_NAME shows up in multiple PHI
> >> alternatives would help keep the cost down as well.
> >>
> >> Ultimately I don't think we need to integrate uncprop and out-of-ssa to
> >> avoid the unprofitable transformation during uncprop.
> >
> > Also see "Boissinot et al., Fast Liveness Checking for SSA-Form Programs"
> > (CGO 08).  They describe a way to do fast liveness queries without actually
> > doing a (memory) expensive data-flow analysis but using SSA immediate-uses
> > and dominance checks.  Sth we could use in SSA coalescing as well to avoid
> > both the liveness bitmaps and the conflict graph.
> Yea, it looks reasonably interesting and there's probably benefit in 
> experimenting with that approach.  However, be aware that it's memory 
> consumption can be problematical.   According to their summary, it's 
> quadratic.

Yes, but that's only if you store the liveness info.  We don't need to do that
but we only need to compute whether two partitions conflict for each coalescing
candidate (which means a few SSA conflict checks dependent on partition size).

Our current algorithm is already quadratic in memory use because we do
store SSA liveness and the partition conflict graph.

What I'm not sure is whether doing the SSA based liveness check is going to
be slower compile-time wise.

>  Though presumably we could drop back to the tried and true 
> approach if we have too many BBs.
> 
> That definitely is stage1 material.

Indeed.

> Jeff



More information about the Gcc-bugs mailing list