This is the mail archive of the
mailing list for the GCC project.
Re: What to do with new-ra for GCC 4.0
- From: "Sam Lauber" <sam124 at operamail dot com>
- To: gcc at gcc dot gnu dot org
- Date: Sat, 08 Jan 2005 07:39:34 +0100
- Subject: Re: What to do with new-ra for GCC 4.0
> 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
> 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.
> 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.
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
Web-based SMS services available at http://www.operamail.com.
From your mailbox to local or overseas cell phones.
Powered by Outblaze