Register classes

[Daniel Berlin]

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