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).
Hope this is constructive
Dave
