Register Pressure in Instruction Level Parallelism (fwd)

[Andrew Haley]

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.  Of course that doesn't forbid
gcc from providing something better as a special option.

Andrew.