GCSE memory usage

[Mark Mitchell <mark at codesourcery dot com>]

GCSE is eating tons of memory on some test-cases I have.  The culprit
seems to be the use of sbitmaps; when you've got 264,772 pseudos,
967,369 instructions, and 15,600 basic blocks in a function, GCSE
wants sbitmaps that take four sbitmaps that take up 500 megabytes.  On
the test machines, I've got a 2GB hard memory limit (these are
machines with 32GB of real physical memory), and I lose.  Other
compilers are able to generate far better code than GCC using only a
couple of hundred megabytes.

It's very important that we find a way to get these kinds of programs
to compile, for two reasons.  One is that the use of
expression-templates is becoming very common in the scientific
community; if we are unable to optimize that kind of code, g++ is
simply not going to be an acceptable choice in that community.

GCSE will be very important here since these huge functions are the
result of massive inlining on template functions; there are lots of
calls to the same functions with the same inputs, yielding lots of
common sub-expressions.  So, in order to get good performance, we
cannot simply throttle GCSE off.

Most of the entries in the sbitmaps are going to be zero; very few of
the pseudos are live across many blocks.  So, we need a sparse bitmap
representation.  I propose changing the "big" arrays (i.e., those that
depend on the number of pseudos or instructions) to use bitmap.[hc]
rather than sbitmap.[hc].

Admittedly, this will slow down the compiler somewhat for smaller
cases, since the bitmap accesses will be slower.  On the other hand,
for smaller cases, the amount of time spent in GCSE is not so long, so
we'll not lose noticeably.  And, I've observed GCSE to cause
significant thrashing even on reasonably small test-cases on machines
with more average size memories.  Furthermore, I bet these bitmaps are
sparse even on smaller cases, so we'll recoup some of the losses in
not having to initialize and bitwise-and/or so much data.

Any objections?  I'm also willing to code this conditionally in some
way, if people really think the use of ordinary bitmaps, rather than
sbitmaps, will slow down the smaller cases substantially.

--
Mark Mitchell                   mark@codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com