/* Functions to support general ended bitmaps.
- Copyright (C) 1997-2018 Free Software Foundation, Inc.
+ Copyright (C) 1997-2020 Free Software Foundation, Inc.
This file is part of GCC.
on which many random-access membership tests will happen. */
#include "obstack.h"
+#include "array-traits.h"
/* Bitmap memory usage. */
-struct bitmap_usage: public mem_usage
+class bitmap_usage: public mem_usage
{
+public:
/* Default contructor. */
bitmap_usage (): m_nsearches (0), m_search_iter (0) {}
/* Constructor. */
{
fprintf (stderr, "%-48s %11s%16s%17s%12s%12s%10s\n", name, "Leak", "Peak",
"Times", "N searches", "Search iter", "Type");
- print_dash_line ();
}
/* Number search operations. */
#define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)
/* Obstack for allocating bitmaps and elements from. */
-struct GTY (()) bitmap_obstack {
+struct bitmap_obstack {
struct bitmap_element *elements;
- struct bitmap_head *heads;
- struct obstack GTY ((skip)) obstack;
+ bitmap_head *heads;
+ struct obstack obstack;
};
/* Bitmap set element. We use a linked list to hold only the bits that
bitmap_elt_clear_from to be implemented in unit time rather than
linear in the number of elements to be freed. */
-struct GTY((chain_next ("%h.next"), chain_prev ("%h.prev"))) bitmap_element {
+struct GTY((chain_next ("%h.next"))) bitmap_element {
/* In list form, the next element in the linked list;
in tree form, the left child node in the tree. */
struct bitmap_element *next;
/* Head of bitmap linked list. The 'current' member points to something
already pointed to by the chain started by first, so GTY((skip)) it. */
-struct GTY(()) bitmap_head {
+class GTY(()) bitmap_head {
+public:
static bitmap_obstack crashme;
/* Poison obstack to not make it not a valid initialized GC bitmap. */
CONSTEXPR bitmap_head()
- : indx(0), tree_form(false), first(NULL), current(NULL),
- obstack (&crashme)
+ : indx (0), tree_form (false), padding (0), alloc_descriptor (0), first (NULL),
+ current (NULL), obstack (&crashme)
{}
/* Index of last element looked at. */
unsigned int indx;
/* False if the bitmap is in list form; true if the bitmap is in tree form.
Bitmap iterators only work on bitmaps in list form. */
- bool tree_form;
+ unsigned tree_form: 1;
+ /* Next integer is shifted, so padding is needed. */
+ unsigned padding: 2;
+ /* Bitmap UID used for memory allocation statistics. */
+ unsigned alloc_descriptor: 29;
/* In list form, the first element in the linked list;
in tree form, the root of the tree. */
bitmap_element *first;
/* Last element looked at. */
bitmap_element * GTY((skip(""))) current;
/* Obstack to allocate elements from. If NULL, then use GGC allocation. */
- bitmap_obstack *obstack;
+ bitmap_obstack * GTY((skip(""))) obstack;
+
+ /* Dump bitmap. */
void dump ();
+
+ /* Get bitmap descriptor UID casted to an unsigned integer pointer.
+ Shift the descriptor because pointer_hash<Type>::hash is
+ doing >> 3 shift operation. */
+ unsigned *get_descriptor ()
+ {
+ return (unsigned *)(ptrdiff_t)(alloc_descriptor << 3);
+ }
};
/* Global data */
extern void bitmap_set_range (bitmap, unsigned int, unsigned int);
extern bool bitmap_ior (bitmap, const_bitmap, const_bitmap);
extern bool bitmap_ior_into (bitmap, const_bitmap);
+extern bool bitmap_ior_into_and_free (bitmap, bitmap *);
extern void bitmap_xor (bitmap, const_bitmap, const_bitmap);
extern void bitmap_xor_into (bitmap, const_bitmap);
extern bool bitmap_set_bit (bitmap, int);
/* Return true if a bit is set in a bitmap. */
-extern int bitmap_bit_p (bitmap, int);
+extern int bitmap_bit_p (const_bitmap, int);
/* Debug functions to print a bitmap. */
extern void debug_bitmap (const_bitmap);
{
head->first = head->current = NULL;
head->indx = head->tree_form = 0;
+ head->padding = 0;
+ head->alloc_descriptor = 0;
head->obstack = obstack;
if (GATHER_STATISTICS)
bitmap_register (head PASS_MEM_STAT);
bitmap_head m_bits;
};
+/* Base class for bitmap_view; see there for details. */
+template<typename T, typename Traits = array_traits<T> >
+class base_bitmap_view
+{
+public:
+ typedef typename Traits::element_type array_element_type;
+
+ base_bitmap_view (const T &, bitmap_element *);
+ operator const_bitmap () const { return &m_head; }
+
+private:
+ base_bitmap_view (const base_bitmap_view &);
+
+ bitmap_head m_head;
+};
+
+/* Provides a read-only bitmap view of a single integer bitmask or a
+ constant-sized array of integer bitmasks, or of a wrapper around such
+ bitmasks. */
+template<typename T, typename Traits>
+class bitmap_view<T, Traits, true> : public base_bitmap_view<T, Traits>
+{
+public:
+ bitmap_view (const T &array)
+ : base_bitmap_view<T, Traits> (array, m_bitmap_elements) {}
+
+private:
+ /* How many bitmap_elements we need to hold a full T. */
+ static const size_t num_bitmap_elements
+ = CEIL (CHAR_BIT
+ * sizeof (typename Traits::element_type)
+ * Traits::constant_size,
+ BITMAP_ELEMENT_ALL_BITS);
+ bitmap_element m_bitmap_elements[num_bitmap_elements];
+};
+
+/* Initialize the view for array ARRAY, using the array of bitmap
+ elements in BITMAP_ELEMENTS (which is known to contain enough
+ entries). */
+template<typename T, typename Traits>
+base_bitmap_view<T, Traits>::base_bitmap_view (const T &array,
+ bitmap_element *bitmap_elements)
+{
+ m_head.obstack = NULL;
+
+ /* The code currently assumes that each element of ARRAY corresponds
+ to exactly one bitmap_element. */
+ const size_t array_element_bits = CHAR_BIT * sizeof (array_element_type);
+ STATIC_ASSERT (BITMAP_ELEMENT_ALL_BITS % array_element_bits == 0);
+ size_t array_step = BITMAP_ELEMENT_ALL_BITS / array_element_bits;
+ size_t array_size = Traits::size (array);
+
+ /* Process each potential bitmap_element in turn. The loop is written
+ this way rather than per array element because usually there are
+ only a small number of array elements per bitmap element (typically
+ two or four). The inner loops should therefore unroll completely. */
+ const array_element_type *array_elements = Traits::base (array);
+ unsigned int indx = 0;
+ for (size_t array_base = 0;
+ array_base < array_size;
+ array_base += array_step, indx += 1)
+ {
+ /* How many array elements are in this particular bitmap_element. */
+ unsigned int array_count
+ = (STATIC_CONSTANT_P (array_size % array_step == 0)
+ ? array_step : MIN (array_step, array_size - array_base));
+
+ /* See whether we need this bitmap element. */
+ array_element_type ior = array_elements[array_base];
+ for (size_t i = 1; i < array_count; ++i)
+ ior |= array_elements[array_base + i];
+ if (ior == 0)
+ continue;
+
+ /* Grab the next bitmap element and chain it. */
+ bitmap_element *bitmap_element = bitmap_elements++;
+ if (m_head.current)
+ m_head.current->next = bitmap_element;
+ else
+ m_head.first = bitmap_element;
+ bitmap_element->prev = m_head.current;
+ bitmap_element->next = NULL;
+ bitmap_element->indx = indx;
+ m_head.current = bitmap_element;
+ m_head.indx = indx;
+
+ /* Fill in the bits of the bitmap element. */
+ if (array_element_bits < BITMAP_WORD_BITS)
+ {
+ /* Multiple array elements fit in one element of
+ bitmap_element->bits. */
+ size_t array_i = array_base;
+ for (unsigned int word_i = 0; word_i < BITMAP_ELEMENT_WORDS;
+ ++word_i)
+ {
+ BITMAP_WORD word = 0;
+ for (unsigned int shift = 0;
+ shift < BITMAP_WORD_BITS && array_i < array_size;
+ shift += array_element_bits)
+ word |= array_elements[array_i++] << shift;
+ bitmap_element->bits[word_i] = word;
+ }
+ }
+ else
+ {
+ /* Array elements are the same size as elements of
+ bitmap_element->bits, or are an exact multiple of that size. */
+ unsigned int word_i = 0;
+ for (unsigned int i = 0; i < array_count; ++i)
+ for (unsigned int shift = 0; shift < array_element_bits;
+ shift += BITMAP_WORD_BITS)
+ bitmap_element->bits[word_i++]
+ = array_elements[array_base + i] >> shift;
+ while (word_i < BITMAP_ELEMENT_WORDS)
+ bitmap_element->bits[word_i++] = 0;
+ }
+ }
+}
+
#endif /* GCC_BITMAP_H */