/* Functions to support general ended bitmaps.
Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005,
- 2006, 2007 Free Software Foundation, Inc.
+ 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
-Software Foundation; either version 2, or (at your option) any later
+Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
const char *function;
const char *file;
int line;
- int allocated;
int created;
- int peak;
- int current;
+ HOST_WIDEST_INT allocated;
+ HOST_WIDEST_INT peak;
+ HOST_WIDEST_INT current;
int nsearches;
};
static hashval_t
hash_descriptor (const void *p)
{
- const struct bitmap_descriptor *const d = p;
+ const struct bitmap_descriptor *const d =
+ (const struct bitmap_descriptor *) p;
return htab_hash_pointer (d->file) + d->line;
}
struct loc
static int
eq_descriptor (const void *p1, const void *p2)
{
- const struct bitmap_descriptor *const d = p1;
- const struct loc *const l = 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;
}
slot = (struct bitmap_descriptor **)
htab_find_slot_with_hash (bitmap_desc_hash, &loc,
htab_hash_pointer (file) + line,
- 1);
+ INSERT);
if (*slot)
return *slot;
- *slot = xcalloc (sizeof (**slot), 1);
+ *slot = XCNEW (struct bitmap_descriptor);
(*slot)->file = file;
(*slot)->function = function;
(*slot)->line = line;
/* Global data */
bitmap_element bitmap_zero_bits; /* An element of all zero bits. */
bitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */
+static int bitmap_default_obstack_depth;
static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of
GC'd elements. */
/* Clear a bitmap by freeing the linked list. */
-inline void
+void
bitmap_clear (bitmap head)
{
if (head->first)
bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
{
if (!bit_obstack)
- bit_obstack = &bitmap_default_obstack;
+ {
+ if (bitmap_default_obstack_depth++)
+ return;
+ bit_obstack = &bitmap_default_obstack;
+ }
#if !defined(__GNUC__) || (__GNUC__ < 2)
#define __alignof__(type) 0
bitmap_obstack_release (bitmap_obstack *bit_obstack)
{
if (!bit_obstack)
- bit_obstack = &bitmap_default_obstack;
+ {
+ if (--bitmap_default_obstack_depth)
+ {
+ gcc_assert (bitmap_default_obstack_depth > 0);
+ return;
+ }
+ bit_obstack = &bitmap_default_obstack;
+ }
bit_obstack->elements = NULL;
bit_obstack->heads = NULL;
bit_obstack = &bitmap_default_obstack;
map = bit_obstack->heads;
if (map)
- bit_obstack->heads = (void *)map->first;
+ bit_obstack->heads = (struct bitmap_head_def *) map->first;
else
map = XOBNEW (&bit_obstack->obstack, bitmap_head);
bitmap_initialize_stat (map, bit_obstack PASS_MEM_STAT);
if (map)
{
bitmap_clear (map);
- map->first = (void *)map->obstack->heads;
+ map->first = (bitmap_element *) map->obstack->heads;
#ifdef GATHER_STATISTICS
register_overhead (map, -((int)sizeof (bitmap_head)));
#endif
return element;
}
\f
-/* Clear a single bit in a bitmap. */
+/* Clear a single bit in a bitmap. Return true if the bit changed. */
-void
+bool
bitmap_clear_bit (bitmap head, int bit)
{
bitmap_element *const ptr = bitmap_find_bit (head, bit);
{
unsigned bit_num = bit % BITMAP_WORD_BITS;
unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
- ptr->bits[word_num] &= ~ (((BITMAP_WORD) 1) << bit_num);
+ 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);
+
+ return res;
}
+
+ return false;
}
-/* Set a single bit in a bitmap. */
+/* Set a single bit in a bitmap. Return true if the bit changed. */
-void
+bool
bitmap_set_bit (bitmap head, int bit)
{
bitmap_element *ptr = bitmap_find_bit (head, bit);
ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
ptr->bits[word_num] = bit_val;
bitmap_element_link (head, ptr);
+ return true;
}
else
- ptr->bits[word_num] |= bit_val;
+ {
+ bool res = (ptr->bits[word_num] & bit_val) == 0;
+ if (res)
+ ptr->bits[word_num] |= bit_val;
+ return res;
+ }
}
/* Return whether a bit is set within a bitmap. */
return count;
}
+/* Return true if the bitmap has a single bit set. Otherwise return
+ false. */
+
+bool
+bitmap_single_bit_set_p (const_bitmap a)
+{
+ unsigned long count = 0;
+ const bitmap_element *elt;
+ unsigned ix;
+
+ if (bitmap_empty_p (a))
+ return false;
+
+ elt = a->first;
+ /* As there are no completely empty bitmap elements, a second one
+ means we have more than one bit set. */
+ if (elt->next != NULL)
+ return false;
+
+ for (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 (elt->bits[ix]);
+#else
+ count += bitmap_popcount (elt->bits[ix]);
+#endif
+ if (count > 1)
+ return false;
+ }
+
+ return count == 1;
+}
/* Return the bit number of the first set bit in the bitmap. The
#endif
return bit_no;
}
+
+/* Return the bit number of the first set bit in the bitmap. The
+ bitmap must be non-empty. */
+
+unsigned
+bitmap_last_set_bit (const_bitmap a)
+{
+ const bitmap_element *elt = a->current ? a->current : a->first;
+ unsigned bit_no;
+ BITMAP_WORD word;
+ int ix;
+
+ gcc_assert (elt);
+ while (elt->next)
+ elt = elt->next;
+ bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
+ for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--)
+ {
+ word = elt->bits[ix];
+ if (word)
+ goto found_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);
+#else
+#if BITMAP_WORD_BITS > 64
+#error "Fill out the table."
+#endif
+#if BITMAP_WORD_BITS > 32
+ if ((word & 0xffffffff00000000))
+ word >>= 32, bit_no += 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;
+#endif
+
+ gcc_assert (word & 1);
+ return bit_no;
+}
\f
/* DST = A & B. */
return changed;
}
+/* A |= (B & C). Return true if A changes. */
+
+bool
+bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c)
+{
+ bitmap_element *a_elt = a->first;
+ const bitmap_element *b_elt = b->first;
+ const bitmap_element *c_elt = c->first;
+ bitmap_element and_elt;
+ bitmap_element *a_prev = NULL;
+ bitmap_element **a_prev_pnext = &a->first;
+ bool changed = false;
+ unsigned ix;
+
+ if (b == c)
+ return bitmap_ior_into (a, b);
+ if (bitmap_empty_p (b) || bitmap_empty_p (c))
+ return false;
+
+ and_elt.indx = -1;
+ while (b_elt && c_elt)
+ {
+ BITMAP_WORD overall;
+
+ /* Find a common item of B and C. */
+ while (b_elt->indx != c_elt->indx)
+ {
+ if (b_elt->indx < c_elt->indx)
+ {
+ b_elt = b_elt->next;
+ if (!b_elt)
+ goto done;
+ }
+ else
+ {
+ c_elt = c_elt->next;
+ if (!c_elt)
+ goto done;
+ }
+ }
+
+ overall = 0;
+ and_elt.indx = b_elt->indx;
+ for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+ {
+ and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix];
+ overall |= and_elt.bits[ix];
+ }
+
+ b_elt = b_elt->next;
+ c_elt = c_elt->next;
+ if (!overall)
+ continue;
+
+ /* Now find a place to insert AND_ELT. */
+ do
+ {
+ ix = a_elt ? a_elt->indx : and_elt.indx;
+ if (ix == and_elt.indx)
+ changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed);
+ else if (ix > and_elt.indx)
+ changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed);
+
+ a_prev = *a_prev_pnext;
+ a_prev_pnext = &a_prev->next;
+ a_elt = *a_prev_pnext;
+
+ /* If A lagged behind B/C, we advanced it so loop once more. */
+ }
+ while (ix < and_elt.indx);
+ }
+
+ done:
+ gcc_assert (!a->current == !a->first);
+ if (a->current)
+ a->indx = a->current->indx;
+ return changed;
+}
\f
/* Debugging function to print out the contents of a bitmap. */
{
const bitmap_element *ptr;
- fprintf (file, "\nfirst = %p current = %p indx = %u\n",
+ fprintf (file, "\nfirst = " HOST_PTR_PRINTF
+ " current = " HOST_PTR_PRINTF " indx = %u\n",
(void *) head->first, (void *) head->current, head->indx);
for (ptr = head->first; ptr; ptr = ptr->next)
{
unsigned int i, j, col = 26;
- fprintf (file, "\t%p next = %p prev = %p indx = %u\n\t\tbits = {",
+ fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
+ " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
(const void*) ptr, (const void*) ptr->next,
(const void*) ptr->prev, ptr->indx);
/* Used to accumulate statistics about bitmap sizes. */
struct output_info
{
+ HOST_WIDEST_INT size;
int count;
- int size;
};
/* Called via htab_traverse. Output bitmap descriptor pointed out by SLOT
s1 = s2 + 4;
sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
s[41] = 0;
- fprintf (stderr, "%-41s %6d %10d %10d %10d %10d\n", s,
- d->created, d->allocated, d->peak, d->current, d->nsearches);
+ fprintf (stderr, "%-41s %8d %15"HOST_WIDEST_INT_PRINT"d %15"
+ HOST_WIDEST_INT_PRINT"d %15"HOST_WIDEST_INT_PRINT"d %10d\n",
+ s, d->created, d->allocated, d->peak, d->current, d->nsearches);
i->size += d->allocated;
i->count += d->created;
}
return;
fprintf (stderr, "\nBitmap Overall "
- "Allocated Peak Leak searched "
+ " Allocated Peak Leak searched "
" per search\n");
fprintf (stderr, "---------------------------------------------------------------------------------\n");
info.count = 0;
info.size = 0;
htab_traverse (bitmap_desc_hash, print_statistics, &info);
fprintf (stderr, "---------------------------------------------------------------------------------\n");
- fprintf (stderr, "%-40s %7d %10d\n",
+ fprintf (stderr, "%-40s %9d %15"HOST_WIDEST_INT_PRINT"d\n",
"Total", info.count, info.size);
fprintf (stderr, "---------------------------------------------------------------------------------\n");
#endif