/* Functions to support general ended bitmaps.
- Copyright (C) 1997-2014 Free Software Foundation, Inc.
+ Copyright (C) 1997-2016 Free Software Foundation, Inc.
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "obstack.h"
-#include "ggc.h"
#include "bitmap.h"
-#include "hash-table.h"
-#include "vec.h"
+#include "selftest.h"
-/* Store information about each particular bitmap, per allocation site. */
-struct bitmap_descriptor_d
-{
- int id;
- const char *function;
- const char *file;
- int line;
- int created;
- unsigned HOST_WIDEST_INT allocated;
- unsigned HOST_WIDEST_INT peak;
- unsigned HOST_WIDEST_INT current;
- unsigned HOST_WIDEST_INT nsearches;
- unsigned HOST_WIDEST_INT search_iter;
-};
-
-typedef struct bitmap_descriptor_d *bitmap_descriptor;
-typedef const struct bitmap_descriptor_d *const_bitmap_descriptor;
-
-/* Next available unique id number for bitmap desciptors. */
-static int next_bitmap_desc_id = 0;
-
-/* Vector mapping descriptor ids to descriptors. */
-static vec<bitmap_descriptor> bitmap_descriptors;
-
-/* Hashtable helpers. */
-
-struct loc
-{
- const char *file;
- const char *function;
- int line;
-};
-
-struct bitmap_desc_hasher : typed_noop_remove <bitmap_descriptor_d>
-{
- typedef bitmap_descriptor_d value_type;
- typedef loc compare_type;
- static inline hashval_t hash (const value_type *);
- static inline bool equal (const value_type *, const compare_type *);
-};
-
-inline hashval_t
-bitmap_desc_hasher::hash (const value_type *d)
-{
- return htab_hash_pointer (d->file) + d->line;
-}
-
-inline bool
-bitmap_desc_hasher::equal (const value_type *d, const compare_type *l)
-{
- return d->file == l->file && d->function == l->function && d->line == l->line;
-}
-
-/* Hashtable mapping bitmap names to descriptors. */
-static hash_table <bitmap_desc_hasher> bitmap_desc_hash;
-
-/* For given file and line, return descriptor, create new if needed. */
-static bitmap_descriptor
-get_bitmap_descriptor (const char *file, int line, const char *function)
-{
- bitmap_descriptor_d **slot;
- struct loc loc;
-
- loc.file = file;
- loc.function = function;
- loc.line = line;
-
- if (!bitmap_desc_hash.is_created ())
- bitmap_desc_hash.create (10);
-
- slot = bitmap_desc_hash.find_slot_with_hash (&loc,
- htab_hash_pointer (file) + line,
- INSERT);
- if (*slot)
- return *slot;
-
- *slot = XCNEW (struct bitmap_descriptor_d);
- bitmap_descriptors.safe_push (*slot);
- (*slot)->id = next_bitmap_desc_id++;
- (*slot)->file = file;
- (*slot)->function = function;
- (*slot)->line = line;
- return *slot;
-}
+/* Memory allocation statistics purpose instance. */
+mem_alloc_description<bitmap_usage> bitmap_mem_desc;
/* Register new bitmap. */
void
bitmap_register (bitmap b MEM_STAT_DECL)
{
- bitmap_descriptor desc = get_bitmap_descriptor (ALONE_FINAL_PASS_MEM_STAT);
- desc->created++;
- b->descriptor_id = desc->id;
+ bitmap_mem_desc.register_descriptor (b, BITMAP_ORIGIN, false
+ FINAL_PASS_MEM_STAT);
}
/* Account the overhead. */
static void
-register_overhead (bitmap b, int amount)
+register_overhead (bitmap b, size_t amount)
{
- bitmap_descriptor desc = bitmap_descriptors[b->descriptor_id];
- desc->current += amount;
- if (amount > 0)
- desc->allocated += amount;
- if (desc->peak < desc->current)
- desc->peak = desc->current;
+ if (bitmap_mem_desc.contains_descriptor_for_instance (b))
+ bitmap_mem_desc.register_instance_overhead (amount, b);
}
/* Global data */
/* Inner list was just a singleton. */
bitmap_ggc_free = element->prev;
else
- element = ggc_alloc_bitmap_element ();
+ element = ggc_alloc<bitmap_element> ();
}
if (GATHER_STATISTICS)
{
bitmap map;
- map = ggc_alloc_bitmap_head ();
+ map = ggc_alloc<bitmap_head> ();
bitmap_initialize_stat (map, NULL PASS_MEM_STAT);
if (GATHER_STATISTICS)
to_ptr = to_elt;
}
}
+
+/* Move a bitmap to another bitmap. */
+
+void
+bitmap_move (bitmap to, bitmap from)
+{
+ gcc_assert (to->obstack == from->obstack);
+
+ bitmap_clear (to);
+
+ *to = *from;
+
+ if (GATHER_STATISTICS)
+ {
+ size_t sz = 0;
+ for (bitmap_element *e = to->first; e; e = e->next)
+ sz += sizeof (bitmap_element);
+ register_overhead (to, sz);
+ register_overhead (from, -sz);
+ }
+}
\f
/* Find a bitmap element that would hold a bitmap's bit.
Update the `current' field even if we can't find an element that
&& head->first->next == NULL)
return NULL;
+ /* Usage can be NULL due to allocated bitmaps for which we do not
+ call initialize function. */
+ bitmap_usage *usage = NULL;
+ if (GATHER_STATISTICS)
+ usage = bitmap_mem_desc.get_descriptor_for_instance (head);
+
/* This bitmap has more than one element, and we're going to look
through the elements list. Count that as a search. */
- if (GATHER_STATISTICS)
- bitmap_descriptors[head->descriptor_id]->nsearches++;
+ if (GATHER_STATISTICS && usage)
+ usage->m_nsearches++;
if (head->indx < indx)
/* INDX is beyond head->indx. Search from head->current
element->next != 0 && element->indx < indx;
element = element->next)
{
- if (GATHER_STATISTICS)
- bitmap_descriptors[head->descriptor_id]->search_iter++;
+ if (GATHER_STATISTICS && usage)
+ usage->m_search_iter++;
}
else if (head->indx / 2 < indx)
element->prev != 0 && element->indx > indx;
element = element->prev)
{
- if (GATHER_STATISTICS)
- bitmap_descriptors[head->descriptor_id]->search_iter++;
+ if (GATHER_STATISTICS && usage)
+ usage->m_search_iter++;
}
else
for (element = head->first;
element->next != 0 && element->indx < indx;
element = element->next)
- if (GATHER_STATISTICS)
+ if (GATHER_STATISTICS && usage)
{
- bitmap_descriptors[head->descriptor_id]->search_iter++;
+ usage->m_search_iter++;
}
/* `element' is the nearest to the one we want. If it's not the one we
want, the one we want doesn't exist. */
head->current = element;
head->indx = element->indx;
- if (element != 0 && element->indx != indx)
+ if (element->indx != indx)
element = 0;
return element;
return ret;
}
#endif
+
+/* Count and return the number of bits set in the bitmap word BITS. */
+static unsigned long
+bitmap_count_bits_in_word (const BITMAP_WORD *bits)
+{
+ unsigned long count = 0;
+
+ for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
+ {
+#if GCC_VERSION >= 3400
+ /* Note that popcountl matches BITMAP_WORD in type, so the actual size
+ of BITMAP_WORD is not material. */
+ count += __builtin_popcountl (bits[ix]);
+#else
+ count += bitmap_popcount (bits[ix]);
+#endif
+ }
+ return count;
+}
+
/* Count the number of bits set in the bitmap, and return it. */
unsigned long
{
unsigned long count = 0;
const bitmap_element *elt;
- unsigned ix;
for (elt = a->first; elt; elt = elt->next)
+ count += bitmap_count_bits_in_word (elt->bits);
+
+ return count;
+}
+
+/* Count the number of unique bits set in A and B and return it. */
+
+unsigned long
+bitmap_count_unique_bits (const_bitmap a, const_bitmap b)
+{
+ unsigned long count = 0;
+ const bitmap_element *elt_a, *elt_b;
+
+ for (elt_a = a->first, elt_b = b->first; elt_a && elt_b; )
{
- for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
+ /* If we're at different indices, then count all the bits
+ in the lower element. If we're at the same index, then
+ count the bits in the IOR of the two elements. */
+ if (elt_a->indx < elt_b->indx)
{
-#if GCC_VERSION >= 3400
- /* Note that popcountl matches BITMAP_WORD in type, so the actual size
- of BITMAP_WORD is not material. */
- count += __builtin_popcountl (elt->bits[ix]);
-#else
- count += bitmap_popcount (elt->bits[ix]);
-#endif
+ count += bitmap_count_bits_in_word (elt_a->bits);
+ elt_a = elt_a->next;
+ }
+ else if (elt_b->indx < elt_a->indx)
+ {
+ count += bitmap_count_bits_in_word (elt_b->bits);
+ elt_b = elt_b->next;
+ }
+ else
+ {
+ BITMAP_WORD bits[BITMAP_ELEMENT_WORDS];
+ for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
+ bits[ix] = elt_a->bits[ix] | elt_b->bits[ix];
+ count += bitmap_count_bits_in_word (bits);
+ elt_a = elt_a->next;
+ elt_b = elt_b->next;
}
}
return count;
if (!count)
return;
+ if (count == 1)
+ {
+ bitmap_set_bit (head, start);
+ return;
+ }
+
first_index = start / BITMAP_ELEMENT_ALL_BITS;
end_bit_plus1 = start + count;
last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
if (!count)
return;
+ if (count == 1)
+ {
+ bitmap_clear_bit (head, start);
+ return;
+ }
+
first_index = start / BITMAP_ELEMENT_ALL_BITS;
end_bit_plus1 = start + count;
last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
if (dst_elt)
{
changed = true;
+ /* Ensure that dst->current is valid. */
+ dst->current = dst->first;
bitmap_elt_clear_from (dst, dst_elt);
}
gcc_checking_assert (!dst->current == !dst->first);
if (dst_elt)
{
changed = true;
+ /* Ensure that dst->current is valid. */
+ dst->current = dst->first;
bitmap_elt_clear_from (dst, dst_elt);
}
gcc_checking_assert (!dst->current == !dst->first);
fputs (suffix, file);
}
-
-/* Used to accumulate statistics about bitmap sizes. */
-struct output_info
-{
- unsigned HOST_WIDEST_INT size;
- unsigned HOST_WIDEST_INT count;
-};
-
-/* Called via hash_table::traverse. Output bitmap descriptor pointed out by
- SLOT and update statistics. */
-int
-print_statistics (bitmap_descriptor_d **slot, output_info *i)
-{
- bitmap_descriptor d = *slot;
- char s[4096];
-
- if (d->allocated)
- {
- const char *s1 = d->file;
- const char *s2;
- while ((s2 = strstr (s1, "gcc/")))
- s1 = s2 + 4;
- sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
- s[41] = 0;
- fprintf (stderr,
- "%-41s %9u"
- " %15"HOST_WIDEST_INT_PRINT"d %15"HOST_WIDEST_INT_PRINT"d"
- " %15"HOST_WIDEST_INT_PRINT"d"
- " %10"HOST_WIDEST_INT_PRINT"d %10"HOST_WIDEST_INT_PRINT"d\n",
- s, d->created,
- d->allocated, d->peak, d->current,
- d->nsearches, d->search_iter);
- i->size += d->allocated;
- i->count += d->created;
- }
- return 1;
-}
-
/* Output per-bitmap memory usage statistics. */
void
dump_bitmap_statistics (void)
{
- struct output_info info;
-
- if (! GATHER_STATISTICS)
+ if (!GATHER_STATISTICS)
return;
- if (!bitmap_desc_hash.is_created ())
- return;
-
- fprintf (stderr,
- "\n%-41s %9s %15s %15s %15s %10s %10s\n",
- "Bitmap", "Overall",
- "Allocated", "Peak", "Leak",
- "searched", "search_itr");
- fprintf (stderr, "---------------------------------------------------------------------------------\n");
- info.count = 0;
- info.size = 0;
- bitmap_desc_hash.traverse <output_info *, print_statistics> (&info);
- fprintf (stderr, "---------------------------------------------------------------------------------\n");
- fprintf (stderr,
- "%-41s %9"HOST_WIDEST_INT_PRINT"d %15"HOST_WIDEST_INT_PRINT"d\n",
- "Total", info.count, info.size);
- fprintf (stderr, "---------------------------------------------------------------------------------\n");
+ bitmap_mem_desc.dump (BITMAP_ORIGIN);
}
DEBUG_FUNCTION void
fprintf (stderr, "<nil>\n");
}
+#if CHECKING_P
+
+namespace selftest {
+
+/* Selftests for bitmaps. */
+
+/* Freshly-created bitmaps ought to be empty. */
+
+static void
+test_gc_alloc ()
+{
+ bitmap b = bitmap_gc_alloc ();
+ ASSERT_TRUE (bitmap_empty_p (b));
+}
+
+/* Verify bitmap_set_range. */
+
+static void
+test_set_range ()
+{
+ bitmap b = bitmap_gc_alloc ();
+ ASSERT_TRUE (bitmap_empty_p (b));
+
+ bitmap_set_range (b, 7, 5);
+ ASSERT_FALSE (bitmap_empty_p (b));
+ ASSERT_EQ (5, bitmap_count_bits (b));
+
+ /* Verify bitmap_bit_p at the boundaries. */
+ ASSERT_FALSE (bitmap_bit_p (b, 6));
+ ASSERT_TRUE (bitmap_bit_p (b, 7));
+ ASSERT_TRUE (bitmap_bit_p (b, 11));
+ ASSERT_FALSE (bitmap_bit_p (b, 12));
+}
+
+/* Verify splitting a range into two pieces using bitmap_clear_bit. */
+
+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));
+}
+
+/* Verify bitmap_copy. */
+
+static void
+test_copying ()
+{
+ bitmap src = bitmap_gc_alloc ();
+ bitmap_set_range (src, 40, 10);
+
+ bitmap dst = bitmap_gc_alloc ();
+ ASSERT_FALSE (bitmap_equal_p (src, dst));
+ bitmap_copy (dst, src);
+ ASSERT_TRUE (bitmap_equal_p (src, dst));
+
+ /* Verify that we can make them unequal again... */
+ bitmap_set_range (src, 70, 5);
+ ASSERT_FALSE (bitmap_equal_p (src, dst));
+
+ /* ...and that changing src after the copy didn't affect
+ the other: */
+ ASSERT_FALSE (bitmap_bit_p (dst, 70));
+}
+
+/* Verify bitmap_single_bit_set_p. */
+
+static void
+test_bitmap_single_bit_set_p ()
+{
+ bitmap b = bitmap_gc_alloc ();
+
+ ASSERT_FALSE (bitmap_single_bit_set_p (b));
+
+ bitmap_set_range (b, 42, 1);
+ ASSERT_TRUE (bitmap_single_bit_set_p (b));
+ ASSERT_EQ (42, bitmap_first_set_bit (b));
+
+ bitmap_set_range (b, 1066, 1);
+ ASSERT_FALSE (bitmap_single_bit_set_p (b));
+ ASSERT_EQ (42, bitmap_first_set_bit (b));
+
+ bitmap_clear_range (b, 0, 100);
+ ASSERT_TRUE (bitmap_single_bit_set_p (b));
+ ASSERT_EQ (1066, bitmap_first_set_bit (b));
+}
+
+/* Run all of the selftests within this file. */
+
+void
+bitmap_c_tests ()
+{
+ test_gc_alloc ();
+ test_set_range ();
+ test_clear_bit_in_middle ();
+ test_copying ();
+ test_bitmap_single_bit_set_p ();
+}
+
+} // namespace selftest
+#endif /* CHECKING_P */
#include "gt-bitmap.h"
projects / platform / upstream / gcc.git / blobdiff