Re: [RFA] The Integrated Register Allocator

[Kenneth Zadeck <Kenneth dot Zadeck at NaturalBridge dot com>]

I have made a cursory look over the code, and there are some things
that I like about the new allocator and some things that cause me
great concern.

The thing that I like about it is that some of the parts of it are
true steps forward.  The thing that bothers me is that there is not
just some backward steps but there appear to be a lot of sideways
steps.  

When we committed the actual dataflow branch, the patch was about
twice as large as this one, but to a very large extent, it was a
finished project.  Certainly there were loose ends and fixes on minor
ports, but the dataflow branch essentially replaced the existing
dataflow, and there was nothing (or at least very little) left of the
old framework.

Here we have a patch that inserts a new allocator, but the old one has
been left "largely" in place.   While the dataflow branch did not work
on ever supported target when it was committed, we had at least tested
it ourselves or had it tested on almost every platform (except the
vax, knuth's machine and the mc6810).   Furthermore there was a
commitment to the steering committee and the community that we would
either fix ourselves or at least help with the problems that arose on
all of the active platforms and by the time that stage 2 closed, we
had pretty much accomplished this.

I am especially concerned that this patch is setting up for something
that is going to make the continued maintenance of reload, which is at
the core of the rtl level of the compiler, much more difficult because
there are now two completely separate code paths thru it that need to
be kept working.  I understand that gcc has passes that are optional
for individual targets and that this is what is necessary, but none of
them are as intertwined in the core rtl machinery as this patch.  If
the plan is that by the end of this release that we are going to be
there, then this particular objection is moot.

On the other hand, if the plan is to have two register allocators for
the foreseeable future, this patch raises several troubling issues in
addition to reload: for instance, the new allocator seems to use sets
of registers rather than register classes.  I think that this is an
excellent idea.  However, if we are going to live with both allocators
for a long time, then we should make global use the same data
structure.   This will allow the continued evolution or removal of
passes that feed into the ra stack.

My next concern is that the new allocator seems to be a large
regression with respect to building conflict graphs.  Peter Bergner
and my self have spent a lot of time replacing the conflict builder in
global with a modern algorithm that is both efficient and very
precise, and yet this patch essentially regresses back to the
technology used in global before we started.  In general the problem
is that this work seems to have started from where we were three years
ago and there has been minimal work to keep up with the improvements
that have surrounded the register allocator.  While I am certainly for
an allocator that improves the quality of code that is generated,
I wonder how much better it could have been had it integrated the
other improvements rather than simply replaced them.

GCC is a moving target, and certainly I learned on the dataflow branch
that if you do not continually track the changes that are happening in
the rest of the compiler and the community, you run into these kinds
of issues.   

I think that there needs to be an explicit plan as to both how and how
quickly we are going to seamlessly integrate this technology.  The
patch as it stands as something to just be bolted onto the side of gcc
is not really acceptable.

I would personally love to see a series of patches that do things like
change the entire compiler from register classes to register sets.  I
think that some of the changes that vlad makes are long overdue.  Such
of series of patches would allow the community to move forward with
other changes in the compiler, but to have to live with will become a
pastiche of technologies I believe is going to cause more problems
than it is going to solve.

I personally dislike the Chow based approach, but if the improvements
stand over what we currently have, then I am willing to let it go.
My primary concern is that the integration is so superficial that it
will be years before we can move forward after this.
 
Kenny