RE: bitmaps in gcc

RE: bitmaps in gcc

[Meissner, Michael]

One of the classic places that sparse bitmaps were used in GCC in the
past is in register allocation phase, where you essentially have a 2D
sparse matrix with # of basic blocks on one axis and pseudo register
number on the other axis.  When you are compiling very large functions,
the number of basic blocks and the number of pseudo registers are very
large, and if the table wasn't compressed (most registers aren't live
past a single basic block) it was very significant.  I haven't looked at
this area in the last two years or so when I wasn't working on GCC, so
it might have changed.  Unfortunately I don't recall whether we were
using compressed bitmaps before I wrote the original versions of the
compressed bit vectors, but the idea was to encapsulate everything
within macros so it could be changed in the future.

-----Original Message-----
From: gcc-owner@gcc.gnu.org [mailto:gcc-owner@gcc.gnu.org] On Behalf Of
Brian Makin
Sent: Friday, October 14, 2005 1:27 PM
To: gcc@gcc.gnu.org
Subject: bitmaps in gcc


In reference to this on the wiki.

Bitmaps, also called sparse bit sets, are implemented using a linked
list with a cache. This is probably not the most time-efficient
representation, and it is not unusual for bitmap functions to show up
high on the execution profile. Bitmaps are used for many things, such as
for live register sets at the entry and exit of basic blocks in RTL, or
for a great number of data flow problems. See bitmap.c (and sbitmap.c
for GCC's simple bitmap implementation).

Can someone point me to a testcase where bitmap functions show up high
on the profile?


Can anyone give me some background on the use of bitmaps in gcc?

Are they assumed to be sparse?
How critical is the memory consumption of bitsets?
What operations are the most speed critical?
Would it be desirable to merge bitmap and sbitmap into one
datastructure?
Anyone have good ideas for improvements?

Anything else anyone would want to add?

I think I may take a look at this.  Once I figure out the requirments
maybe we can speed it up a bit.


Brian N. Makin






		
__________________________________
Start your day with Yahoo! - Make it your home page! 
http://www.yahoo.com/r/hs

Re: bitmaps in gcc

[Richard Henderson]

On Fri, Oct 14, 2005 at 11:27:15AM -0700, Brian Makin wrote:
> Can anyone give me some background on the use of
> bitmaps in gcc?

There's pleanty of material in the list archives.  This is not
the first time that this topic has come up.


r~

Re: bitmaps in gcc

[Ian Lance Taylor]

Brian Makin <merimus@yahoo.com> writes:

> Bitmaps, also called sparse bit sets, are implemented
> using a linked list with a cache. This is probably not
> the most time-efficient representation, and it is not
> unusual for bitmap functions to show up high on the
> execution profile. Bitmaps are used for many things,
> such as for live register sets at the entry and exit
> of basic blocks in RTL, or for a great number of data
> flow problems. See bitmap.c (and sbitmap.c for GCC's
> simple bitmap implementation).
> 
> Can someone point me to a testcase where bitmap
> functions show up high on the profile?

PR 8361.

Ian

bitmaps in gcc

[Brian Makin]

In reference to this on the wiki.

Bitmaps, also called sparse bit sets, are implemented
using a linked list with a cache. This is probably not
the most time-efficient representation, and it is not
unusual for bitmap functions to show up high on the
execution profile. Bitmaps are used for many things,
such as for live register sets at the entry and exit
of basic blocks in RTL, or for a great number of data
flow problems. See bitmap.c (and sbitmap.c for GCC's
simple bitmap implementation).

Can someone point me to a testcase where bitmap
functions show up high on the profile?


Can anyone give me some background on the use of
bitmaps in gcc?

Are they assumed to be sparse?
How critical is the memory consumption of bitsets?
What operations are the most speed critical?
Would it be desirable to merge bitmap and sbitmap into
one datastructure?
Anyone have good ideas for improvements?

Anything else anyone would want to add?

I think I may take a look at this.  Once I figure out
the requirments maybe we can speed it up a bit.


Brian N. Makin






		
__________________________________ 
Start your day with Yahoo! - Make it your home page! 
http://www.yahoo.com/r/hs