This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Fwd: Register classes
- From: Caroline Tice <ctice at apple dot com>
- To: gcc at gcc dot gnu dot org
- Date: Wed, 18 Aug 2004 11:05:32 -0700
- Subject: Fwd: Register classes
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