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
