Re: [patch][RFC] bitmaps as lists *or* trees

[Steven Bosscher <stevenb.gcc@gmail.com>]

On Tue, Mar 5, 2013 at 1:32 PM, Richard Biener wrote:
>> The attached patch is a first stab at an idea I've had for a while:
>> Implement a "change of view" for bitmaps, such that a bitmap can be
>> either a linked list, or a binary tree.
...
> Definitely a nice idea.  Iteration should be easy to implement (without
> actually splaying for each visited bit), the bit operations can use the
> iteration as building block as well then.

It is really easy, you only have to "listify" the splay tree such that
the root is the element with the lowest index. AFAICT the iterators
only look at the "next" member of each bitmap_element, and a list is
also a valid splay tree.


> Now, an instrumented bitmap to identify bitmaps that would benefit
> from the tree view would be nice ;)  [points-to sets are never modified
> after being computed, but they are both random-tested and intersected]

I have no idea how to create that kind of instrumentation.

> What I missed often as well is a reference counted shared bitmap
> implementation (we have various special case implementations).
> I wonder if that could even use shared sub-trees/lists of bitmap_elts.

And this idea, I don't even understand :-)
"reference counted shared bitmaps" as in, the same bitmap element
shared between different bitmaps? How would you link such elements
together in a tree or a list? It could be done with array bitmaps, but
those have other downsides (insert/delete is near impossible without a
lot of mem-moving around).

Ciao!
Steven