This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Project RABLET

Last fall I produced the RABLE document which described the approach I
thought should be taken to write a new register allocator for GCC.

A new register allocator written from scratch is a very long term
project (measured in years), and there is no guarantee after all that
work that we'd end up with something which is remarkably better. One
would hope that it is a lot more maintainable, but the generated code is
a crapshot. It will surely look better but will it really run faster?
The current plate of spaghetti we call the register allocator has had a
lot of fine tuning go into it over the years, and it generally generates
pretty darn good code IF it doesn't have to spill much, which is much of
the time.

This describes my current work-in-progress, RABLET, which stands for
RABLE-Themes, and conveniently implies something smaller. Rather than
write a new allocator, I think there are things we can do that are a lot
less work which will reap many of the benefits. This works from the
premise that we generate good code when we don't have to spill, so try
to detect early that we are going to spill and do something about it at
a point where we have good analysis.


1 - One of the core themes in RABLE was very early selection of
instructions from patterns.  RTL patterns are initially chosen by the
EXPAND pass. EXPAND tends to generates better rtl patterns by being
handed complex trees which it can process and get better combinations.

  When TREE-SSA was first implemented, we got very poor RTL because
expand was seeing very small trees.  TER (Temporary Expression
Replacement) was invented, which mashed any single-def/single-use
ssa_names together into more complex trees. This gave expand a better
chance of selecting better instructions, and made a huge difference.

2 - Rematerialization/register pressure reduction was another major
component.  The tree-ssa optimizers pay no attention to potential
register pressure (which is as it should be). This sometimes results in
very high register pressure entering the back end.  RABLE defined passes
performing expression rematerialization and other register pressure
reducing techniques to reduce excessive register pressure before
actually trying to do allocation.  If you have 120 register live at some
point, and only 16 physical registers, the allocator is clearly going to
have a difficult time. Try to present it with something more manageable.


On to the meat of the subject. RABLET involves reworking the out-of-ssa
pass, rewriting expand such that it is tightly integrated with the
out-of-ssa pass, and adding some new work to reduce register pressure.
Thats a lot less work than a whole new register allocator.

If we look at the RABLE architecture, the passes before global
allocation are as follows:

Register coalescing
register pressure reduction
<.. then regular register allocation activity ...>

In the context of RABLET:

-Out of SSA naturally performs live range disjointing.
-Initial RTL pattern selection is performed by expand.
-Register coalescing -  ssa_name coalescing is done by out-of-ssa, and
ssa_name == register.
-Register pressure reduction â This is new work which would be

If we create a new black box super pass called
out-of-ssa-expand-register-pressure-reducer,  (ewww,  lets just refer to
it as ssa-to-rtl :-),  then we'd have something close to the first part
of RABLE. Not exactly of course, because 'instruction selection' means
something slightly different.  In RABLE it means choosing an instruction
alternative from an RTL pattern , in RABLET it simple means "choose good
RTL patterns".

âBut wait...â I hear some clever person saying... âA lot of things
happen between ssa-to-rtl and global register allocation.â.  Hold that
thought until I get through describing ssa-to-rtl since there are some
important considerations which affect that discussion


When out-of-ssa was originally written, tree-ssa was still evolving. We
didnt know exactly what was going to be expected of it, so it was
written to be flexible and had a lot of gorp added after the fact.
TREE-SSA is now mature and we understand much more fully what is
expected of translation out of ssa. I have begun rewriting it to be
smaller and faster and to eliminate all the unused features which were
initially provided.  It is also being rewritten with RABLET in mind.  

The new generation out-of-ssa will eliminate PHIs, much as it does
today. This is done by coalescing together ssa_names connected by copies
(and PHIs are just copies), and issuing copies on edges required by the
PHIs.  Instead of  then mapping these back to VAR_DECLs and writing this
all back to the trees, it will simply be maintained in a partition list
map.  This is *key*. At this point, we have a mapping of what ssa_names
have been coalesced together, and the copies required to perform this.
The trees themselves are unaltered, which means we are STILL IN SSA

OK, why is that so important. That means we still have all the SSA live
range and data flow information which we can use to generate RTL insns.
Today,  expand produces better instructions selections by seeing larger
hunks of trees at one. If expand is rewritten to be ssa-aware, then it
can paw back through the IL to see what stmts and instructions feed this
stmt. It can look at as large a hunk  of the program as it sees fit.
When it actually generates RTL, it will use the partition map to
determine what ssa_names variables are actually substituted into the RTL

âInteresting, but why is that so grand?â.  A couple of reasons.  One is
that RTL doesn't have to be generated linearly in complete absence of
flow information.  We can generate code for a stmt, attach it to the
stmt, and at a later stmt, determine that it would be better to combine
it some other way and remove/modify the RTL that was first generated. It
can also look forward to see how this stmt is going to be used, and how
often in making decisions.  Another nice feature is that it still has
flow/use info for a variable. So if 'A' requires a load from a base
register, we can tell if that base register has already been loaded, and
where.  If register pressure is high, it can force a new load of the
base register thus splitting the live range.  Which then brings home the
point that we can look at the rtl being generated, and overlay what we
know about the SSA_NAMES over the register being generated. Its not
truly RTL-SSA, but it gives us some information to work with as
addressing modes are exposed.

Furthermore, we can calculate more accurate register pressure at this
point, which can help to determine the code we generate. For instance,
local variables are all turned into registers today. If the register
pressure is high, we could elect instead to load the local from its
stack location instead of leaving it in a register all the time. This
would prevent the register allocator fro having to perform this spill.
Instead, we get a load from the home address.

That's a flavor of what combining out-of-ssa and expand can do. I'm not
terribly familiar with expand (yet), so there will be other things come
up Im sure.  As well as issues. This is just the initial plan.


On to the register pressure reduction component. As mentioned, some
small level of register pressure reduction can be done during the rtl
expansion phase.  We can do some higher level work just before expansion
to rtl. Once we have the ssa_name mappings, we can do rough register
pressure calculations. Integer ssa_names are 1 int register, double ints
are two, etc. This would not take into account any extra registers
exposed by addressing modes and expansion, but it can give you a rough
idea if pressure is excessive or not. 25 lives values and 6 hardware
registers could use some register pressure reduction!

So register pressure calculations atr implemented, and then the same
techniques RABLE would have used, rematerialization, live range
splitting, pre-spilling, etc., ON SSA FORM. This makes the
implementation much easier since it becomes simply another ssa pass,
with some minor caveats.  There are some minor issues to resolve, but in
general, any of these types of operations will result in new local
temporary registers which don't coalesce with any other partition, and
results in exactly what RABLE would have done. The bonus is that it is
performed *before* RTL expansion , so we should get better instruction

And that forms the new ssa-to-rtl pass.  A side effect of this is that I
am suddenly very interested in the work done earlier (Honza was it?) to
make opt0 go into ssa and do a few basic optimizations before generating
rtl.  If expand is going to be swallowed by ssa-to-rtl, we wont want to
keep the old expand around for non-optimized code.

Back to that earlier observation, âBut wait, A lot of things happen
between ssa-to-rtl and global register allocation.â

If we substitute ssa-to-rtl into the RABLE architecture flow, it looks
something like:

spill cost analysis
global allocation
spill location optimizer
instruction rewriter.

Since RABLET doesn't propose writing RABLE as such, we'll just have to
substitute in the current register allocator passes for the RABLE ones.

What about all the stuff in between? CSE, GCSE, scheduling, and all

If expand is made much smarter, I would argue that much of GCSE and CSE
isn't needed.  We've already performed those optimizations at  a high
level, and we can hopefully do a lot of the factoring and things on
addressing registers exposed during expand.  I'm sure there are other
things to do, but I would argue that they are significantly less than a
"general purpose" CSE and GCSE pass. And in the cases of high register
pressure, how much would you want them to do anyway?  Its really these
high register pressure areas that RABLET is attacking anyway.

If I recall, scheduling is register pressure aware and normally doesn't
increase register pressure dramatically. If it does increase pressure,
well, this won't solve every problem after all.

I don't see the need for anything between RTl generation and
scheduling/register allocation that would undo all the work done in
ssa-to-rtl.  We may still have need for some RTL optimizations, sure,
but their impact on register pressure is likely to be minimal, and
should be so. Those that can increase pressure, like CSE and GCSE either
arent needed, or can be handcuffed. (ie, don't work on registers which
have been handled by ssa already, only look at registers that are not
flagged as   'optimized' by the ssa-to-rtl phase, or dont run on areas
where register pressure is above a threshold value, etc.).  There are
multiple options which can be considered.

Based on that, I would argue that all those things between ssa-to-rtl
and the register allocator are irrelevant as far as undoing the register
pressure reductions done in RABLET.  This makes the point of view on RTL
optimizations to be more like âdo good things only to registers which
earlier optimizations couldn't seeâ, noting that ssa-to-rtl does more
optimizations to rtl registers than expand did by itself.


Thats the project in a nutshell.  There are quite a few more details of
course, but that's the gist. Its not a perfect implementation of RABLE
of course, but it takes the major themes, and with a small shoe-horn,
you can fit the description of RABLET into the architectural diagram of
RABLE. The hope is that although we certainly wont see 100% of the
benefit of RABLE, we will see enough benefit to justify this work and
perhaps make RABLE unnecessary.  If work on RABLE begins (or some other
new allocator arrives...), it will still be presented with something
better to work with than we have today, making its job easier.  Well, at
least making the job of allocating registers easier, although it might
be a more difficult job to get performance gains :-P. 

Unlike RABLE, I am currently working on RABLET, with the out-of-ssa
rewrite underway.  The new out-of-ssa will be ready for GCC 4.3. It
should be faster and not suffer from slowdowns in some of the
pathological cases we've found with the current implementation. 

Once that is complete, the next step is to do some of the higher level
register pressure reduction work in SSA.  Combined with TER as it exists
today (with perhaps a few modifications), I would expect to see some
benefit in the generated code simply due to RA not having as much
pressure to deal with. There is some possibility this will make it into
4.3 as well, but that's not a sure thing. There is also the impact
MEM-SSA will have on this pass, which is not clear at this point.

Then its time for the integration of expand.  I really don't know how
long that would take, but I am pretty sure that's not in the 4.3 time
frame! :-)  When tree-ssa was first implemented, a rewrite of expand was
on the table as eventually being needed (as well as a new allocator).
TER was  stopgap solution until it could be tackled, and I doubt anyone
will be sorry to see it go! :-)

I'd be more than happy to respond to any useful feedback anyone might
have. As I said, I didn't delve deeply into some of the details,  and I
can think of half a dozen obvious questions/concerns people might have.
With a much shorter time frame, I think there will be enough benefit
from this project to reduce the urgency of a new register allocator, at
least from a performance point of view.  As always with compilers, you
can never be 100% sure :-)

I am not actually attending the conference in Ottawa next week, but I
will be in Ottawa late Tuesday afternoon through Wednesday night if
anyone wants to track me down, (or arrange to meet up with me), to
discuss any of this. (Or even RABLE for that matter).


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]