Fwd: Register classes

[Caroline Tice]

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
>>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/enriched
Size: 3974 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc/attachments/20040818/8532ad9d/attachment.bin>