On Tue, Mar 5, 2013 at 3:50 PM, Steven Bosscher <stevenb....@gmail.com> wrote: > 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.
You'd have a "fat" iterator object with a (sorted) array of bitmap elements to iterate over, similar to how loop iterators work. >> 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). You can share "leafs" of trees (not of lists due to the back pointer), splaying of course destroys the shared properties ... At the moment shared bitmaps (where used) are simply using hashtables and bitmap_hash. The propagation parts of the points-to solver could benefit from copy-on-write shared bitmaps. Richard. > Ciao! > Steven
