Fwd: Register classes

Fwd: Register classes

[Caroline Tice]

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

Oops, I forgot to copy the list on this message...

Begin forwarded message:

> From: Caroline Tice <ctice@apple.com>
> Date: August 18, 2004 10:55:43 AM PDT
> To: Daniel Berlin <dberlin@dberlin.org>
> Subject: Re: Register classes
>
> If you are planning on doing some work on the register allocator, 
> there was an EXCELLENT paper in
> PLDI this year (ACM Conference on Programming Language Design and 
> Implementation) on
> updating Chaitin's algorithm to work well on modern architectures.  I 
> would strongly recommend you read it, if you haven't already.  I can 
> send you a copy if you like.  Below is my summary of the paper:
>
> A Generalized Algorithm for Graph-Coloring Register Allocation
> by M.D. Smith, N. Ramsey and G. Holloway
>
> Expanding Chaitin's graph coloring algorithm to work on real hardware 
> architectures (taking into account
> register classes, overlapping between register classes, register 
> aliasing, etc).  Basically, Chaitin said a
> node in the coloring graph was trivially colorable if the number of 
> neighbors of N, "degree(N)" was less
> than the number of registers on the machine.  The new formula says   
> node is trivially colorable is
>  "squeeze (N)" is less than the number of registers actually available 
> for allocation, where squeeze (N) is
> the number of registers that N's neighbors will actually need.  The 
> rest of the paper is the concerned with
> accurately defining "squeeze (N)" and "number of registers actually 
> available for allocation" taking the
> various hardware architectures and constraints into account.
>
> -- Caroline Tice
> ctice@apple.com
>
> On Aug 18, 2004, at 10:39 AM, Daniel Berlin wrote:
>
>> A whole lot of ports seem to have register classes that contain 
>> registers that can't possibly be used together.
>> They also have to seem weird groupings of registers that don't make 
>> sense to be used by any single pseudo.
>>
>> What exactly is the goal of these register classes?
>> Is it to work around bad allocation decisions by the register 
>> allocator/regclass (IE get regclass to choose this new class as the 
>> preferred class so that the allocator makes a better decision later 
>> on)?
>>
>> I recently had another discussion with Gregory Chaitan about register 
>> allocation, and two things he was adamant about (that I was also 
>> somewhat strong feeling, but not as adamant about during design of 
>> new-ra):
>>
>> 1. The interference graph should represent all interference 
>> constraints necessary to do allocation in some way.  IE for variables 
>> that need multiple registers, this needs to be represented in the 
>> interference graph in some way (through either extra or weighted 
>> edges).
>> IE you should need nothing but a single bit test to determine whether 
>> two variables can share a register or not.
>> New-ra didn't follow this, and it became quite messy to try to 
>> determine whether two variables actually interfered, and what the 
>> possible registers we could use for these variables were.  This took 
>> away most of the benefits of using an interference graph in the first 
>> place.
>>
>> 2. That a lot of parameterization be done properly, so that costs are 
>> done right for each thing, and the allocator can make the right 
>> decisions.
>>
>>
>> In our case, that means that register classes (if we keep them) 
>> should represent only one thing, whereas right now it seems they can 
>> represent one of three things:
>>
>> 1. The set of registers possible for some given mode/usage.
>> 2. The set of registers good (but not all possibly usable registers 
>> for that mode/usage are included) for some given mode/usage.
>> 3. The set of registers good (but including  unusable registers for 
>> that mode/usage) are included.
>>
>> Have I missed anything (I haven't touched new-ra or old-ra in a year 
>> or so, so it's possibly i've lost it).
>> --Dan
>>
>

[-- Attachment #2: Type: text/enriched, Size: 3974 bytes --]

Oops, I forgot to copy the list on this message...


Begin forwarded message:


<excerpt><bold><color><param>0000,0000,0000</param>From:
</color></bold>Caroline Tice <<ctice@apple.com>

<bold><color><param>0000,0000,0000</param>Date: </color></bold>August
18, 2004 10:55:43 AM PDT

<bold><color><param>0000,0000,0000</param>To: </color></bold>Daniel
Berlin <<dberlin@dberlin.org>

<bold><color><param>0000,0000,0000</param>Subject: </color>Re:
Register classes

</bold>

If you are planning on doing some work on the register allocator,
there was an EXCELLENT paper in

PLDI this year (ACM Conference on Programming Language Design and
Implementation) on

updating Chaitin's algorithm to work well on modern architectures.  I
would strongly recommend you read it, if you haven't already.  I can
send you a copy if you like.  Below is my summary of the paper:


A Generalized Algorithm for Graph-Coloring Register Allocation

by M.D. Smith, N. Ramsey and G. Holloway


Expanding Chaitin's graph coloring algorithm to work on real hardware
architectures (taking into account

register classes, overlapping between register classes, register
aliasing, etc).  Basically, Chaitin said a

node in the coloring graph was trivially colorable if the number of
neighbors of N, "degree(N)" was less

than the number of registers on the machine.  The new formula says  
node is trivially colorable is

 "squeeze (N)" is less than the number of registers actually available
for allocation, where squeeze (N) is

the number of registers that N's neighbors will actually need.  The
rest of the paper is the concerned with

accurately defining "squeeze (N)" and "number of registers actually
available for allocation" taking the

various hardware architectures and constraints into account.


-- Caroline Tice

ctice@apple.com


On Aug 18, 2004, at 10:39 AM, Daniel Berlin wrote:


<excerpt>A whole lot of ports seem to have register classes that
contain registers that can't possibly be used together.

They also have to seem weird groupings of registers that don't make
sense to be used by any single pseudo.


What exactly is the goal of these register classes?

Is it to work around bad allocation decisions by the register
allocator/regclass (IE get regclass to choose this new class as the
preferred class so that the allocator makes a better decision later
on)?


I recently had another discussion with Gregory Chaitan about register
allocation, and two things he was adamant about (that I was also
somewhat strong feeling, but not as adamant about during design of
new-ra):


1. The interference graph should represent all interference
constraints necessary to do allocation in some way.  IE for variables
that need multiple registers, this needs to be represented in the
interference graph in some way (through either extra or weighted
edges).

IE you should need nothing but a single bit test to determine whether
two variables can share a register or not.

New-ra didn't follow this, and it became quite messy to try to
determine whether two variables actually interfered, and what the
possible registers we could use for these variables were.  This took
away most of the benefits of using an interference graph in the first
place.


2. That a lot of parameterization be done properly, so that costs are
done right for each thing, and the allocator can make the right
decisions.



In our case, that means that register classes (if we keep them) should
represent only one thing, whereas right now it seems they can
represent one of three things:


1. The set of registers possible for some given mode/usage.

2. The set of registers good (but not all possibly usable registers
for that mode/usage are included) for some given mode/usage.

3. The set of registers good (but including  unusable registers for
that mode/usage) are included.


Have I missed anything (I haven't touched new-ra or old-ra in a year
or so, so it's possibly i've lost it).

--Dan


</excerpt>

</excerpt>

Re: Register classes

[Daniel Berlin]

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


On Aug 18, 2004, at 2:05 PM, Caroline Tice wrote:

> Oops, I forgot to copy the list on this message...

Just so nobody has any doubts, i have no current plans to do anything 
to the register allocator.
I'm just trying to gather more information in case i decide to mount 
another future assault on it.

I should point out something from the below paper though:
"One of our key insights is that coloring constraints on each
interference-graph node should be expressed in terms of the set
of registers available to it. With this insight we produce a 
generalization
that handles simultaneous allocation of multiple register
classes and accommodates register aliasing in an elegant way. Because
allocators using our approach know about the set of registers
available to each node, they can recognize when overlap between
such sets would introduce inaccuracies in the criterion for 
colorability,
and thereby avoid the overcounting inherent in simpler
formulations."

This insight is something i have shared as well, and one of the reasons 
i've always hated regclasses. They don't give you this information, 
they give you "kinda sorta this information, sometimes".


> Begin forwarded message:
>
>> From: Caroline Tice <ctice@apple.com>
>> Date: August 18, 2004 10:55:43 AM PDT
>> To: Daniel Berlin <dberlin@dberlin.org>
>> Subject: Re: Register classes
>>
>> If you are planning on doing some work on the register allocator, 
>> there was an EXCELLENT paper in
>> PLDI this year (ACM Conference on Programming Language Design and 
>> Implementation) on
>> updating Chaitin's algorithm to work well on modern architectures.  I 
>> would strongly recommend you read it, if you haven't already.  I can 
>> send you a copy if you like.  Below is my summary of the paper:
>>
>> A Generalized Algorithm for Graph-Coloring Register Allocation
>> by M.D. Smith, N. Ramsey and G. Holloway
>>
>> Expanding Chaitin's graph coloring algorithm to work on real hardware 
>> architectures (taking into account
>> register classes, overlapping between register classes, register 
>> aliasing, etc).  Basically, Chaitin said a
>> node in the coloring graph was trivially colorable if the number of 
>> neighbors of N, "degree(N)" was less
>> than the number of registers on the machine.  The new formula says   
>> node is trivially colorable is
>>  "squeeze (N)" is less than the number of registers actually 
>> available for allocation, where squeeze (N) is
>> the number of registers that N's neighbors will actually need.  The 
>> rest of the paper is the concerned with
>> accurately defining "squeeze (N)" and "number of registers actually 
>> available for allocation" taking the
>> various hardware architectures and constraints into account.
>>
>> -- Caroline Tice
>> ctice@apple.com
>>
>> On Aug 18, 2004, at 10:39 AM, Daniel Berlin wrote:
>>
>>> A whole lot of ports seem to have register classes that contain 
>>> registers that can't possibly be used together.
>>> They also have to seem weird groupings of registers that don't make 
>>> sense to be used by any single pseudo.
>>>
>>> What exactly is the goal of these register classes?
>>> Is it to work around bad allocation decisions by the register 
>>> allocator/regclass (IE get regclass to choose this new class as the 
>>> preferred class so that the allocator makes a better decision later 
>>> on)?
>>>
>>> I recently had another discussion with Gregory Chaitan about 
>>> register allocation, and two things he was adamant about (that I was 
>>> also somewhat strong feeling, but not as adamant about during design 
>>> of new-ra):
>>>
>>> 1. The interference graph should represent all interference 
>>> constraints necessary to do allocation in some way.  IE for 
>>> variables that need multiple registers, this needs to be represented 
>>> in the interference graph in some way (through either extra or 
>>> weighted edges).
>>> IE you should need nothing but a single bit test to determine 
>>> whether two variables can share a register or not.
>>> New-ra didn't follow this, and it became quite messy to try to 
>>> determine whether two variables actually interfered, and what the 
>>> possible registers we could use for these variables were.  This took 
>>> away most of the benefits of using an interference graph in the 
>>> first place.
>>>
>>> 2. That a lot of parameterization be done properly, so that costs 
>>> are done right for each thing, and the allocator can make the right 
>>> decisions.
>>>
>>>
>>> In our case, that means that register classes (if we keep them) 
>>> should represent only one thing, whereas right now it seems they can 
>>> represent one of three things:
>>>
>>> 1. The set of registers possible for some given mode/usage.
>>> 2. The set of registers good (but not all possibly usable registers 
>>> for that mode/usage are included) for some given mode/usage.
>>> 3. The set of registers good (but including  unusable registers for 
>>> that mode/usage) are included.
>>>
>>> Have I missed anything (I haven't touched new-ra or old-ra in a year 
>>> or so, so it's possibly i've lost it).
>>> --Dan
>>>
>>

[-- Attachment #2: Type: text/enriched, Size: 5218 bytes --]



On Aug 18, 2004, at 2:05 PM, Caroline Tice wrote:


<excerpt>Oops, I forgot to copy the list on this message...

</excerpt>

Just so nobody has any doubts, i have no current plans to do anything
to the register allocator.

I'm just trying to gather more information in case i decide to mount
another future assault on it.


I should point out something from the below paper though: 

"<smaller><x-tad-smaller>One of our key insights is that coloring
constraints on each

</x-tad-smaller><x-tad-smaller>interference-graph node should be
expressed in terms of the set

of registers available to it. With this insight we produce a
generalization

that handles simultaneous allocation of multiple register

classes and accommodates register aliasing in an elegant way. Because

allocators using our approach know about the set of registers

available to each node, they can recognize when overlap between

such sets would introduce inaccuracies in the criterion for
colorability,

and thereby avoid the overcounting inherent in simpler

formulations.</x-tad-smaller></smaller>"


This insight is something i have shared as well, and one of the
reasons i've always hated regclasses. They don't give you this
information, they give you "kinda sorta this information, sometimes".



<excerpt>Begin forwarded message:


<excerpt><bold><color><param>0000,0000,0000</param>From:
</color></bold>Caroline Tice <<ctice@apple.com>

<bold><color><param>0000,0000,0000</param>Date: </color></bold>August
18, 2004 10:55:43 AM PDT

<bold><color><param>0000,0000,0000</param>To: </color></bold>Daniel
Berlin <<dberlin@dberlin.org>

<bold><color><param>0000,0000,0000</param>Subject: </color>Re:
Register classes

</bold>

If you are planning on doing some work on the register allocator,
there was an EXCELLENT paper in

PLDI this year (ACM Conference on Programming Language Design and
Implementation) on

updating Chaitin's algorithm to work well on modern architectures.  I
would strongly recommend you read it, if you haven't already.  I can
send you a copy if you like.  Below is my summary of the paper:


A Generalized Algorithm for Graph-Coloring Register Allocation

by M.D. Smith, N. Ramsey and G. Holloway


Expanding Chaitin's graph coloring algorithm to work on real hardware
architectures (taking into account

register classes, overlapping between register classes, register
aliasing, etc).  Basically, Chaitin said a

node in the coloring graph was trivially colorable if the number of
neighbors of N, "degree(N)" was less

than the number of registers on the machine.  The new formula says  
node is trivially colorable is

 "squeeze (N)" is less than the number of registers actually available
for allocation, where squeeze (N) is

the number of registers that N's neighbors will actually need.  The
rest of the paper is the concerned with

accurately defining "squeeze (N)" and "number of registers actually
available for allocation" taking the

various hardware architectures and constraints into account.


-- Caroline Tice

ctice@apple.com


On Aug 18, 2004, at 10:39 AM, Daniel Berlin wrote:


<excerpt>A whole lot of ports seem to have register classes that
contain registers that can't possibly be used together.

They also have to seem weird groupings of registers that don't make
sense to be used by any single pseudo.


What exactly is the goal of these register classes?

Is it to work around bad allocation decisions by the register
allocator/regclass (IE get regclass to choose this new class as the
preferred class so that the allocator makes a better decision later
on)?


I recently had another discussion with Gregory Chaitan about register
allocation, and two things he was adamant about (that I was also
somewhat strong feeling, but not as adamant about during design of
new-ra):


1. The interference graph should represent all interference
constraints necessary to do allocation in some way.  IE for variables
that need multiple registers, this needs to be represented in the
interference graph in some way (through either extra or weighted
edges).

IE you should need nothing but a single bit test to determine whether
two variables can share a register or not.

New-ra didn't follow this, and it became quite messy to try to
determine whether two variables actually interfered, and what the
possible registers we could use for these variables were.  This took
away most of the benefits of using an interference graph in the first
place.


2. That a lot of parameterization be done properly, so that costs are
done right for each thing, and the allocator can make the right
decisions.



In our case, that means that register classes (if we keep them) should
represent only one thing, whereas right now it seems they can
represent one of three things:


1. The set of registers possible for some given mode/usage.

2. The set of registers good (but not all possibly usable registers
for that mode/usage are included) for some given mode/usage.

3. The set of registers good (but including  unusable registers for
that mode/usage) are included.


Have I missed anything (I haven't touched new-ra or old-ra in a year
or so, so it's possibly i've lost it).

--Dan


</excerpt>

</excerpt></excerpt>

Re: Register classes

[Michael Matz]

Hi,

On Wed, 18 Aug 2004, Daniel Berlin wrote:

> Just so nobody has any doubts, i have no current plans to do anything to
> the register allocator. I'm just trying to gather more information in
> case i decide to mount another future assault on it.
> 
> I should point out something from the below paper though:

As this paper didn't yet show up in citeseer (it seems), I would be 
thankful for this paper.

Note that new-ra does not really use register classes for the interference 
graph, but instead register sets.

Trivially colorable nodes are still trivially colorable also in new-ra,
_as long_ as they only require one register, so I'm not exactly sure what
you were speaking about in your first mail.

The problem with multi-reg pseudos is a tradeoff.  If you exactly count 
the necessary registers you make your nodes unnesessarily non-trivial.  
One example:  suppose R needs two _consecutive_ hardregs and that there 
are N colors.  This node is only trivially colorable if it has N/2-1 
neighbors (instead of N-2 which on would think at first).  The problem is 
the consecutivness.  If it has N-2 neighbors that we can be sure that 
there are two arbitrary hardregs available, but not two consecutive.
N/2-1 is a big hammer to ensure trivial colorability, which makes much too 
many nodes spilled than later necessary.

So, I choose another solution, by also popping it off the stack if it has 
<= N-2 neighbors.  But then I have to live and cope with the fact that 
this node might not get its two free consecutive hardregs.  And to make 
the effect of this less noticable (i.e. increasing the probability of it 
finding the two colors) there are some heuristics added.

Maybe you speak about this complexity.  But IMHO the coloring of the graph 
itself is still reasonable clean.  The other complexity is due to the way 
how it tries to avoid spilling must-get-a-color webs (which are of 
different classes, like short-living ones, or those with only one register 
possible and such).  Due to the above some simplified webs do not fall 
into the category, and some do.

> "One of our key insights is that coloring constraints on each
> interference-graph node should be expressed in terms of the set

Without having read the paper, at least this part I think is basically 
implemented in new-ra.  Sometimes we still use the regclasses for 
preferring some regs.  And of course when looking on the constraints of an 
insn you have to deal with regclasses.


Ciao,
Michael.

Re: Register classes

[Daniel Berlin]

On Aug 19, 2004, at 8:56 AM, Michael Matz wrote:

> Hi,
>
> On Wed, 18 Aug 2004, Daniel Berlin wrote:
>
>> Just so nobody has any doubts, i have no current plans to do anything 
>> to
>> the register allocator. I'm just trying to gather more information in
>> case i decide to mount another future assault on it.
>>
>> I should point out something from the below paper though:
>
> As this paper didn't yet show up in citeseer (it seems), I would be
> thankful for this paper.
>
I'll send it to you.

> Note that new-ra does not really use register classes for the 
> interference
> graph, but instead register sets.
>
Except they are taken from register classes.

> Trivially colorable nodes are still trivially colorable also in new-ra,
> _as long_ as they only require one register, so I'm not exactly sure 
> what
> you were speaking about in your first mail.

Uh, handling multi-regs is something very ugly in new-ra right now.
Also, the interference graph in new-ra is split into two graphs, which 
is also a bad idea.
(sup_igraph and igraph).

>> "One of our key insights is that coloring constraints on each
>> interference-graph node should be expressed in terms of the set
>
> Without having read the paper, at least this part I think is basically
> implemented in new-ra.

But it's not, because we don't gracefully handle multi-reg pseudos and 
whatnot simply by using the interference graph.  We go through all 
kinds of contortions.

>   Sometimes we still use the regclasses for
> preferring some regs.  And of course when looking on the constraints 
> of an
> insn you have to deal with regclasses.
>
>
> Ciao,
> Michael.

Re: Register classes

[Denis Chertykov]

Daniel Berlin <dberlin@dberlin.org> writes:

> On Aug 19, 2004, at 8:56 AM, Michael Matz wrote:
> 
> > Hi,
> >
> > On Wed, 18 Aug 2004, Daniel Berlin wrote:
> >
> >> Just so nobody has any doubts, i have no current plans to do
> >> anything to
> >> the register allocator. I'm just trying to gather more information in
> >> case i decide to mount another future assault on it.
> >>
> >> I should point out something from the below paper though:
> >
> > As this paper didn't yet show up in citeseer (it seems), I would be
> > thankful for this paper.
> >
> I'll send it to you.
> 
> > Note that new-ra does not really use register classes for the
> > interference
> > graph, but instead register sets.
> >
> Except they are taken from register classes.

The register sets are taken from register classes and new-ra use
register sets for interference graph. Even more new-ra tracks useless
conflicts. This is conflicts between webs with nonintersected
register sets but intersected live ranges.

Denis.

Register classes

[Daniel Berlin]

A whole lot of ports seem to have register classes that contain 
registers that can't possibly be used together.
They also have to seem weird groupings of registers that don't make 
sense to be used by any single pseudo.

What exactly is the goal of these register classes?
Is it to work around bad allocation decisions by the register 
allocator/regclass (IE get regclass to choose this new class as the 
preferred class so that the allocator makes a better decision later 
on)?

I recently had another discussion with Gregory Chaitan about register 
allocation, and two things he was adamant about (that I was also 
somewhat strong feeling, but not as adamant about during design of 
new-ra):

1. The interference graph should represent all interference constraints 
necessary to do allocation in some way.  IE for variables that need 
multiple registers, this needs to be represented in the interference 
graph in some way (through either extra or weighted edges).
IE you should need nothing but a single bit test to determine whether 
two variables can share a register or not.
New-ra didn't follow this, and it became quite messy to try to 
determine whether two variables actually interfered, and what the 
possible registers we could use for these variables were.  This took 
away most of the benefits of using an interference graph in the first 
place.

2. That a lot of parameterization be done properly, so that costs are 
done right for each thing, and the allocator can make the right 
decisions.


In our case, that means that register classes (if we keep them) should 
represent only one thing, whereas right now it seems they can represent 
one of three things:

1. The set of registers possible for some given mode/usage.
2. The set of registers good (but not all possibly usable registers for 
that mode/usage are included) for some given mode/usage.
3. The set of registers good (but including  unusable registers for 
that mode/usage) are included.

Have I missed anything (I haven't touched new-ra or old-ra in a year or 
so, so it's possibly i've lost it).
--Dan

Re: Register classes

[James E Wilson]

Daniel Berlin wrote:
> A whole lot of ports seem to have register classes that contain 
> registers that can't possibly be used together.
> They also have to seem weird groupings of registers that don't make 
> sense to be used by any single pseudo.

This is because of interactions between the register preferences 
computed by regclass and the register allocator.

The register preferencing works by looking at the instructions that use 
a pseudo, looking at the register classes preferred by these 
instructions, and then forming unions/intersections to determine the 
best class to allocate a register to.  If you don't have register 
classes to represent the union/intersection of other register classes, 
then you can end up with suboptimal results.  In some extreme cases, a 
port may fail in reload if a union/intersection class isn't there.  This 
is sometimes a problem for embedded targets with small register sets, 
and lots of registers with special purposes.  See the subunion and 
superunion stuff in regclass.c for some of the stuff that is done with 
register classes.

Suppose you have a pseudo that is used in only two instructions.  One 
instruction requires the pseudo to be in class A.  The other requires it 
to be in class B.  The two classes don't intersect.  Neither class is 
better.  The best class to use would be the union of class A and B, 
which then lets the register allocator choose a hard reg from either 
class, depending on other factors, such as which class has less register 
pressure.  If you don't have the union reg class, then regclass must 
arbitrarily pick one (I think it picks the lower numbered one?), and 
this may result in suboptimal code if this forces an otherwise 
unnecessary spill.

Also, in some cases, it is useful to have classes that represent the 
difference of two classes.  Suppose you have a couple of registers with 
special purposes that cause them to have high register pressure.  Then 
you may be able to improve results by creating register classes with 
those registers subtracted out, and then using hooks to force the 
difference class to be used when possible, to reduce register pressure 
on the special purpose registers.  Again, this is more likely to be 
useful for an embedded target with a small number of registers and a set 
of registers with special purposes.
-- 
Jim Wilson, GNU Tools Support, http://www.SpecifixInc.com

Re: Register classes

[Daniel Berlin]

On Aug 19, 2004, at 9:53 PM, James E Wilson wrote:

> Daniel Berlin wrote:
>> A whole lot of ports seem to have register classes that contain 
>> registers that can't possibly be used together.
>> They also have to seem weird groupings of registers that don't make 
>> sense to be used by any single pseudo.
>
> This is because of interactions between the register preferences 
> computed by regclass and the register allocator.
>
IOW, it's done to try to get better performance out of the register 
allocator.
:)
--Dan