Re: [new-regalloc-branch]: pre-reload pass

[Michael Matz <matzmich at cs dot tu-berlin dot de>]

Hi,

On 7 Feb 2002, Denis Chertykov wrote:

> You wrote about the heuristic algorithm for web_part's connection.
> I wrote about ideal coalescing/connecting.

Yes, but I think that's not a fundamental difference.  We only differ in
the heuristic when to add copy-insns (your web-barriers).  You add them
everywhere (with certain effects), I add them where it seems to be good
guided by the web-parts (with certain other effects).

Your heuristic is of course easier to implement, as my method involves
adding copy-insns, i.e. changing the code, _while_ building the webs out
of web-parts (it basically stop's building webs, when it seems to have too
narrow hardregs, and starts a new one, and adds copy-insns to make the
code agree with the built webs).

But that should be the only difference.  We both rely on good coalescing
to hopefully get rid of some of those copy-insns again.

Your method maximizes the freedom for each web (which are very tiny before
coalscing), but also stresses the coalescer maximally.  My method maybe
gives not that much freedom for each web, but they are bigger from the
beginning, not stressing coalesce as much.  I think we could implement
both methods to see what gives better code, or is faster.  Certainly I
would start with yours, for it's simplicity ;)

> > Well, we shouldn't add copy insns all over the place when we aren't sure,
> > if they are usefull.  But other than that the coalesce is quite effective
> > as said.
>
> May be we can have a two methods of coalescing/spilling.
> 1. Coalesce a lot of micro-web's (without spilling to regs);
> 2. Spilling long (normal) webs to regs.

Hmm, at first glance the above seemed to me like what I said above
(implement both methods), but now I'm not sure anymore: What irritates me
is your reference to 'without spilling to regs'.  Why should we handle
those things different?  In fact what do you think a micro-web is exactly?
After adding those web-barriers, everything are normal webs.  They are
coalesced in a normal way, and also spilled in a normal way.  What I
talked about in last mail (spilling to regs), was a completely orthogonal
thought, dealing with spilling itself, not with the other ideas how we
should deal with conflicting (or too narrow) constraints.

> > Ohh, hmm, right.  At least not in the form of a changed regclass.  I hope
> > you don't mind too much.
>
> My web_class was based on regclass.
> IMHO: existing regclass compute a good register preferences.

But we now both think, that this too can go away, yes?  (I at least think
so).

> > Yes.  What do you want to do?  Right now I can think of three things I
> > could do tomorrow in my long train trip ;-) :

Bah, the trip is over and I haven't done any of those three, instead
slept, and read newspaper ;-)

> > 1) changing spilling to first try pseudo copy insn, instead stack spills.
> > 2) familiarizing with the current pre-reload and maybe simplyfy it through
> >    deletion of random chunks of text ;)
>
> IMHO: it's not necessary because current pre-reload will go away.

Hmm, well, but as a starting point for creating ra_refs it will be used,
so simplifying still might be a good idea ;-)

> > 3) playing with the above pseudo-code loop to actually create
> > ra_refs.
>
> I'm more familiar with 2 and may be 3.

Ok, I'll fiddle with 1) the next days.

> IMHO: 3 must be incorporated to pre-reload.

Exactly.

> IMHO: pre-reload must do for each insn:
> 1. Chose better insn alternative;
>    (easy to implement. It's already part of pre-reload.)
> 2. reload existing insn for satisfying chosen alternative:
>   2.1. Reload all match_dups and '0...9' constraints;
>   2.2. Add all required clobber registers for (match_scratch ...);
>   2.3. Correct all operands with wrong constant values;
>   2.4. Correct all wrong addresses; (very difficult item)
>   2.5. Reload all earlyclobbered operands. IE operands with '=&' constraint.
>      (Some time such operands overlap or equal to another operands)
> 3. Fill ra_ref;
> 4. Build list of ra_ref's for insn operands.

To be precise, the ra_refs should be built already in (1) (when looking
for the best alternative), as the operands and such are readily available.
Later those ra_refs will only be filled with more and more information
(i.e. after the best alternative is found, or if code is changed in (2)).
This is so, because I think it might be worthwhile for (2) to have already
some readily available information about operands of the insn (i.e. the
half-filled ra_refs), without iterating over the RTL again.

> I can try to implement 1 and commit it.

You mean your 1. here, not my 1), right (i.e. the pre-reload alternative
choosing)?  Hack away ;)


Ciao,
Michael.