Mainline space problem

[Daniel Berlin]

On Mon, 30 Aug 2004, James E Wilson wrote:

> Bradley Lucier wrote:
>> It would be nice if someone could try to fix the problem here.  I don't 
>> know why it's still marked as UNCONFIRMED when Andrew has noted the 
>> precise allocation that fails.
>
> The problem Andrew pointed out isn't something that can be fixed. global 
> builds a conflict matrix that is quadratic in number of pseudos.  So if you 
> have 100K+ pseudos, then you need 2GB+ of memory.  This can't be fixed, at 
> least not in global.

Only if the conflict matrix is
1. Dense.
2. Bidirectional.

Otherwise, you could use sparse bitmaps (in case of 1 not being gtrue) , 
and/or a lower-triangular bitmatrix (in case of 2 not being true).

Unless global is doing something completely weird (it may be, i haven't 
looked at since i worked on new-ra), the conflict matrix is unidirectional 
(IE if x conflicts with y, then y must conflict with x).
Thus you can use a lower-triangular bitmatrix, and save half the 
memory.
.
This is a standard technique for interference graphs in graph coloring 
register allocators.

See http://citeseer.ist.psu.edu/cooper88how.html
(It's a little out of date these days, but still goes over this stuff).

--Dan