This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH]: Updated new sparse bitmap patch

Hi Michael,

A little clarification/correction for posterity ;-)

On Friday 30 March 2007 23:17, Michael Meissner wrote:
> Note, the main motivating factor for the linked list bitmap routines
> (sbitmap)

sbitmap is not the linked list bitmap datastructure. An sbitmap is
just an array of (usually) fixed size.  sbitmaps should be used if
you expect your bitmap to be not sparse (e.g. when you're walking
an ordered set of fixed size such as all ssa names, or all basic
blocks).  See sbitmap.[ch].

bitmap is GCC's sparse bitmap implementation.  This is the linked
list of elements. Used for e.g. liveness and for selecting subsets
of larger numbered sets (e.g. to mark a subselection of all ssa
names or all basic blocks).  See bitmap.[ch].
(Just to confuse the uninitiated, bitmap is sometimes also known
as regset, see basic-block.h.  It took me years to find out that
regset and bitmap are actually the same datastructure.)

ebitmaps should compete with bitmap.

> was to handle the conflict matrix used by the global register 
> allocator to note whether a register was live in a basic block or not. 

The global register allocator still uses bitmap (aka. regset) to
see which registers are live, via like global_live_at_{start,end}.

For the conflict graph, it uses an array of HOST_WIDE_INTs.

> When you are compiling very large modules this can seriously affect the
> compiler performance.  When switching between ebitmap and sbitmap, it would
> probably be a useful exercise to test the compiler performance on small
> memory machines as well as large memory machines.

It never hurts to try, but I think it'll be difficult to measure
a difference.  The real memory abuse in global.c is in the conflict
graph representation, and no bitmaps of any kind are used there.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]