Debugging info on # spills?

[Vladimir Makarov]

Daniel Berlin wrote:

>
> 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.
>
  Even if you can solve optimaly graph colouring problem, it is probably 
not what Tim asked.

  The optimal graph colouring is just one of the register allocation 
problems (probably not the most complex).  Accoring to the solution a 
register is supposed to be allocated in one hard register or in memory. 
 Most register allocators can place register in different hard-registers 
(or in memory partially) making live range splitting and or web spliting 
.  Also optimal graph coloring problem is simplified in sense of 
register classes.  Gcc has more powerfull register model.  According to 
this model the same pseudo-register  sometimes has to be placed in 
different non-intersected classes, it will require register moving 
sometimes through memory (secondary reloads) if there is no direct 
moving one class register to another one.

   Moreover gcc sometimes will always place pseudo-register in memory 
even if there are enough hard-regiseters because it will be more 
profitable (e.g. an x86 argument pseudo-register passed through stack 
and used only once).

  Also with my point of view the problem is formulated inaccurately.   
What dose `extra' registers mean?   What classes?
  So even if spills mean spills generated by reload and the problem will 
be formulated more accurately, in general writing code finding minimal 
number of hard registers enough for compiling programs by gcc without 
"spilling"  will be a difficult task.   And moreover the algorithm will 
be slow too.

Vlad