Re: An unusual Performance approach using Synthetic registers

[Daniel Berlin <dberlin at dberlin dot org>]

> BTW: Is there a good way to figure out how much registers the compiler
> could have used sensibly if they were available?
Good way?
no.
You are effectively trying to figure out the chromatic number of the 
graph (The smallest number of colors necessary to color the graph).
Determining this number is NP-hard.
Approximating it is in NP.
It is known that, unless coRP = NP , there is no polynomial time 
algorithm which approximates any of these quantities within a factor of 
n^(1-epsilon) for graphs on n vertices, for any fixed episilon > 0.

In other words, worst case, you can't even *approximate* this number 
with reasonable accuracy in polynomial time.
That's bad.
:)

> It's easy to count the
> numbers of virtual registers allocated after the optimisation passes
> but this number does not account for intersecting behaviour when
> registers have to be saved and restored to make room for a different
> content.