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

["Sam Lauber" <sam124 at operamail dot com>]

> 1. We support probably 10 different types of coalescing, spilling, 
> and coloring mechanisms.
I think that's bad. A better design would be a few diffrent
types of that kind of thing that contain parts of all of the
others.

> 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).
Add some code that causes it to save the data structures,
rerun the RA code a few times, and check if it is correct by
comparing those structures.

> 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.
Follow suit.

> 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. 
What 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].
Oh, good grief!

> 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.
Who?

Samuel Lauber
-- 
_____________________________________________________________
Web-based SMS services available at http://www.operamail.com.
From your mailbox to local or overseas cell phones.

Powered by Outblaze