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 <ste...@gcc.gnu.org>
> > Richard Biener <rguent...@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 <rguent...@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB
21284 (AG Nuernberg)
