Re: Graph coloring for register allocation?

Re: Graph coloring for register allocation?

[dewar]

Well there is loads of work on register allocation and scheduling
since the publication of the IBM algorithm, so I don't think anyone
would use this unchanged. There are many variations on this theme
which certainly are NOT patented (even a small variation on a patent
tends to escape the patenting in the software field).

So rather than ask whether we want to use the IBM patented algorithn
at this stage, I think the appropriate thing is to survey the current
state of the art and ask whether we could be doing better using whatever
algorithms and methods are available.

Re: Graph coloring for register allocation?

[Daniel Berlin]

On 1/17/01 8:48 PM, "dewar@gnat.com" <dewar@gnat.com> wrote:

> Well there is loads of work on register allocation and scheduling
> since the publication of the IBM algorithm, so I don't think anyone
> would use this unchanged. There are many variations on this theme
> which certainly are NOT patented (even a small variation on a patent
> tends to escape the patenting in the software field).
> 
> So rather than ask whether we want to use the IBM patented algorithn
> at this stage, I think the appropriate thing is to survey the current
> state of the art and ask whether we could be doing better using whatever
> algorithms and methods are available.
> 

I've been working on, besides the SSA value numbering stuff (which works
nicely, I'm just putting the finishing touches on it before contributing.
Probably be a few weeks. ), an register allocator that also does live range
splitting. It's based on optimistic register coalescing
( http://citeseer.nj.nec.com/park98optimistic.html ).
This is, from what I understand, pretty close to state of the art, if not
there already.

I started this morning during first day of class classes, and finished and
tested the routine to build the interference graph.

It'll probably be months for me to finish the register allocator, and it
would be nice to have some help.

--Dan

Re: Graph coloring for register allocation?

[Michael Matz]

Hi,

On Wed, 17 Jan 2001, Daniel Berlin wrote:
> 
> I've been working on, besides the SSA value numbering stuff (which works
> nicely, I'm just putting the finishing touches on it before contributing.
> Probably be a few weeks. ), an register allocator that also does live range
> splitting. It's based on optimistic register coalescing
> ( http://citeseer.nj.nec.com/park98optimistic.html ).
> This is, from what I understand, pretty close to state of the art, if not
> there already.
> 
> I started this morning during first day of class classes, and finished and
> tested the routine to build the interference graph.
> 
> It'll probably be months for me to finish the register allocator, and it
> would be nice to have some help.

I too was planning to write a register allocator. And guess what, after
reading probably all modern freely available papers on that topic I also
wanted to take Park's approach (optimistic Coloring and Coalescing).  
While the algorithmic dimension is no problem, I was a little bit slowed
down by gcc's RTL, and how to parse it correctly for conflicts (to not
overconstrain the graph, but also to not forget conflicts), and to take
the machine architecture into account. Of course it wasn't of much help,
that I'm more a middle-end guy ;-)

To make it short, I would very much love to help with this.


Ciao,
Michael.

Re: Graph coloring for register allocation?

[Daniel Berlin]

On Thu, 18 Jan 2001, Michael Matz wrote:

> Hi,
>
> On Wed, 17 Jan 2001, Daniel Berlin wrote:
> >
> > I've been working on, besides the SSA value numbering stuff (which works
> > nicely, I'm just putting the finishing touches on it before contributing.
> > Probably be a few weeks. ), an register allocator that also does live range
> > splitting. It's based on optimistic register coalescing
> > ( http://citeseer.nj.nec.com/park98optimistic.html ).
> > This is, from what I understand, pretty close to state of the art, if not
> > there already.
> >
> > I started this morning during first day of class classes, and finished and
> > tested the routine to build the interference graph.
> >
> > It'll probably be months for me to finish the register allocator, and it
> > would be nice to have some help.
>
> I too was planning to write a register allocator. And guess what, after
> reading probably all modern freely available papers on that topic I also
> wanted to take Park's approach (optimistic Coloring and Coalescing).

Great minds read the same papers, or something like that.
> While the algorithmic dimension is no problem, I was a little bit slowed
> down by gcc's RTL, and how to parse it correctly for conflicts (to not
> overconstrain the graph, but also to not forget conflicts),

This was actually the largest pain in the ass for generating the
interference graph. I stole two routines from combine.c and modified them
(they tell you whether a register is live after a certain insn).

I've verified the interference graph matches what the normal register
allocator believes as well.
>  and to  take
> the machine architecture into account.

This is something i was planning on worrying about after the the
implementation was far along. For the case ofinsns that will take up >1
register, it's already handled when building the interference graph.
 I  figured there are actually a billion
ways to handle the case of things like floating point calculations using
fp registers.  For instance, for some architectures (or maybe all
of them , it's hard to say), It might pay to just allocate the registers
in seperate passes (IE run the algorithm for the integer operations, then
the fp operations) . SML/NJ does this. It's not that particularly
difficult, since we know the modes of the instructions, and thus, what
kind of registers they need.
> Of  course it wasn't of much help,
> that I'm more a middle-end guy ;-)

Same here.
>
> To make it short, I would very much love to help with this.
>

Let me figure out the best way to do this (IE a branch on gcc cvs, or a
seperate cvs server, which i already have).
>
> Ciao,
> Michael.
>
>

Re: Graph coloring for register allocation?

[Michael Hayes]

Daniel Berlin writes:

 > This was actually the largest pain in the ass for generating the
 > interference graph. I stole two routines from combine.c and modified them
 > (they tell you whether a register is live after a certain insn).

I posted some generic dataflow routines that I posted to this list a
few weeks ago that could help with this.  As well as liveness info,
they generate def-use and use-def info from which you can generate
webs from.

Michael.

Re: Graph coloring for register allocation?

[Daniel Berlin]

On Sat, 20 Jan 2001, Michael Hayes wrote:

> Daniel Berlin writes:
>
>  > This was actually the largest pain in the ass for generating the
>  > interference graph. I stole two routines from combine.c and modified them
>  > (they tell you whether a register is live after a certain insn).
>
> I posted some generic dataflow routines that I posted to this list a
> few weeks ago that could help with this.  As well as liveness info,
> they generate def-use and use-def info from which you can generate
> webs from.
>

Neat!
Apparently i'm blind. I searched the archives (for dataflow, use-def,
etc), and looked at all messages
from you since december, and all i can find is loop patches.
Are these routines in one of them? If so, which one. There are about 20
Loop patches from you.

--Dan

Re: Graph coloring for register allocation?

[Michael Hayes]

Daniel Berlin writes:
 > Neat!
 > Apparently i'm blind. I searched the archives (for dataflow, use-def,
 > etc), and looked at all messages
 > from you since december, and all i can find is loop patches.
 > Are these routines in one of them? If so, which one. There are about 20
 > Loop patches from you.

Ah, in retrospect it was pretty obscure. 

Try gcc.gnu.org/ml/gcc/2000-12/msg00888.html

Michael.

Re: Graph coloring for register allocation?

[Daniel Berlin]

On Sat, 20 Jan 2001, Michael Hayes wrote:

> Daniel Berlin writes:
>  > Neat!
>  > Apparently i'm blind. I searched the archives (for dataflow, use-def,
>  > etc), and looked at all messages
>  > from you since december, and all i can find is loop patches.
>  > Are these routines in one of them? If so, which one. There are about 20
>  > Loop patches from you.
>
> Ah, in retrospect it was pretty obscure.
>
> Try gcc.gnu.org/ml/gcc/2000-12/msg00888.html
>
> Michael.
>
Almost works, except you appear to have modified sbitmap.h to include an
EXECUTE_IF_SET_IN_SBITMAP_REV macro.
It appears to have no min argument (IE it's not EXECUTE_IF_SET_IN_SBITMAP
with the for loop arguments changed a little), so could you post the patch
that gives this routine?
--Dan

Re: Graph coloring for register allocation?

[Michael Hayes]

[-- Attachment #1: Type: text/plain, Size: 395 bytes --]

Daniel Berlin writes:

 > Almost works, except you appear to have modified sbitmap.h to include an
 > EXECUTE_IF_SET_IN_SBITMAP_REV macro.
 > It appears to have no min argument (IE it's not EXECUTE_IF_SET_IN_SBITMAP
 > with the for loop arguments changed a little), so could you post the patch
 > that gives this routine?

OK, here it is again.  I've also ripped out the timing stuff.

Michael.

[-- Attachment #2: df.patch.gz --]
[-- Type: application/x-gzip, Size: 22400 bytes --]

Re: Graph coloring for register allocation?

[Michael Matz]

Hi,

On Sat, 20 Jan 2001, Michael Hayes wrote:
>  > This was actually the largest pain in the ass for generating the
>  > interference graph. I stole two routines from combine.c and modified them
>  > (they tell you whether a register is live after a certain insn).
> 
> I posted some generic dataflow routines that I posted to this list a
> few weeks ago that could help with this.  As well as liveness info,
> they generate def-use and use-def

Yep, I have them, but not looked at them closely due to missing time.
Also, meanwhile I was playing with the thought of building the
interference graph incrementally (as proposed in one of the newer
articles), and for that u/d-d/u-chains are not the best source. But at
least for gathering the info your routines seem very handy.

> info from which you can generate webs from.

Ahh, a Muchnick reader?  ;-) I found nowhere else (IIRC) the term "web"
for what is called everywhere else live range. Although I also like more
the former one ;)


Ciao,
Michael.

Re: Graph coloring for register allocation?

[Daniel Berlin]

On Sun, 21 Jan 2001, Michael Matz wrote:

> Hi,
>
> On Sat, 20 Jan 2001, Michael Hayes wrote:
> >  > This was actually the largest pain in the ass for generating the
> >  > interference graph. I stole two routines from combine.c and modified them
> >  > (they tell you whether a register is live after a certain insn).
> >
> > I posted some generic dataflow routines that I posted to this list a
> > few weeks ago that could help with this.  As well as liveness info,
> > they generate def-use and use-def
>
> Yep, I have them, but not looked at them closely due to missing time.
> Also, meanwhile I was playing with the thought of building the
> interference graph incrementally (as proposed in one of the newer
> articles), and for that u/d-d/u-chains are not the best source. But at
> least for gathering the info your routines seem very handy.
What papers show how to build it incrementally?
I couldn't find any.

As for the handiness, Yes, definitely.

Because there are so many implementations available, i've started with
Iterated Register Coalescing, and will convert it to optimistic when it's
done.
Works well so far.

Just so we are all on the same page, everyone realizes that the new
register allocator will replace the regmove, the local-alloc, and the
global-alloc passes, right?


 > > > info from which you can generate webs from.
>
> Ahh, a Muchnick reader?  ;-) I found nowhere else (IIRC) the term "web"
> for what is called everywhere else live range. Although I also like more
> the former one ;)
>
>
> Ciao,
> Michael.
>
>

Re: Graph coloring for register allocation?

[Daniel Berlin]

>
> Just so we are all on the same page, everyone realizes that the new
> register allocator will replace the regmove, the local-alloc, and the
> global-alloc passes, right?

Also, it gets rid of reload unless it's comment at the top of the file is
lying (we can force).

That means we replace about 25000 lines of code (24,775 according to wc)
with like 1000 or 2000.

If you can do something in 25x less code than you do now, it usually means
your current way is a *bit* complex.
--Dan

Re: Graph coloring for register allocation?

[Nick Ing-Simmons]

Daniel Berlin <dberlin@redhat.com> writes:
>>
>> Just so we are all on the same page, everyone realizes that the new
>> register allocator will replace the regmove, the local-alloc, and the
>> global-alloc passes, right?
>
>Also, it gets rid of reload unless it's comment at the top of the file is
>lying (we can force).
>
>That means we replace about 25000 lines of code (24,775 according to wc)
>with like 1000 or 2000.
>
>If you can do something in 25x less code than you do now, it usually means
>your current way is a *bit* complex.

I suspect your new one will grow some ;-)
But I am very interested in the results - the existing register
allocator(s) have been a pain for DSP targets.

-- 
Nick Ing-Simmons <nik@tiuk.ti.com>
Via, but not speaking for: Texas Instruments Ltd.

Re: Graph coloring for register allocation?

[Richard Henderson]

On Sun, Jan 21, 2001 at 04:44:20PM -0500, Daniel Berlin wrote:
> Also, it gets rid of reload unless it's comment at the top of the file is
> lying (we can force).

No, you'll never get rid of reload.  Not without replicating
it anyway, which seems a less than winning proposition.

It's job is to fix up the mistakes the register allocator makes.
As such, the best you can do is give it no work to do by finding
a perfect allocation.


r~

Re: Graph coloring for register allocation?

[Daniel Berlin]

On Mon, 22 Jan 2001, Richard Henderson wrote:

> On Sun, Jan 21, 2001 at 04:44:20PM -0500, Daniel Berlin wrote:
> > Also, it gets rid of reload unless it's comment at the top of the file is
> > lying (we can force).
>
> No, you'll never get rid of reload.  Not without replicating
> it anyway, which seems a less than winning proposition.
>
> It's job is to fix up the mistakes the register allocator makes.

Define mistakes.
Thinks like forcing things that need to be in hard regs into hard regs,
making sure certain things have certain registers, combinations of
these two, etc, are already going to be taken care of for us by the new
allocator.


 > As such, the best you can do is give it no work to do by finding
> a perfect allocation.

Re: Graph coloring for register allocation?

[Richard Henderson]

On Mon, Jan 22, 2001 at 05:31:17PM -0500, Daniel Berlin wrote:
> Define mistakes.

Spills, invalid combinations of register classes, non-legitimate
constants into memory, anything that isn't otherwise valid.  Mistakes.

> Thinks like forcing things that need to be in hard regs into hard regs,
> making sure certain things have certain registers, combinations of
> these two, etc, are already going to be taken care of for us by the new
> allocator.

You're going to take care of all of the exceedingly nasty bits with
secondary and tertiary reload regs?  With cases for which there are
no valid combination of register classes, and we have to go through
memory, possibly via a third register class first?

I sure hope you're not planning on messing up a nice understandable
register allocation algorithm with this.  All you should be striving
for IMO is "close to correct".


r~

Re: Graph coloring for register allocation?

[Daniel Berlin]

On Mon, 22 Jan 2001, Richard Henderson wrote:

> On Mon, Jan 22, 2001 at 05:31:17PM -0500, Daniel Berlin wrote:
> > Define mistakes.
>
> Spills, invalid combinations of register classes,

Both are taken care of pretty easily.
In fact, both are already accounted for in the algorithms i've looked at,
or are amazingly simple to extend to handle.

> non-legitimate
> constants into memory, anything that isn't otherwise valid.  Mistakes.
>
Rest may take work.

> > Thinks like forcing things that need to be in hard regs into hard regs,
> > making sure certain things have certain registers, combinations of
> > these two, etc, are already going to be taken care of for us by the new
> > allocator.
>
> You're going to take care of all of the exceedingly nasty bits with
> secondary and tertiary reload regs?  With cases for which there are
> no valid combination of register classes, and we have to go through
> memory, possibly via a third register class first?
>
> I sure hope you're not planning on messing up a nice understandable
> register allocation algorithm with this.  All you should be striving
> for IMO is "close to correct".

Making sure what we have is valid for the architecture, in terms of
combinations of registers and register classes, making sure we don't
spill things we shouldn't, etc, are pretty easy to take care of in an
elegant way in the graph coloring allocator.
Most of these algorithms have this stuff already accounted for. since they
have to do the same thing.

Anything I can't do without adding a lot of complexity, i won't do.
--Dan
> > r~ >

Re: Graph coloring for register allocation?

[Zack Weinberg]

On Sun, Jan 21, 2001 at 04:44:20PM -0500, Daniel Berlin wrote:
> >
> > Just so we are all on the same page, everyone realizes that the new
> > register allocator will replace the regmove, the local-alloc, and the
> > global-alloc passes, right?
> 
> Also, it gets rid of reload unless it's comment at the top of the file is
> lying (we can force).
> 
> That means we replace about 25000 lines of code (24,775 according to wc)
> with like 1000 or 2000.

Some other things you might at least try to get rid of:

SMALL_REGISTER_CLASSES (and therefore all kinds of cruft all over the place).
Inability to run the scheduler before register allocation on some machines.
regclass.c (not entirely clear to me what this does)
reg-stack.c
hard-reg-set.h (more cruft all over the place)

zw

Re: Graph coloring for register allocation?

[Daniel Berlin]

>
> SMALL_REGISTER_CLASSES (and therefore all kinds of cruft all over the place).
> Inability to run the scheduler before register allocation on some machines.

Unless i'm mistaken, all the papers i've looked at(save one or two, i
think Chow and Hennessy didn't, it's hard to recall) require that
scheduling be run before register allocation.

> zw
>

Re: Graph coloring for register allocation?

[Zack Weinberg]

On Wed, Jan 24, 2001 at 01:08:05PM -0500, Daniel Berlin wrote:
> >
> > SMALL_REGISTER_CLASSES (and therefore all kinds of cruft all over the place).
> > Inability to run the scheduler before register allocation on some machines.
> 
> Unless i'm mistaken, all the papers i've looked at(save one or two, i
> think Chow and Hennessy didn't, it's hard to recall) require that
> scheduling be run before register allocation.

I haven't been reading papers.  The current situation is that if you
run the scheduler before register allocation on certain machines,
reload will run out of registers and abort.  You see things like

void
c4x_optimization_options (level, size)
     int level ATTRIBUTE_UNUSED;
     int size ATTRIBUTE_UNUSED;
{
  /* Scheduling before register allocation can screw up global
     register allocation, especially for functions that use MPY||ADD
     instructions.  The benefit we gain we get by scheduling before
     register allocation is probably marginal anyhow.  */
  flag_schedule_insns = 0;
}

(c4x/c4x.c)  When they say "can screw up", they mean "can make reload
abort."

I had thought this was a problem with all SMALL_REGISTER_CLASSES
machines, but it seems not.

zw

Re: Graph coloring for register allocation?

[David Edelsohn]

>>>>> "Zack Weinberg" writes:

Zack> (c4x/c4x.c)  When they say "can screw up", they mean "can make reload
Zack> abort."

	Isn't the question whether the new allocator can replace reload,
or at least most of it?  If the new allocator can replace the part of
reload which crashes in this type of case, there is not problem.

	MPY-ADD allocation seems more like carefully obeying the register
classes as opposed to a constant that cannot be loaded directly or a value
ending up in completely the wrong register which requires secondary and
tertiary reloads to fix up.

David

Re: Graph coloring for register allocation?

[Richard Henderson]

On Wed, Jan 24, 2001 at 10:47:14AM -0800, Zack Weinberg wrote:
> I had thought this was a problem with all SMALL_REGISTER_CLASSES
> machines, but it seems not.

Actually, we're nearly at the point where we could run scheduling
before reload and not abort.

A while ago I solved the problem of moving the copy from hard
return register to pseudo away from the call instruction.  What's
left is making sure that copies from hard argument register to
pseudo don't move from the start of the function.

Of course, that doesn't address the fact that the current 
scheduler doesn't even pretend to consider register pressure,
so it's a questionable thing whether sched1 would be a win.



r~

Re: Graph coloring for register allocation?

[Michael Hayes]

Richard Henderson writes:
 > Actually, we're nearly at the point where we could run scheduling
 > before reload and not abort.
 > 
 > A while ago I solved the problem of moving the copy from hard
 > return register to pseudo away from the call instruction.  What's
 > left is making sure that copies from hard argument register to
 > pseudo don't move from the start of the function.

Does this also handle the case where incoming args are in hard
registers?  This was the primary reason why sched1 was disabled for
the c4x.

Michael.

Re: Graph coloring for register allocation?

[Richard Henderson]

On Thu, Jan 25, 2001 at 11:53:29AM +1300, Michael Hayes wrote:
>  > What's
>  > left is making sure that copies from hard argument register to
>  > pseudo don't move from the start of the function.
> 
> Does this also handle the case where incoming args are in hard
> registers?

Er, no.  As I said, that exactly the case that's left to do.


r~

Re: Graph coloring for register allocation?

[Michael Hayes]

Richard Henderson writes:
 > On Thu, Jan 25, 2001 at 11:53:29AM +1300, Michael Hayes wrote:
 > >  > What's
 > >  > left is making sure that copies from hard argument register to
 > >  > pseudo don't move from the start of the function.
 > > 
 > > Does this also handle the case where incoming args are in hard
 > > registers?
 > 
 > Er, no.  As I said, that exactly the case that's left to do.

That's what I thought but I've noticed that the interaction between
the scheduler and register allocator does not seem as bad as it used
to be for these incoming arguments.

Michael.

Re: Graph coloring for register allocation?

[Richard Henderson]

On Thu, Jan 25, 2001 at 12:06:49PM +1300, Michael Hayes wrote:
> That's what I thought but I've noticed that the interaction between
> the scheduler and register allocator does not seem as bad as it used
> to be for these incoming arguments.

That's true, things are better with Bernd's rewrite last year.
That is not, however, a guarantee.  There are still known x86
failures with -mregparm -fschedule-insns.


r~

Re: Graph coloring for register allocation?

[Michael Matz]

Hi,

On Wed, 24 Jan 2001, Daniel Berlin wrote:
> > SMALL_REGISTER_CLASSES (and therefore all kinds of cruft all over the place).
> > Inability to run the scheduler before register allocation on some machines.
> 
> Unless i'm mistaken, all the papers i've looked at(save one or two, i
> think Chow and Hennessy didn't, it's hard to recall) require that
> scheduling be run before register allocation.

There is still no good knowledge how the connection between RA and
scheduling is. Either the papers develop a merged algorithm for RA and
scheduling, or they run scheduling before and after RA. Exclusively
running it before wouldn't make sense, as spill insertions would destroy
(or change) dependence relationship and therefore scheduling assumbptions,
and if there was no spill insertion, running scheduling after RA would
make no difference. So, we would still have sched and sched2.


Ciao,
Michael.

Re: Graph coloring for register allocation?

[Zack Weinberg]

On Wed, Jan 24, 2001 at 08:21:11PM +0100, Michael Matz wrote:
> Hi,
> 
> On Wed, 24 Jan 2001, Daniel Berlin wrote:
> > > SMALL_REGISTER_CLASSES (and therefore all kinds of cruft all over the place).
> > > Inability to run the scheduler before register allocation on some machines.
> > 
> > Unless i'm mistaken, all the papers i've looked at(save one or two, i
> > think Chow and Hennessy didn't, it's hard to recall) require that
> > scheduling be run before register allocation.
> 
> There is still no good knowledge how the connection between RA and
> scheduling is. Either the papers develop a merged algorithm for RA and
> scheduling, or they run scheduling before and after RA. Exclusively
> running it before wouldn't make sense, as spill insertions would destroy
> (or change) dependence relationship and therefore scheduling assumbptions,
> and if there was no spill insertion, running scheduling after RA would
> make no difference. So, we would still have sched and sched2.

I've just been reading the Morgan book, which describes what I think
is a clever approach.  You do register coalescing and renaming, plus
"peephole" optimization (not the same thing as our peepholes), as you
come out of SSA form.  Then you walk the flow graph and calculate the
register pressure in all blocks; if it's bigger than the number of
architectural registers, you spill pseudos.  Then you do lazy code
motion to get the spills and reloads as far apart as possible.

Now you're ready to run the scheduler.  You've got a pretty good
guarantee that whatever it does, it won't crank up the register
pressure to the point where the allocator can't handle it.  The
register allocator still might have to spill things, but it's less
likely.  (But there's still a second scheduling pass after allocation
just in case.  It can be skipped if there were no additional spills.)

The problem I see, as with most things in Morgan, is that he assumes a
symmetric, RISCy target chip.  One big set of integer registers, one
big set of float registers.  I don't know how well the idea will map
to machines with odd register classes.

zw

Re: Graph coloring for register allocation?

[Daniel Berlin]

> > make no difference. So, we would still have sched and sched2.
>
> I've just been reading the Morgan book, which describes what I think
> is a clever approach.  You do register coalescing and renaming, plus
> "peephole" optimization (not the same thing as our peepholes), as you
> come out of SSA form.

Also, a few compilers i know of use more than one type of ssa form
(pruned, minimal, etc), because it's better to have duplicates adn whatnot
when doing certain ssa optimizations, like code motion, etc.

>  Then you walk the flow graph and calculate the
> register pressure in all blocks; if it's bigger than the number of
> architectural registers, you spill pseudos.  Then you do lazy code
> motion to get the spills and reloads as far apart as possible.
>
> Now you're ready to run the scheduler.  You've got a pretty good
> guarantee that whatever it does, it won't crank up the register
> pressure to the point where the allocator can't handle it.  The
> register allocator still might have to spill things, but it's less
> likely.  (But there's still a second scheduling pass after allocation
> just in case.  It can be skipped if there were no additional spills.)
>
> The problem I see, as with most things in Morgan, is that he assumes a
> symmetric, RISCy target chip.  One big set of integer registers, one
> big set of float registers.  I don't know how well the idea will map
> to machines with odd register classes.

Yeah, that's a problem.
One upside of the new allocator is that we can now leave around as many
copies/moves as we want, and we know the allocatgor will clean them up.

This is very nice for some optimizations, where you generate a lot of
copies, and then would waste time cleaning them up.

>
> zw
>

Re: Graph coloring for register allocation?

[Jeffrey A Law]

  In message < 20010124121031.J20522@wolery.stanford.edu >you write:
  > The problem I see, as with most things in Morgan, is that he assumes a
  > symmetric, RISCy target chip.  One big set of integer registers, one
  > big set of float registers.  I don't know how well the idea will map
  > to machines with odd register classes.
I believe it maps reasonably well.  You just need to compute the estimated
pressure for each class and compare the estimated pressure with the number
of registers of that particular class that are available.

Where I think it falls down is when we have values that can live in
multiple register classes, even though they prefer a specific class
(like addresses on machines with separate address and data registers).

That may (or may not) be solvable by also computing pressure for the
superclasses and using that to decide if it's worth creating a split
range when there aren't enough registers of the subclass available.

jeff

Re: Graph coloring for register allocation?

[Nick Ing-Simmons]

Daniel Berlin <dberlin@redhat.com> writes:
>>
>> SMALL_REGISTER_CLASSES (and therefore all kinds of cruft all over the place).
>> Inability to run the scheduler before register allocation on some machines.
>
>Unless i'm mistaken, all the papers i've looked at(save one or two, i
>think Chow and Hennessy didn't, it's hard to recall) require that
>scheduling be run before register allocation.

Which is not always ideal. For example "we" had/have DSP(s) where operations on 
address registers happen in a different pipe stage to operations on data 
registers. So schedule differs depending on whether a pseudo is assigned
to data register or address register. On that architecture at least 
it is better for something that knows data flow to "decide" that a pseudo 
should live in an address register (as that is how it is used next) and then 
schedule can arrange things correctly, then you have acurate lifetimes. 
"Our" compiler also moves the user's variable from one register to another 
during its life so that it can live in a data register if multiplied, and 
an address/index register when used as such. I attempted to mimic this in 
gcc port by creating new psuedos at the "emit" stage. But existing gcc code 
at the time "helpfully" collapsed them back, and then reload had to emit 
lots of reg/reg moves to get them in the right classes to meet the constraints.

-- 
Nick Ing-Simmons <nik@tiuk.ti.com>
Via, but not speaking for: Texas Instruments Ltd.

Re: Graph coloring for register allocation?

[Phil Edwards]

On Sun, Jan 21, 2001 at 12:56:23PM -0500, Daniel Berlin wrote:
>  > > > info from which you can generate webs from.
> >
> > Ahh, a Muchnick reader?  ;-) I found nowhere else (IIRC) the term "web"
> > for what is called everywhere else live range. Although I also like more
> > the former one ;)

I first came across "web" in a paper on cross-procedure register allocation
by -- I think -- Santhanam and Odert which predates Muchnick by about
eight years.  I'm fairly certain Muchnick references the earlier paper.
(I can say that only because the bibliography is *huge* -- pick a journal
paper at random and there's a good chance Muchnick references it.  :-)


Phil

-- 
pedwards at disaster dot jaj dot com  |  pme at sources dot redhat dot com
devphil at several other less interesting addresses in various dot domains
The gods do not protect fools.  Fools are protected by more capable fools.

Re: Graph coloring for register allocation?

[Michael Matz]

Hi,

On Sun, 21 Jan 2001, Daniel Berlin wrote:
> > Yep, I have them, but not looked at them closely due to missing time.
> > Also, meanwhile I was playing with the thought of building the
> > interference graph incrementally (as proposed in one of the newer
> > articles), and for that u/d-d/u-chains are not the best source. But at
> > least for gathering the info your routines seem very handy.
> What papers show how to build it incrementally?
> I couldn't find any.

Well, not incrementally, but sparse construction which can be more easily
extended for incremental updates (it only needs all def/use site of a
variable, no global information, and no incremental update of local
liveness per basic block). It's from the MLRISC guys in their new register
allocator: http://cm.bell-labs.com/cm/cs/what/smlnj/compiler-notes/new-ra.ps

> Because there are so many implementations available, i've started with
> Iterated Register Coalescing, and will convert it to optimistic when it's
> done.
> Works well so far.

Cool. Any code, CVS branches or similar stuff?

> Just so we are all on the same page, everyone realizes that the new
> register allocator will replace the regmove, the local-alloc, and the
> global-alloc passes, right?

Yep, and probably much (though not all) of reload*.c. 


Ciao,
Michael.

Re: Graph coloring for register allocation?

[Daniel Berlin]

On Tue, 23 Jan 2001, Michael Matz wrote:

> Hi,
>
> On Sun, 21 Jan 2001, Daniel Berlin wrote:
> > > Yep, I have them, but not looked at them closely due to missing time.
> > > Also, meanwhile I was playing with the thought of building the
> > > interference graph incrementally (as proposed in one of the newer
> > > articles), and for that u/d-d/u-chains are not the best source. But at
> > > least for gathering the info your routines seem very handy.
> > What papers show how to build it incrementally?
> > I couldn't find any.
>
> Well, not incrementally, but sparse construction which can be more easily
> extended for incremental updates (it only needs all def/use site of a
> variable, no global information, and no incremental update of local
> liveness per basic block). It's from the MLRISC guys in their new register
> allocator: http://cm.bell-labs.com/cm/cs/what/smlnj/compiler-notes/new-ra.ps

Ahhh.
I constantly look at the MLRISC stuff, since they always seem to have the
latest optimizations and whatnot implemented.

>
> > Because there are so many implementations available, i've started with
> > Iterated Register Coalescing, and will convert it to optimistic when it's
> > done.
> > Works well so far.
>
> Cool. Any code, CVS branches or similar stuff?

I have code, and after classes today, i should be finished with another
phase of allocation.

I'll ask about a cvs branch then.

>
> > Just so we are all on the same page, everyone realizes that the new
> > register allocator will replace the regmove, the local-alloc, and the
> > global-alloc passes, right?
>

--Dan

Re: Graph coloring for register allocation?

[Joseph S. Myers]

On Wed, 17 Jan 2001, Daniel Berlin wrote:

> I've been working on, besides the SSA value numbering stuff (which works
> nicely, I'm just putting the finishing touches on it before contributing.
> Probably be a few weeks. ), an register allocator that also does live range
> splitting. It's based on optimistic register coalescing
> ( http://citeseer.nj.nec.com/park98optimistic.html ).
> This is, from what I understand, pretty close to state of the art, if not
> there already.

Is this any relation to David Miller's register allocator that was being
written a couple of years ago (e.g.
http://gcc.gnu.org/ml/gcc/1999-01n/msg00221.html ), or is that now a dead
project?

-- 
Joseph S. Myers
jsm28@cam.ac.uk

Re: Graph coloring for register allocation?

[Daniel Berlin]

On 19 Jan 2001 19:09:43 +0000, Joseph S. Myers wrote:
> On Wed, 17 Jan 2001, Daniel Berlin wrote:
> 
> > I've been working on, besides the SSA value numbering stuff (which works
> > nicely, I'm just putting the finishing touches on it before contributing.
> > Probably be a few weeks. ), an register allocator that also does live range
> > splitting. It's based on optimistic register coalescing
> > ( http://citeseer.nj.nec.com/park98optimistic.html ).
> > This is, from what I understand, pretty close to state of the art, if not
> > there already.
> 
> Is this any relation to David Miller's register allocator that was being
> written a couple of years ago (e.g.
> http://gcc.gnu.org/ml/gcc/1999-01n/msg00221.html ), or is that now a dead
> project?
> 

No relation at all.
No idea if it's dead, might be nice to see the code, but hey, that's
life.
--Dan

Re: Graph coloring for register allocation?

[dewar]

<<If you can do something in 25x less code than you do now, it usually means
your current way is a *bit* complex.
>>

Or that there are issues not fully understood, but of course the proof
is in the pudding as they say :-)

Graph coloring for register allocation?

[Stan Shebs]

Do we believe that the use of graph coloring will improve GCC's
register allocation?  IBM's patent will presumably run out in a couple
of years, so it seems like a good time to start thinking about it.
Perhaps IBM could be nice and license it for GCC before then, but
maybe it doesn't matter, because the current algorithm has gotten
enough tuning over the years?  Has anybody experimented with this?

Stan