This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Mainline space problem
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