/* Functions to support general ended bitmaps.
- Copyright (C) 1997-2019 Free Software Foundation, Inc.
+ Copyright (C) 1997-2021 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. */
/* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */
inline void
- dump (mem_location *loc, mem_usage &total) const
+ dump (mem_location *loc, const mem_usage &total) const
{
char *location_string = loc->to_string ();
/* Obstack for allocating bitmaps and elements from. */
struct bitmap_obstack {
struct bitmap_element *elements;
- struct bitmap_head *heads;
+ bitmap_head *heads;
struct obstack obstack;
};
/* 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;
bitmap_element * GTY((skip(""))) current;
/* Obstack to allocate elements from. If NULL, then use GGC allocation. */
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);
+
+/* Set and get multiple bit values in a sparse bitmap. This allows a bitmap to
+ function as a sparse array of bit patterns where the patterns are
+ multiples of power of 2. This is more efficient than performing this as
+ multiple individual operations. */
+void bitmap_set_aligned_chunk (bitmap, unsigned int, unsigned int, BITMAP_WORD);
+BITMAP_WORD bitmap_get_aligned_chunk (const_bitmap, unsigned int, unsigned 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);
class auto_bitmap
{
public:
- auto_bitmap () { bitmap_initialize (&m_bits, &bitmap_default_obstack); }
- explicit auto_bitmap (bitmap_obstack *o) { bitmap_initialize (&m_bits, o); }
+ auto_bitmap (ALONE_CXX_MEM_STAT_INFO)
+ { bitmap_initialize (&m_bits, &bitmap_default_obstack PASS_MEM_STAT); }
+ explicit auto_bitmap (bitmap_obstack *o CXX_MEM_STAT_INFO)
+ { bitmap_initialize (&m_bits, o PASS_MEM_STAT); }
~auto_bitmap () { bitmap_clear (&m_bits); }
// Allow calling bitmap functions on our bitmap.
operator bitmap () { return &m_bits; }
// Prevent making a copy that references our bitmap.
auto_bitmap (const auto_bitmap &);
auto_bitmap &operator = (const auto_bitmap &);
-#if __cplusplus >= 201103L
auto_bitmap (auto_bitmap &&);
auto_bitmap &operator = (auto_bitmap &&);
-#endif
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 */
projects / thirdparty / gcc.git / blobdiff