/* Functions to support general ended bitmaps.
- Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005,
- 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
+ Copyright (C) 1997-2015 Free Software Foundation, Inc.
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
-#include "rtl.h"
-#include "flags.h"
#include "obstack.h"
-#include "ggc.h"
#include "bitmap.h"
-#include "hashtab.h"
-#ifdef GATHER_STATISTICS
-
-/* 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, const char *function, int line)
-{
- 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 (_loc_name, _loc_function, _loc_line);
- 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);
}
-#endif
/* Global data */
bitmap_element bitmap_zero_bits; /* An element of all zero bits. */
else
head->indx = 0;
}
-#ifdef GATHER_STATISTICS
- register_overhead (head, -((int)sizeof (bitmap_element)));
-#endif
+
+ if (GATHER_STATISTICS)
+ register_overhead (head, -((int)sizeof (bitmap_element)));
+
bitmap_elem_to_freelist (head, elt);
}
\f
/* Inner list was just a singleton. */
bitmap_ggc_free = element->prev;
else
- element = ggc_alloc_bitmap_element_def ();
+ element = ggc_alloc<bitmap_element> ();
}
-#ifdef GATHER_STATISTICS
- register_overhead (head, sizeof (bitmap_element));
-#endif
+ if (GATHER_STATISTICS)
+ register_overhead (head, sizeof (bitmap_element));
+
memset (element->bits, 0, sizeof (element->bits));
return element;
{
bitmap_element *prev;
bitmap_obstack *bit_obstack = head->obstack;
-#ifdef GATHER_STATISTICS
- int n;
-#endif
if (!elt) return;
-#ifdef GATHER_STATISTICS
- n = 0;
- for (prev = elt; prev; prev = prev->next)
- n++;
- register_overhead (head, -sizeof (bitmap_element) * n);
-#endif
+
+ if (GATHER_STATISTICS)
+ {
+ int n = 0;
+ for (prev = elt; prev; prev = prev->next)
+ n++;
+ register_overhead (head, -sizeof (bitmap_element) * n);
+ }
prev = elt->prev;
if (prev)
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);
-#ifdef GATHER_STATISTICS
- register_overhead (map, sizeof (bitmap_head));
-#endif
+
+ if (GATHER_STATISTICS)
+ register_overhead (map, sizeof (bitmap_head));
return map;
}
{
bitmap map;
- map = ggc_alloc_bitmap_head_def ();
+ map = ggc_alloc<bitmap_head> ();
bitmap_initialize_stat (map, NULL PASS_MEM_STAT);
-#ifdef GATHER_STATISTICS
- register_overhead (map, sizeof (bitmap_head));
-#endif
+
+ if (GATHER_STATISTICS)
+ register_overhead (map, sizeof (bitmap_head));
return map;
}
{
bitmap_clear (map);
map->first = (bitmap_element *) map->obstack->heads;
-#ifdef GATHER_STATISTICS
- register_overhead (map, -((int)sizeof (bitmap_head)));
-#endif
+
+ if (GATHER_STATISTICS)
+ register_overhead (map, -((int)sizeof (bitmap_head)));
+
map->obstack->heads = map;
}
}
}
else
{
- gcc_assert (head->current);
+ gcc_checking_assert (head->current);
node->next = elt->next;
if (node->next)
node->next->prev = node;
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;
-#ifdef GATHER_STATISTICS
- head->desc->nsearches++;
-#endif
+ if (head->current == head->first
+ && 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 = 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
for (element = head->current;
element->next != 0 && element->indx < indx;
element = element->next)
-#ifdef GATHER_STATISTICS
- head->desc->search_iter++;
-#else
- ;
-#endif
+ {
+ if (GATHER_STATISTICS && usage)
+ usage->m_search_iter++;
+ }
else if (head->indx / 2 < indx)
/* INDX is less than head->indx and closer to head->indx than to
for (element = head->current;
element->prev != 0 && element->indx > indx;
element = element->prev)
-#ifdef GATHER_STATISTICS
- head->desc->search_iter++;
-#else
- ;
-#endif
+ {
+ if (GATHER_STATISTICS && usage)
+ usage->m_search_iter++;
+ }
else
/* INDX is less than head->indx and closer to 0 than to
for (element = head->first;
element->next != 0 && element->indx < indx;
element = element->next)
-#ifdef GATHER_STATISTICS
- head->desc->search_iter++;
-#else
- ;
-#endif
+ if (GATHER_STATISTICS && usage)
+ {
+ 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. */
BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
bool res = (ptr->bits[word_num] & bit_val) != 0;
if (res)
- ptr->bits[word_num] &= ~bit_val;
-
- /* If we cleared the entire word, free up the element. */
- if (bitmap_element_zerop (ptr))
- bitmap_element_free (head, ptr);
+ {
+ ptr->bits[word_num] &= ~bit_val;
+ /* If we cleared the entire word, free up the element. */
+ if (!ptr->bits[word_num]
+ && bitmap_element_zerop (ptr))
+ bitmap_element_free (head, ptr);
+ }
return res;
}
BITMAP_WORD word;
unsigned ix;
- gcc_assert (elt);
+ gcc_checking_assert (elt);
bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
{
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. */
if (!(word & 0x1))
word >>= 1, bit_no += 1;
- gcc_assert (word & 1);
+ gcc_checking_assert (word & 1);
#endif
return bit_no;
}
BITMAP_WORD word;
int ix;
- gcc_assert (elt);
+ gcc_checking_assert (elt);
while (elt->next)
elt = elt->next;
bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
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_assert (word & 1);
- return bit_no;
+ return bit_no;
}
\f
/* Ensure that dst->current is valid. */
dst->current = dst->first;
bitmap_elt_clear_from (dst, dst_elt);
- gcc_assert (!dst->current == !dst->first);
+ gcc_checking_assert (!dst->current == !dst->first);
if (dst->current)
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);
- gcc_assert (!a->current == !a->first);
- gcc_assert (!a->current || a->indx == a->current->indx);
+
+ 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;
}
changed = true;
bitmap_elt_clear_from (dst, dst_elt);
}
- gcc_assert (!dst->current == !dst->first);
+ gcc_checking_assert (!dst->current == !dst->first);
if (dst->current)
dst->indx = dst->current->indx;
b_elt = b_elt->next;
}
}
- gcc_assert (!a->current == !a->first);
- gcc_assert (!a->current || a->indx == a->current->indx);
+ gcc_checking_assert (!a->current == !a->first
+ && (!a->current || a->indx == a->current->indx));
return changed != 0;
}
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;
bitmap_element_link (head, elt);
}
- gcc_assert (elt->indx == first_index);
+ gcc_checking_assert (elt->indx == first_index);
elt_prev = elt->prev;
for (i = first_index; i <= last_index; i++)
{
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;
b_elt = b_elt->next;
}
}
- gcc_assert (!a->current == !a->first);
- gcc_assert (!a->current || a->indx == a->current->indx);
+ gcc_checking_assert (!a->current == !a->first
+ && (!a->current || a->indx == a->current->indx));
return;
}
else
src = b_elt;
- gcc_assert (src);
+ gcc_checking_assert (src);
changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed);
}
return changed;
if (dst_elt)
{
changed = true;
+ /* Ensure that dst->current is valid. */
+ dst->current = dst->first;
bitmap_elt_clear_from (dst, dst_elt);
}
- gcc_assert (!dst->current == !dst->first);
+ gcc_checking_assert (!dst->current == !dst->first);
if (dst->current)
dst->indx = dst->current->indx;
return changed;
a_elt = *a_prev_pnext;
}
- gcc_assert (!a->current == !a->first);
+ gcc_checking_assert (!a->current == !a->first);
if (a->current)
a->indx = a->current->indx;
return changed;
/* Ensure that dst->current is valid. */
dst->current = dst->first;
bitmap_elt_clear_from (dst, dst_elt);
- gcc_assert (!dst->current == !dst->first);
+ gcc_checking_assert (!dst->current == !dst->first);
if (dst->current)
dst->indx = dst->current->indx;
}
a_elt = next;
}
}
- gcc_assert (!a->current == !a->first);
+ gcc_checking_assert (!a->current == !a->first);
if (a->current)
a->indx = a->current->indx;
}
if (dst_elt)
{
changed = true;
+ /* Ensure that dst->current is valid. */
+ dst->current = dst->first;
bitmap_elt_clear_from (dst, dst_elt);
}
- gcc_assert (!dst->current == !dst->first);
+ gcc_checking_assert (!dst->current == !dst->first);
if (dst->current)
dst->indx = dst->current->indx;
}
done:
- gcc_assert (!a->current == !a->first);
+ gcc_checking_assert (!a->current == !a->first);
if (a->current)
a->indx = a->current->indx;
return changed;
}
+
+/* Compute hash of bitmap (for purposes of hashing). */
+hashval_t
+bitmap_hash (const_bitmap head)
+{
+ const bitmap_element *ptr;
+ BITMAP_WORD hash = 0;
+ int ix;
+
+ for (ptr = head->first; ptr; ptr = ptr->next)
+ {
+ hash ^= ptr->indx;
+ for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
+ hash ^= ptr->bits[ix];
+ }
+ return (hashval_t)hash;
+}
+
\f
/* Debugging function to print out the contents of a bitmap. */
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);
}
-#ifdef GATHER_STATISTICS
-
-
-/* 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;
-}
-#endif
/* Output per-bitmap memory usage statistics. */
void
dump_bitmap_statistics (void)
{
-#ifdef GATHER_STATISTICS
- struct output_info info;
-
- if (!bitmap_desc_hash)
+ if (!GATHER_STATISTICS)
return;
- 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");
-#endif
+ bitmap_mem_desc.dump (BITMAP_ORIGIN);
}
-/* Compute hash of bitmap (for purposes of hashing). */
-hashval_t
-bitmap_hash (const_bitmap head)
+DEBUG_FUNCTION void
+debug (const bitmap_head &ref)
{
- const bitmap_element *ptr;
- BITMAP_WORD hash = 0;
- int ix;
+ dump_bitmap (stderr, &ref);
+}
- for (ptr = head->first; ptr; ptr = ptr->next)
- {
- hash ^= ptr->indx;
- for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
- hash ^= ptr->bits[ix];
- }
- return (hashval_t)hash;
+DEBUG_FUNCTION void
+debug (const bitmap_head *ptr)
+{
+ if (ptr)
+ debug (*ptr);
+ else
+ fprintf (stderr, "<nil>\n");
}
+
#include "gt-bitmap.h"
projects / gcc.git / blobdiff