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

[Denis Chertykov]

Michael Matz <matzmich@cs.tu-berlin.de> writes:

> 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 ;)

I don't think than my method will be better. It was just a thought.
(I don't want to say than my method better and we must implement it.)

> 
> > > 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.

Why I think than Coalesce a lot of micro-web's not needed in spilling
to regs. (But needed in spilling to memory)


So, example:

(set (reg 101) (symbol_ref "user_var"))       ;; reg 101 must be GENERAL_REGS
... many other insns without reg 101
(set (reg 100) (mem (reg 101)))               ;; reg 101 must be BASE_REGS
... many other insns without reg 101
(set (reg 101) (plus (reg 101) (const_int 4)));; reg 101 must be IMM_REGS

Before coalescing will have:

1 (set (reg 101) (symbol_ref "user_var")) ;; reg 101 must be GENERAL_REGS
2 (web-barrier (reg 101))                 ;; reg 101 must be in GENERAL_REGS
... many other insns without reg 101
3 (web-barrier (reg 101))                 
4 (set (reg 100) (mem (reg 101)))         ;; reg 101 must be BASE_REGS
5 (web-barrier (reg 101))                 ;; reg 101 must be in GENERAL_REGS
... many other insns without reg 101
6 (web-barrier (reg 101))                 
7 (set (reg 101) (plus (reg 101) (const_int 4))) ;; reg 101 must be IMM_REGS

So, we will have separate micro-webs for insns:
 - 1,2 (web12);
 - 3,4,5 (web345);
 - 6,7 (web67).

If allocator can coalesce micro-webs then we will have one web - web12+345+67
If (after coalescing) allocator will not find coloring for web12+345+67
then allocator must split coalesced webs (web12+345+67) to originals
and if even micro-webs can't be colored then allocator can spill
them only to memory. Not to registers because all three webs already uses
restricted class (not GENERAL_REGS) as short as possible.
Or Before coalescing we already have a code which seems like code
after spilling to regs.

I'm use (web-barrier ...) only for better understanding the problem.
I don't want to generate real insns with (web-barrier ...).

> > > 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).

I'm agree with you. 
I just want to say than regclass uses another heuristic for choosing
registers preferences and it's effective.

> > 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 ;)

I mean my 1.
IMHO: In this case better to commit small uncomplete changes (if they don't
      break existing code) than wait for complete thing and commit
      huge changes.

Denis.