[new-ra] Development status?

[new-ra] Development status?

[Giovanni Bajo]

Hello,

what's the development status for new-ra? How does it look like right now? Does
it improve compile-time or code generation? On which platforms? This has been
also discussed several times on IRC with mixed results, so I would like to get
a complete status report for it. The point has been brought up in the tree-ssa
discussion as well.

I would also like to ask why there is an active development branch for new-ra.
We have a few bug reports in bugzilla which are against the mainline version
(-fnew-ra), which looks like to be outdated. Can the development be done on the
mainline directly? Can the latest version be merged to the 3.4 branch &
mainline? Also, we never consider *any* new-ra bug as regressions since it's an
experimental switch for 3.4, so I guess changes can be committed there freely,
without the "regression-only" policy.

Thanks!
Giovanni Bajo

Re: [new-ra] Development status?

[Michael Matz]

Hi,

On Sun, 18 Jan 2004, Giovanni Bajo wrote:

> what's the development status for new-ra?

There is one big patch outstanding waiting review (and mayby design
decisions), plus one smaller patch from Denis, which touches the remaining
big problem:

1. For reload to become reducable (at least on sufficiently sane, probably
   on most platforms) we basically need to do something similar to
   regclass.  This means figuring out the correct (i.e. possbile) register
   classes for each register reference.  Due to GCCs design choosing a
   class for one reference might influence the possible classes for other
   references of the same register, or of other refs in the insn under
   consideration.  Implementing this optimally would mean finding some
   minimal set of paths over a set of graphs (I'm not even yet sure how it
   would have to be structured).  I haven't tried this but I think it
   would be too slow.

   Regclass.c does use some heuristics to find a good result, although
   it's also not exactly fast.  Currently we can either use the results
   from regclass for new-ra, or use pre-reload to do that (which fixes the
   choice of one certain alternative for an insn, before choosing
   classes).  Both result in suboptimal code, sometimes in horrible code.

   The above is something which needs to be implemented to make new-ra not
   regress compared to current ra.

2. Then, before considering new-ra done, pre-reload.c needs to be heavily
   massaged to not be an ugly clone of reload*.c .  Cosmetic (it's more or
   less a black box), but still important.

3. Then, performance issues.  Some passes in new-ra are only candidates
   for -O3 (or not even that), or have to be rewritten to be incremental.  
   Web splitting in particular, which would ideally be integrated into the
   normal spilling process, which then also would mean we wouldn't have to
   disable interference region spilling when using it.

The first numbered item above is ugly.  I believe at least, I haven't even 
starting implementing it, because I think it's so ugle ;-)  I know that 
this is a vicious circle.


> How does it look like right now? Does it improve compile-time

No.

> or code generation?

Sometimes.

> On which platforms?

Alpha, ppc.  To a lesser extend x86 and amd64.

> I would also like to ask why there is an active development branch for
> new-ra.

Sometimes I needed to touch other parts than ra*.c, which would 
have required full testing for mainline.  Also a branch is more 
appropriate for experimental things, even if that functionality would be 
hidden by an command line arg, IMHO.

> Can the latest version be merged to the 3.4 branch & mainline?

Hmm.  Let's say it this way, I don't want to have pre-reload in the 
current form in mainline.  It simply adds too much cruft, and I fear if it 
lands in mainline it never will get cleaned up.  But the allocator core is 
depending on pre-reload (unlike the one in currentl mainline).

> Also, we never consider *any* new-ra bug as regressions since it's an
> experimental switch for 3.4, so I guess changes can be committed there
> freely, without the "regression-only" policy.

Technically that's posible, but we also need to consider maintenability on 
our main branch.


Ciao,
Michael.
P.S: Yes, I'm working on the above.  Slowly, I admit.

Re: [new-ra] Development status?

[Denis Chertykov]

Michael Matz <matz@suse.de> writes:

> Hi,
> 
> On Sun, 18 Jan 2004, Giovanni Bajo wrote:
> 
> > what's the development status for new-ra?
> 
> There is one big patch outstanding waiting review (and mayby design
> decisions), plus one smaller patch from Denis, which touches the remaining
> big problem:
> 
> 1. For reload to become reducable (at least on sufficiently sane, probably
>    on most platforms) we basically need to do something similar to
>    regclass.  This means figuring out the correct (i.e. possbile) register
>    classes for each register reference.  Due to GCCs design choosing a
>    class for one reference might influence the possible classes for other
>    references of the same register, or of other refs in the insn under
>    consideration.  Implementing this optimally would mean finding some
>    minimal set of paths over a set of graphs (I'm not even yet sure how it
>    would have to be structured).  I haven't tried this but I think it
>    would be too slow.
> 
>    Regclass.c does use some heuristics to find a good result, although
>    it's also not exactly fast.  Currently we can either use the results
>    from regclass for new-ra, or use pre-reload to do that (which fixes the
>    choice of one certain alternative for an insn, before choosing
>    classes).  Both result in suboptimal code, sometimes in horrible code.
> 
>    The above is something which needs to be implemented to make new-ra not
>    regress compared to current ra.
> 
> 2. Then, before considering new-ra done, pre-reload.c needs to be heavily
>    massaged to not be an ugly clone of reload*.c .  Cosmetic (it's more or
>    less a black box), but still important.
> 
> 3. Then, performance issues.  Some passes in new-ra are only candidates
>    for -O3 (or not even that), or have to be rewritten to be incremental.  
>    Web splitting in particular, which would ideally be integrated into the
>    normal spilling process, which then also would mean we wouldn't have to
>    disable interference region spilling when using it.

4. Then, allocator must have a support for register elimination.

> 
> The first numbered item above is ugly.  I believe at least, I haven't even 
> starting implementing it, because I think it's so ugle ;-)  I know that 
> this is a vicious circle.

Michael ! I have completed the patch which calculate register classes
preferences as regclass (not as pre-reload).
Yes. I have converted regclass routines to work with webs.
I was interested in comparision of results given by pre-reload based
web_class and regclass based web_class.

Are you ready to look at patch and results ?

Denis.

Re: [new-ra] Development status?

[Michael Matz]

Hi,

On Tue, 20 Jan 2004, Denis Chertykov wrote:

> 4. Then, allocator must have a support for register elimination.

Indeed, I forgot.

> Michael ! I have completed the patch which calculate register classes
> preferences as regclass (not as pre-reload).

Cool.

> Yes. I have converted regclass routines to work with webs.

I had hoped there would be something better than regclass on webs. *sniff*

> I was interested in comparision of results given by pre-reload based
> web_class and regclass based web_class.

They at least shouldn't be worse, I think, are they?

> Are you ready to look at patch and results ?

Yes, please.


Ciao,
Michael.

Re: [new-ra] Development status?

[Denis Chertykov]

Michael Matz <matz@suse.de> writes:

> Hi,
> 
> On Tue, 20 Jan 2004, Denis Chertykov wrote:
> 
> > 4. Then, allocator must have a support for register elimination.
> 
> Indeed, I forgot.
> 
> > Michael ! I have completed the patch which calculate register classes
> > preferences as regclass (not as pre-reload).
> 
> Cool.
> 
> > Yes. I have converted regclass routines to work with webs.
> 
> I had hoped there would be something better than regclass on
> webs. *sniff*

I'm too, but I can't imagine another way to got a quick comparison of
results pre-reload classes and regclass classes.

> > I was interested in comparision of results given by pre-reload based
> > web_class and regclass based web_class.
> 
> They at least shouldn't be worse, I think, are they?

The results are *equal* !!! (for x86)
Exclude a few difficult cases.

> > Are you ready to look at patch and results ?
> 
> Yes, please.

I can send it tomorrow morning. (I forgot the code at my work. The
mail will be from gazovik@overta.ru)

After you got the patch and seeing on results I would discuss the
problem of register classes in new-ra. Is this OK ?

Denis.

Re: [new-ra] Development status?

[Michael Matz]

Hi,

On Tue, 20 Jan 2004, Denis Chertykov wrote:

> > > I was interested in comparision of results given by pre-reload based
> > > web_class and regclass based web_class.
> > 
> > They at least shouldn't be worse, I think, are they?
> 
> The results are *equal* !!! (for x86)
> Exclude a few difficult cases.

Hmm, but theoretically regclass can do much better than pre-reload (at the 
expense for sometimes emitting some reloads later).  The situation which 
it handles better for instance is this:

There are register classes A, B and AB (union of A and B).  Now suppose 
there is and insns i1 (with two ops) and i2 (one op) having 
such constraints:
 i1  op0 "a,b"   op1 "b,a"
 i2  op0 "a"

and in the insn stream we have this:
 i1(p0, p1)
 i2(p1)

(p0 and p1 are pseudos, i.e. p0 is operand 0 of i1, and p1 is operand 1 of 
i1 and operand 0 of i2).

Now pre-reload looks at each insn individually and selects one certain 
alternative of it (the cheapest for some definition of cheap).  Without 
other means it would select alternative 0 for insn i1.  Ergo p0 gets class 
A and p1 class B.

Now i2 requires p1 to be class A, ergo we need some fixup code.  Had 
pre-reload selected the second alternative from the beginning it wouldn't 
be needed.  Sometimes there are even cases where selection of an 
alternative should be deferred to even later.

regclass does better in this example.  It would determine that the cost of 
class A for p1 is less than class B.

> After you got the patch and seeing on results I would discuss the
> problem of register classes in new-ra. Is this OK ?

Yes.


Ciao,
Michael.