Re: What to do with new-ra for GCC 4.0

[Daniel Berlin <dberlin at dberlin dot org>]

> Well nobody wants to update which is why it got bit rotten like
> most other source which gets bit rotten.
> If you want to debug it and fix it, go ahead but nobody else
> wanted to do it.

This is in part, because it is so fundamentally wrongly engineered at 
this point it's not worth saving.
1. We support probably 10 different types of coalescing, spilling, and 
coloring mechanisms.
This by itself is not bad.  The fact that they are all smashed together in 
the same code, instead of using some sane technique like function 
pointers, or whatever, to replace compatible pieces with other compatible 
pieces (biased coloring vs non-biased coloring), means that debugging it 
is a mess.  Using 30 flags to control the exact behavior of the allocator 
code, with a ridiculous number of ifs in the code itself based on these 
flags, is not the way to go.

2. You can't replace pieces of new-ra with 
other pieces, because there is no documented interface between them.  I 
dare you to replace the graph reducer and color chooser, and then go try 
to discover  why it is you suddenly start getting infinite loops.

3.   The incremental liveness calculation has the absolute worst cache 
behavior of anything in the compiler (unfortunate, but true. Steven 
Bosscher can back me up on this).  Michael believed that we could make 
incremental updating and liveness fast enough for it to be practical for 
us to iterate the register allocation.  So far this has been incorrect, 
and i don't see this changing anytime soon.  I don't blame Michael for 
this, it just happens to be a fact of the way things are.

The combination of these things and others, has made new-ra itself slow, 
bloated, and buggy (because every data structure carries a *lot* of 
info, and nobody verifies that the info is correct until something bad 
happens :P).

If one stops new-ra from iterating, it actually isn't *that* much slower 
than the current allocator.  It also doesn't produce significantly worse 
code.

However, the design and implementation issues above (and others) make it 
not worth saving.

It's not particularly hard to implement the algorithmic parts of the 
register allocator.  I'd rather see a new one, designed and engineered 
right, for the non-algorithmic parts.

In particular, the interference graph itself, the interference 
graph building, coloring, and spilling should all be completely separate 
components that have some sanely engineered interface between each other 
so that one can replace the spiller or the color chooser in a target 
without trouble.  I know for a fact this is possible, because IBM's 
backend does it.  They have a multitude of spill choosers, color choosers, 
and interference graph builders, all as nice C++ classes that derive from 
a simple interface.
They also reuse the interference graph for other optimizations, which is 
why it is a seperate component.

All of this is meaningless however, because the register allocator part 
of register allocation just isn't that hard, and isn't the real problem 
in gcc.   Yes you have to have some nice way of calculating liveness, and 
of handling multiple hard  registers, but that is nothing compared to the 
real elephant in the  room, which is reload.

Nobody wants to go near reload or try an rtl with constraints 
better amenable to register allocation with a 10 foot pole 
because they are afraid of breaking every non-very-actively maintained 
port in existence, when this is simply something that is likely to have to 
happen to replace or significantly rewrite reload[1].

Until someone is willing to step up to the plate and do that, regardless 
of the fact that they will probably become the single most hated person in 
gcc by port maintainers (:P), nothing will happen.

--Dan

PS Just in case anyone thinks i'm being overcritical of thoes involved in 
new-ra, please realize that I myself was relatively involved in new-ra, so 
all of the above criticisms apply to me.  I learned a lot from its 
failure, and hopefully others have to.  Without "post-mortems" of gcc 
projects that don't make it, nobody will ever get better so that we get it 
right the next time.