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: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] 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
