Re: Register Pressure in Instruction Level Parallelism (fwd)

[Daniel Berlin <dberlin at dberlin dot org>]

On Monday, July 15, 2002, at 08:37  AM, Andrew Haley wrote:

> Daniel Berlin writes:
> > On Mon, 15 Jul 2002, Andrew Haley wrote:
> >
> > > Robert Dewar writes:
> > > > It is entirely unrealistic to insist that register allocation and
> > > > scheduling be linear or n*logn if you want good results.
> > > In his PhD thesis, Perston Briggs wrote that "in practice, the time
> > > required by the Yorktown allocator is O(n log n), where n is the size
> > > of the routine."  Do more recent allocators have time complexity that
> > > is so much worse?
> > Well, actually, yes.
> > The yorktown allocator only performs one pass of coloring, to save 
> > time,
> > at the expense of slightly better allocation.
> >
> > Robert's assertion is perfectly reasonable.
> I suppose all this hinges on what exactly is meant by "good results".
> An algorithm that is slightly worse than the best but is O(n log n)
> seems like a sensible choice for gcc.
Let's be clear here.
There are few O(n log n) algorithms for scheduling and register 
allocation that are "slightly worse than the best".
They are often O(n log n) "most of the time", but O(n^2) or worse, 
worst case.  And the worst case isn't all that uncommon.

You can't even get good approximations of things like a graph's 
chromatic number in reasonable amounts of time, let alone color it well.

When I say "slightly worse than the best", of course,I mean RA on x86.  
For other, >3 usable register architectures, it's a much easier problem 
to handle, since spill code algorithms come into play a *lot* less.

> Of course that doesn't forbid
> gcc from providing something better as a special option.
>
> Andrew.