Debugging info on # spills?

[Daniel Berlin]

On Apr 7, 2004, at 9:37 AM, Michael Matz wrote:

> Hi,
>
> On Tue, 6 Apr 2004, Timothy J. Wood wrote:
>
>>   Is there some gcc option I can use that would allow me to determine
>> how many 'extra' registers would be necessary to allow my function to
>> run with zero spilling?
>
> Not really, no.  Solving it optimally is NP complete.

This actually doesn't appear to be true for all register interference 
graphs generated by GCC (and other compilers for that matter).
See "Register Allocation by Optimal Graph Coloring" for some statistics.
As I emailed Tim in private mail, I also tested this theory on all 
register interference graphs generated by GCC during bootstrap, make 
check, and compiling some random large programs i had.
They were all 1-perfect as well.

--Dan