[PATCH] Add splay-tree "view" for bitmap

[Richard Biener]

On Thu, 18 Oct 2018, David Malcolm wrote:

> On Thu, 2018-10-18 at 15:09 +0200, Richard Biener wrote:
> > PR63155 made me pick up this old work from Steven, it turns our
> > linked-list implementation to a two-mode one with one being a
> > splay tree featuring O(log N) complexity for find/remove.
> > 
> > Over Stevens original patch I added a bitmap_tree_to_vec helper
> > that I use from the debug/print methods to avoid changing view
> > there.  In theory the bitmap iterator could get a "stack"
> > as well and we could at least support EXECUTE_IF_SET_IN_BITMAP.
> > 
> > This can be used to fix the two biggest bottlenecks in the PRs
> > testcase, namely SSA propagator worklist handling and out-of-SSA
> > coalesce list building.  perf shows the following data, first
> > unpatched, second patched - also watch the thrid coulumn (samples)
> > when comparing percentages.
> > 
> [...snip...]
> 
> > Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
> > 
> > Any objections?
> > 
> > Thanks,
> > Richard.
> > 
> > 2018-10-18  Steven Bosscher <steven@gcc.gnu.org>
> > 	Richard Biener  <rguenther@suse.de>
> > 
> > 	* bitmap.h: Update data structure documentation, including a
> > 	description of bitmap views as either linked-lists or splay
> > trees.
> 
> [...snip...]
> 
> From a "correctness" perspective, we have some existing unit-test
> coverage for bitmap via selftests in bitmap.c.  Perhaps those tests
> could be generalized to verify that the two different implementations
> work, and that the conversions work correctly?
> 
> e.g. currently we have:
> 
> static void
> test_clear_bit_in_middle ()
> {
>   bitmap b = bitmap_gc_alloc ();
> 
>   /* Set b to [100..200].  */
>   bitmap_set_range (b, 100, 100);
>   ASSERT_EQ (100, bitmap_count_bits (b));
> 
>   /* Clear a bit in the middle.  */
>   bool changed = bitmap_clear_bit (b, 150);
>   ASSERT_TRUE (changed);
>   ASSERT_EQ (99, bitmap_count_bits (b));
>   ASSERT_TRUE (bitmap_bit_p (b, 149));
>   ASSERT_FALSE (bitmap_bit_p (b, 150));
>   ASSERT_TRUE (bitmap_bit_p (b, 151));
> }
> 
> Maybe this could change to:
> 
> static void
> test_clear_bit_in_middle ()
> {
>   bitmap b = bitmap_gc_alloc ();
> 
>   FOR_EACH_BITMAP_IMPL (b)
>     {
>       /* Set b to [100..200].  */
>       bitmap_set_range (b, 100, 100);
>       ASSERT_EQ (100, bitmap_count_bits (b));
>     }
> 
>   bool first_time = true;
>   /* Clear a bit in the middle.  */
>   FOR_EACH_BITMAP_IMPL (b)
>     {
>       if (first_time)
>         {
>           bool changed = bitmap_clear_bit (b, 150);
>           ASSERT_TRUE (changed);
>           first_time = false;
>         }
>       ASSERT_EQ (99, bitmap_count_bits (b));
>       ASSERT_TRUE (bitmap_bit_p (b, 149));
>       ASSERT_FALSE (bitmap_bit_p (b, 150));
>       ASSERT_TRUE (bitmap_bit_p (b, 151));
>     }
> }
> 
> ...or somesuch, where maybe FOR_EACH_BITMAP_IMPL (b) could try linked-
> list, then splay tree, then linked-list, converting "b" as it goes.  
> This would hopefully give us a lot of test coverage for the various
> operations in both modes, and for the conversion routines (in both
> directions, assuming that both directions are supported).

Hmm, unfortunately the splay-tree variant doesn't implement
bitmap_count_bits or bitmap_set_range.

Note some of the missing functionality might need implementation
of a bitmap element iterator (maybe I should transform my
bitmap_tree_to_vec to that instead).

But I'm quite sure bitmaps are extensively tested with GCC
bootstrap ;)

Richard.

> Hope this is constructive
> Dave
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)