CbC/CbC_gcc: gcc/bitmap.h comparison

comparison gcc/bitmap.h @ 145:1830386684a0

gcc-9.2.0

author	anatofuz
date	Thu, 13 Feb 2020 11:34:05 +0900
parents	84e7813d76e9
children

comparison

equal deleted inserted replaced

-:84e7813d76e9
+:1830386684a0
 /* 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.
 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
 of enumeration, and does also *not* support logical operations on sets.
 The binary tree representation is only supposed to be used for sets
 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.  */
 bitmap_usage (size_t allocated, size_t times, size_t peak,
 	     uint64_t nsearches, uint64_t search_iter)
 inline void
 dump (mem_location *loc, mem_usage &total) const
 {
 char *location_string = loc->to_string ();
-fprintf (stderr, "%-48s %10" PRIu64 ":%5.1f%%"
+fprintf (stderr, "%-48s " PRsa (9) ":%5.1f%%"
-	     "%10" PRIu64 "%10" PRIu64 ":%5.1f%%"
+	     PRsa (9) PRsa (9) ":%5.1f%%"
-	     "%12" PRIu64 "%12" PRIu64 "%10s\n",
+	     PRsa (11) PRsa (11) "%10s\n",
-	     location_string, (uint64_t)m_allocated,
+	     location_string, SIZE_AMOUNT (m_allocated),
 	     get_percent (m_allocated, total.m_allocated),
-	     (uint64_t)m_peak, (uint64_t)m_times,
+	     SIZE_AMOUNT (m_peak), SIZE_AMOUNT (m_times),
 	     get_percent (m_times, total.m_times),
-	     m_nsearches, m_search_iter,
+	     SIZE_AMOUNT (m_nsearches), SIZE_AMOUNT (m_search_iter),
 	     loc->m_ggc ? "ggc" : "heap");
 free (location_string);
 }
 static inline void
 dump_header (const char *name)
 {
 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.  */
 uint64_t m_nsearches;
 /* Number of search iterations.  */
 /* Number of bits in each actual element of a bitmap.  */
 #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;
+bitmap_head *heads;
-struct obstack GTY ((skip)) obstack;
+struct obstack obstack;
 };
 /* Bitmap set element.  We use a linked list to hold only the bits that
 are set.  This allows for use to grow the bitset dynamically without
 having to realloc and copy a giant bit array.
 element) that are connected by the next fields.  The prev pointer
 is undefined for interior elements.  This allows
 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;
 /* In list form, the previous element in the linked list;
 in tree form, the right child node in the tree.  */
 };
 /* 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), 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 bitmap_element bitmap_zero_bits;	/* Zero bitmap element */
 extern bitmap_obstack bitmap_default_obstack;   /* Default bitmap obstack */
 extern void bitmap_compl_and_into (bitmap, const_bitmap);
 extern void bitmap_clear_range (bitmap, unsigned int, unsigned int);
 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);
 /* DST = A | (B & C).  Return true if DST changes.  */
 extern bool bitmap_ior_and_into (bitmap DST, const_bitmap B, const_bitmap C);
 /* Set a single bit in a bitmap.  Return true if the bit changed.  */
 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);
 extern void debug_bitmap_file (FILE *, const_bitmap);
 static inline void
 bitmap_initialize (bitmap head, bitmap_obstack *obstack CXX_MEM_STAT_INFO)
 {
 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);
+}
+/* Release a bitmap (but not its head).  This is suitable for pairing with
+bitmap_initialize.  */
+static inline void
+bitmap_release (bitmap head)
+{
+bitmap_clear (head);
+/* Poison the obstack pointer so the obstack can be safely released.
+Do not zero it as the bitmap then becomes initialized GC.  */
+head->obstack = &bitmap_head::crashme;
 }
 /* Allocate and free bitmaps from obstack, malloc and gc'd memory.  */
 extern bitmap bitmap_alloc (bitmap_obstack *obstack CXX_MEM_STAT_INFO);
 #define BITMAP_ALLOC bitmap_alloc
 #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 */

Mercurial > hg > CbC > CbC_gcc

comparison gcc/bitmap.h @ 145:1830386684a0