This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Register Pressure in Instruction Level Parallelism (fwd)
- From: dewar at gnat dot com (Robert Dewar)
- To: aph at cambridge dot redhat dot com, dewar at gnat dot com
- Cc: duraid at fl dot net dot au, gcc at gcc dot gnu dot org, geoffk at geoffk dot org
- Date: Tue, 16 Jul 2002 06:25:41 -0400 (EDT)
- Subject: Re: Register Pressure in Instruction Level Parallelism (fwd)
<<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?
>>
A lot depends on whether you talk about the average performance or
worst case performance. Many modern algorithms for register allocation
and scheduling (the best algorithms do both at the same time) are worse
than NlogN in the worst case, but may do much better in the average case
which is probably what counts.