On 6/7/21 4:40 AM, Richard Biener wrote:
On Wed, Jun 2, 2021 at 11:15 PM Andrew MacLeod <amacl...@redhat.com> wrote:
My thoughts are I would put this into trunk, and assuming nothing comes
up over the next couple of days, port it back to GCC11 to resolve
100299 and other excessive memory consumption PRs there as well. given
that its reusing bitmap code for the sparse representation, it seems
like it would be low risk.
Are we OK with the addition of the bitmap_get_quad and bitmap_set_quad
routines in bitmap.c? It seems like they might be useful to others.
They are simple tweaks of bitmap_set_bit and bitmap_bit_p.. just dealing
with 4 bits at a time. I could make them local if this is a problem,
but i don't have access to the bitmap internals there.
I think _quad is a bit too specific - it's aligned chunks so maybe
void bitmap_set_aligned_chunk (bitmap, unsigned int chunk, unsigned
int chunk_size, BITMAP_WORD chunk_value);
and
BITMAP_WORD bitmap_get_aligned_chunk (bitmap, unsigned int chunk,
unsigned chunk_size);
and assert that chunk_size is power-of-two and fits in BITMAP_WORD?
(also note using unsigned ints and BITMAP_WORD for the data type)
I've been using two-bit representations in a few places (but mostly
setting/testing the
respective bits independently), I suppose for example
That's exactly how this started.. I was using a pair of bits for
pointers. UNDEFINED, zero, non-zero and varying... and checking the bits
independently. when I decided I needed 3 bits, the whole quad thing
evolved since picking up 3 or 4 consecutive bits one at a time seemed
too inefficient.
static dep_state
query_loop_dependence (class loop *loop, im_mem_ref *ref, dep_kind kind)
{
unsigned first_bit = 6 * loop->num + kind * 2;
if (bitmap_bit_p (&ref->dep_loop, first_bit))
return dep_independent;
else if (bitmap_bit_p (&ref->dep_loop, first_bit + 1))
return dep_dependent;
could use a chunk size of 2 and a single bitmap query. Incidentially this
specific code uses 6 bits, so it's not fully aligned ...
/* We use six bits per loop in the ref->dep_loop bitmap to record
the dep_kind x dep_state combinations. */
enum dep_kind { lim_raw, sm_war, sm_waw };
enum dep_state { dep_unknown, dep_independent, dep_dependent };
... but there's also at most a single bit set.
Anyway, I'm OK with adding API to access aligned power-of-two sized chunks.
Even not power-of-two sized unaligned chunks should be quite straight
forward to implement if we limit the chunk size to BITMAP_WORD by
simply advancing to the next bitmap word / element when necessary.
An alternative low-level API would provide accesses to whole BITMAP_WORD
entries and the quads could be implemented on top of that
(bitmap_set_word/_get_word)
Richard.
I think I'll stick to the power of 2 limitation for now. If someone
finds a pressing need or desire, they can enhance it :-)
Wanna eyeball this an make sure I'm not doing something unportable.. I
just used your original 2 function names, and swapped out the 4 and a
couple of constants for computed values. Works fine for me.
I also made the self test process 2, 4 and 8 bit quantities.
Its going thru a test cycle now.
Andrew
commit e0fee2e994c4b763c2a8b2bcfb4b0ee30cb3e500
Author: Andrew MacLeod <amacl...@redhat.com>
Date: Mon Jun 7 13:12:01 2021 -0400
Implement multi-bit aligned accessors for sparse bitmap.
Provide set/get routines to allow sparse bitmaps to be treated as an array
of multiple bit values. Only chunk sizes that are powers of 2 are supported.
* bitmap.c (bitmap_set_aligned_chunk): New.
(bitmap_get_aligned_chunk): New.
(test_aligned_chunk): New.
(bitmap_c_tests): Call test_aligned_chunk.
* bitmap.h (bitmap_set_aligned_chunk, bitmap_get_aligned_chunk): New.
diff --git a/gcc/bitmap.c b/gcc/bitmap.c
index 5a650cdfc1d..7e1a218944d 100644
--- a/gcc/bitmap.c
+++ b/gcc/bitmap.c
@@ -1004,6 +1004,83 @@ bitmap_bit_p (const_bitmap head, int bit)
return (ptr->bits[word_num] >> bit_num) & 1;
}
+/* Set CHUNK_SIZE bits at a time in bitmap HEAD.
+ Store CHUNK_VALUE starting at bits CHUNK * chunk_size.
+ This is the set routine for viewing bitmap as a multi-bit sparse array. */
+
+void
+bitmap_set_aligned_chunk (bitmap head, unsigned int chunk,
+ unsigned int chunk_size, BITMAP_WORD chunk_value)
+{
+ // Ensure chunk size is a power of 2 and fits in BITMAP_WORD.
+ gcc_checking_assert (__builtin_popcount (chunk_size) == 1);
+ gcc_checking_assert (chunk_size < (sizeof (BITMAP_WORD) * CHAR_BIT));
+
+ // Ensure chunk_value is within range of chunk_size bits.
+ BITMAP_WORD max_value = (1 << chunk_size) - 1;
+ gcc_checking_assert (chunk_value <= max_value);
+
+ unsigned bit = chunk * chunk_size;
+ unsigned indx = bit / BITMAP_ELEMENT_ALL_BITS;
+ bitmap_element *ptr;
+ if (!head->tree_form)
+ ptr = bitmap_list_find_element (head, indx);
+ else
+ ptr = bitmap_tree_find_element (head, indx);
+ unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
+ unsigned bit_num = bit % BITMAP_WORD_BITS;
+ BITMAP_WORD bit_val = chunk_value << bit_num;
+ BITMAP_WORD mask = ~(max_value << bit_num);
+
+ if (ptr != 0)
+ {
+ ptr->bits[word_num] &= mask;
+ ptr->bits[word_num] |= bit_val;
+ return;
+ }
+
+ ptr = bitmap_element_allocate (head);
+ ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
+ ptr->bits[word_num] = bit_val;
+ if (!head->tree_form)
+ bitmap_list_link_element (head, ptr);
+ else
+ bitmap_tree_link_element (head, ptr);
+}
+
+/* This is the get routine for viewing bitmap as a multi-bit sparse array.
+ Return a set of CHUNK_SIZE consecutive bits from HEAD, starting at bit
+ CHUNK * chunk_size. */
+
+BITMAP_WORD
+bitmap_get_aligned_chunk (const_bitmap head, unsigned int chunk,
+ unsigned int chunk_size)
+{
+ // Ensure chunk size is a power of 2, fits in BITMAP_WORD and is in range.
+ gcc_checking_assert (__builtin_popcount (chunk_size) == 1);
+ gcc_checking_assert (chunk_size < (sizeof (BITMAP_WORD) * CHAR_BIT));
+
+ BITMAP_WORD max_value = (1 << chunk_size) - 1;
+ unsigned bit = chunk * chunk_size;
+ unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
+ const bitmap_element *ptr;
+ unsigned bit_num;
+ unsigned word_num;
+
+ if (!head->tree_form)
+ ptr = bitmap_list_find_element (const_cast<bitmap> (head), indx);
+ else
+ ptr = bitmap_tree_find_element (const_cast<bitmap> (head), indx);
+ if (ptr == 0)
+ return 0;
+
+ bit_num = bit % BITMAP_WORD_BITS;
+ word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
+
+ // Return 4 bits.
+ return (ptr->bits[word_num] >> bit_num) & max_value;
+}
+
#if GCC_VERSION < 3400
/* Table of number of set bits in a character, indexed by value of char. */
static const unsigned char popcount_table[] =
@@ -2857,6 +2934,33 @@ test_bitmap_single_bit_set_p ()
ASSERT_EQ (1066, bitmap_first_set_bit (b));
}
+/* Verify accessing aligned bit chunks works as expected. */
+
+static void
+test_aligned_chunk (unsigned num_bits)
+{
+ bitmap b = bitmap_gc_alloc ();
+ int limit = 2 ^ num_bits;
+
+ int index = 3;
+ for (int x = 0; x < limit; x++)
+ {
+ bitmap_set_aligned_chunk (b, index, num_bits, (BITMAP_WORD) x);
+ ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index, num_bits) == x);
+ ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index + 1,
+ num_bits) == 0);
+ ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index - 1,
+ num_bits) == 0);
+ index += 3;
+ }
+ index = 3;
+ for (int x = 0; x < limit ; x++)
+ {
+ ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index, num_bits) == x);
+ index += 3;
+ }
+}
+
/* Run all of the selftests within this file. */
void
@@ -2867,6 +2971,10 @@ bitmap_c_tests ()
test_clear_bit_in_middle ();
test_copying ();
test_bitmap_single_bit_set_p ();
+ /* Test 2, 4 and 8 bit aligned chunks. */
+ test_aligned_chunk (2);
+ test_aligned_chunk (4);
+ test_aligned_chunk (8);
}
} // namespace selftest
diff --git a/gcc/bitmap.h b/gcc/bitmap.h
index 26138556b2a..0846f79665d 100644
--- a/gcc/bitmap.h
+++ b/gcc/bitmap.h
@@ -438,6 +438,13 @@ extern bool bitmap_set_bit (bitmap, int);
/* Return true if a bit is set in a bitmap. */
extern int bitmap_bit_p (const_bitmap, int);
+/* Set and get multiple bit values in a sparse bitmap. This allows a bitmap to
+ function as a sparse array of bit patterns where the patterns are
+ multiples of power of 2. This is more efficient than performing this as
+ multiple individual operations. */
+void bitmap_set_aligned_chunk (bitmap, unsigned int, unsigned int, BITMAP_WORD);
+BITMAP_WORD bitmap_get_aligned_chunk (const_bitmap, unsigned int, unsigned int);
+
/* Debug functions to print a bitmap. */
extern void debug_bitmap (const_bitmap);
extern void debug_bitmap_file (FILE *, const_bitmap);
