/* Functions to support general ended bitmaps.
- Copyright (C) 1997-2012 Free Software Foundation, Inc.
+ Copyright (C) 1997-2015 Free Software Foundation, Inc.
This file is part of GCC.
#include "system.h"
#include "coretypes.h"
#include "obstack.h"
-#include "ggc.h"
#include "bitmap.h"
-#include "hashtab.h"
-/* Store information about each particular bitmap. */
-struct bitmap_descriptor
-{
- const char *function;
- const char *file;
- int line;
- int created;
- HOST_WIDEST_INT allocated;
- HOST_WIDEST_INT peak;
- HOST_WIDEST_INT current;
- int nsearches;
- int search_iter;
-};
-
-/* Hashtable mapping bitmap names to descriptors. */
-static htab_t bitmap_desc_hash;
-
-/* Hashtable helpers. */
-static hashval_t
-hash_descriptor (const void *p)
-{
- const struct bitmap_descriptor *const d =
- (const struct bitmap_descriptor *) p;
- return htab_hash_pointer (d->file) + d->line;
-}
-struct loc
-{
- const char *file;
- const char *function;
- int line;
-};
-static int
-eq_descriptor (const void *p1, const void *p2)
-{
- const struct bitmap_descriptor *const d =
- (const struct bitmap_descriptor *) p1;
- const struct loc *const l = (const struct loc *) p2;
- return d->file == l->file && d->function == l->function && d->line == l->line;
-}
-
-/* For given file and line, return descriptor, create new if needed. */
-static struct bitmap_descriptor *
-bitmap_descriptor (const char *file, int line, const char *function)
-{
- struct bitmap_descriptor **slot;
- struct loc loc;
-
- loc.file = file;
- loc.function = function;
- loc.line = line;
-
- if (!bitmap_desc_hash)
- bitmap_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
-
- slot = (struct bitmap_descriptor **)
- htab_find_slot_with_hash (bitmap_desc_hash, &loc,
- htab_hash_pointer (file) + line,
- INSERT);
- if (*slot)
- return *slot;
- *slot = XCNEW (struct bitmap_descriptor);
- (*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)
{
- b->desc = bitmap_descriptor (ALONE_FINAL_PASS_MEM_STAT);
- b->desc->created++;
+ bitmap_mem_desc.register_descriptor (b, BITMAP_ORIGIN, false
+ FINAL_PASS_MEM_STAT);
}
/* Account the overhead. */
static void
register_overhead (bitmap b, int amount)
{
- b->desc->current += amount;
- if (amount > 0)
- b->desc->allocated += amount;
- gcc_assert (b->desc->current >= 0);
- if (b->desc->peak < b->desc->current)
- b->desc->peak = b->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_def ();
+ element = ggc_alloc<bitmap_element> ();
}
if (GATHER_STATISTICS)
bit_obstack = &bitmap_default_obstack;
map = bit_obstack->heads;
if (map)
- bit_obstack->heads = (struct bitmap_head_def *) map->first;
+ bit_obstack->heads = (struct bitmap_head *) map->first;
else
map = XOBNEW (&bit_obstack->obstack, bitmap_head);
bitmap_initialize_stat (map, bit_obstack PASS_MEM_STAT);
{
bitmap map;
- map = ggc_alloc_bitmap_head_def ();
+ map = ggc_alloc<bitmap_head> ();
bitmap_initialize_stat (map, NULL PASS_MEM_STAT);
if (GATHER_STATISTICS)
bitmap_element *element;
unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
- if (head->current == 0
+ if (head->current == NULL
|| head->indx == indx)
return head->current;
+ if (head->current == head->first
+ && head->first->next == NULL)
+ return NULL;
- if (GATHER_STATISTICS)
- head->desc->nsearches++;
+ /* Usage can be NULL due to allocated bitmaps for which we do not
+ call initialize function. */
+ bitmap_usage *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 && 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)
- head->desc->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)
- head->desc->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)
{
- head->desc->search_iter++;
+ usage->m_search_iter++;
}
/* `element' is the nearest to the one we want. If it's not the one we
bit_no += ix * BITMAP_WORD_BITS;
#if GCC_VERSION >= 3004
- gcc_assert (sizeof(long) == sizeof (word));
+ gcc_assert (sizeof (long) == sizeof (word));
bit_no += __builtin_ctzl (word);
#else
/* Binary search for the first set bit. */
gcc_unreachable ();
found_bit:
bit_no += ix * BITMAP_WORD_BITS;
-
- /* Binary search for the last set bit. */
#if GCC_VERSION >= 3004
- gcc_assert (sizeof(long) == sizeof (word));
- bit_no += sizeof (long) * 8 - __builtin_ctzl (word);
+ gcc_assert (sizeof (long) == sizeof (word));
+ bit_no += BITMAP_WORD_BITS - __builtin_clzl (word) - 1;
#else
-#if BITMAP_WORD_BITS > 64
-#error "Fill out the table."
-#endif
+ /* Hopefully this is a twos-complement host... */
+ BITMAP_WORD x = word;
+ x |= (x >> 1);
+ x |= (x >> 2);
+ x |= (x >> 4);
+ x |= (x >> 8);
+ x |= (x >> 16);
#if BITMAP_WORD_BITS > 32
- if ((word & 0xffffffff00000000))
- word >>= 32, bit_no += 32;
+ x |= (x >> 32);
#endif
- if (word & 0xffff0000)
- word >>= 16, bit_no += 16;
- if (!(word & 0xff00))
- word >>= 8, bit_no += 8;
- if (!(word & 0xf0))
- word >>= 4, bit_no += 4;
- if (!(word & 12))
- word >>= 2, bit_no += 2;
- if (!(word & 2))
- word >>= 1, bit_no += 1;
+ bit_no += bitmap_popcount (x) - 1;
#endif
- gcc_checking_assert (word & 1);
- return bit_no;
+ return bit_no;
}
\f
dst->indx = dst->current->indx;
}
-/* A &= B. */
+/* A &= B. Return true if A changed. */
-void
+bool
bitmap_and_into (bitmap a, const_bitmap b)
{
bitmap_element *a_elt = a->first;
const bitmap_element *b_elt = b->first;
bitmap_element *next;
+ bool changed = false;
if (a == b)
- return;
+ return false;
while (a_elt && b_elt)
{
next = a_elt->next;
bitmap_element_free (a, a_elt);
a_elt = next;
+ changed = true;
}
else if (b_elt->indx < a_elt->indx)
b_elt = b_elt->next;
for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
{
BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
-
+ if (a_elt->bits[ix] != r)
+ changed = true;
a_elt->bits[ix] = r;
ior |= r;
}
b_elt = b_elt->next;
}
}
- bitmap_elt_clear_from (a, a_elt);
+
+ if (a_elt)
+ {
+ changed = true;
+ bitmap_elt_clear_from (a, a_elt);
+ }
+
gcc_checking_assert (!a->current == !a->first
&& (!a->current || a->indx == a->current->indx));
+
+ return changed;
}
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);
DEBUG_FUNCTION void
debug_bitmap (const_bitmap head)
{
- debug_bitmap_file (stdout, head);
+ debug_bitmap_file (stderr, head);
}
/* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
it does not print anything but the bits. */
DEBUG_FUNCTION void
-bitmap_print (FILE *file, const_bitmap head, const char *prefix, const char *suffix)
+bitmap_print (FILE *file, const_bitmap head, const char *prefix,
+ const char *suffix)
{
const char *comma = "";
unsigned i;
fputs (suffix, file);
}
-
-/* Used to accumulate statistics about bitmap sizes. */
-struct output_info
-{
- HOST_WIDEST_INT size;
- int count;
-};
-
-/* Called via htab_traverse. Output bitmap descriptor pointed out by SLOT
- and update statistics. */
-static int
-print_statistics (void **slot, void *b)
-{
- struct bitmap_descriptor *d = (struct bitmap_descriptor *) *slot;
- struct output_info *i = (struct output_info *) b;
- 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 %8d %15"HOST_WIDEST_INT_PRINT"d %15"
- HOST_WIDEST_INT_PRINT"d %15"HOST_WIDEST_INT_PRINT"d %10d %10d\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)
- return;
+ bitmap_mem_desc.dump (BITMAP_ORIGIN);
+}
- fprintf (stderr, "\nBitmap Overall "
- " Allocated Peak Leak searched "
- " search itr\n");
- fprintf (stderr, "---------------------------------------------------------------------------------\n");
- info.count = 0;
- info.size = 0;
- htab_traverse (bitmap_desc_hash, print_statistics, &info);
- fprintf (stderr, "---------------------------------------------------------------------------------\n");
- fprintf (stderr, "%-40s %9d %15"HOST_WIDEST_INT_PRINT"d\n",
- "Total", info.count, info.size);
- fprintf (stderr, "---------------------------------------------------------------------------------\n");
+DEBUG_FUNCTION void
+debug (const bitmap_head &ref)
+{
+ dump_bitmap (stderr, &ref);
+}
+
+DEBUG_FUNCTION void
+debug (const bitmap_head *ptr)
+{
+ if (ptr)
+ debug (*ptr);
+ else
+ fprintf (stderr, "<nil>\n");
}
+
#include "gt-bitmap.h"