Re: [PATCH]: Efficient sbitmap based bitset

[Daniel Berlin <dan at cgsoftware dot com>]

Richard Henderson <rth@redhat.com> writes:

> On Wed, Aug 22, 2001 at 02:05:57PM -0400, Daniel Berlin wrote:
> > > Which seems more than sufficient.  If we need more than 500M bits
>> > for a regset, we're in bigger trouble.
>> I'm not so sure about that.
>> The new register allocator, on 20001226-1.c, creates an interference
>> graph bitmatrix of ~300M bits.
>> However, i'm not so sure how common code that has 15000 defs in a
>> single function is (IE whether we'd hit the limit).
>
> It's not entirely uncommon.  Seems like having a provision for
> triple indirection is warrented then.
Sigh.
Sorry, but it turns out 2048 (and even 1024) bytes minimum allocation
is too large.

For the unoptimized version of 1226, we have 15896 basic blocks (for
optimized it's 8000 something).
At 2048 bytes, creating def use and use def chains (and thus, the
reaching defs/reaching uses) will take 260 meg, min. 
This is way too large.

Also, garbage collecting them puts way too much strain on our poor
garbage collector, it turns out.
So i'm going to punt on garbage collecting them for now, or using a
superblock like structure.
I'll just free list them for the ones that want to use an obstack to
allocate the actual bitmap pointer, and use a global ebitmap memory
pool (rather than a obstack stack, since it's the wrong tool for the job) for the 256
bits we are always allocating/deallocating.

As you suggested, I made it directly manipulate the bit blocks itself
(rather than allocate/use sbitmaps), and have the blocks being
manipulated by block  functions/macros (and obviously, we have a
typedef unsigned HOST_WIDE_INT *ebitmap_block), so that if someone
wants to change the structure of what the blocks are stored in, they
don't need to touch anything related to the actual bitmap blocks.

--Dan

>
>
> r~

-- 
"All of the people in my building are insane.  The guy above me
designs synthetic hairballs for ceramic cats.  The lady across
the hall tried to rob a department store...  With a pricing
gun...  She said, "Give me all of the money in the vault, or I'm
marking down everything in the store."
"-Steven Wright