/* Functions to support general ended bitmaps.
- Copyright (C) 1997-2013 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"
-#include "vec.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;
- HOST_WIDEST_INT allocated;
- HOST_WIDEST_INT peak;
- HOST_WIDEST_INT current;
- int nsearches;
- 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 mapping bitmap names to descriptors. */
-static htab_t bitmap_desc_hash;
-
-/* Hashtable helpers. */
-static hashval_t
-hash_descriptor (const void *p)
-{
- const_bitmap_descriptor d = (const_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_bitmap_descriptor d = (const_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 bitmap_descriptor
-get_bitmap_descriptor (const char *file, int line, const char *function)
-{
- 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 = (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_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)
{
- bitmap_descriptor desc = bitmap_descriptors[b->descriptor_id];
- desc->current += amount;
- if (amount > 0)
- desc->allocated += amount;
- gcc_assert (desc->current >= 0);
- 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_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)
- bitmap_descriptors[head->descriptor_id]->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)
- 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
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. */
found_bit:
bit_no += ix * BITMAP_WORD_BITS;
#if GCC_VERSION >= 3004
- gcc_assert (sizeof(long) == sizeof (word));
+ gcc_assert (sizeof (long) == sizeof (word));
bit_no += BITMAP_WORD_BITS - __builtin_clzl (word) - 1;
#else
/* Hopefully this is a twos-complement host... */
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)
-{
- bitmap_descriptor d = (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"