Mercurial > hg > CbC > CbC_gcc
diff gcc/bitmap.h @ 145:1830386684a0
gcc-9.2.0
author | anatofuz |
---|---|
date | Thu, 13 Feb 2020 11:34:05 +0900 |
parents | 84e7813d76e9 |
children |
line wrap: on
line diff
--- a/gcc/bitmap.h Thu Oct 25 07:37:49 2018 +0900 +++ b/gcc/bitmap.h Thu Feb 13 11:34:05 2020 +0900 @@ -1,5 +1,5 @@ /* 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. @@ -210,10 +210,12 @@ 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. */ @@ -239,14 +241,14 @@ { char *location_string = loc->to_string (); - fprintf (stderr, "%-48s %10" PRIu64 ":%5.1f%%" - "%10" PRIu64 "%10" PRIu64 ":%5.1f%%" - "%12" PRIu64 "%12" PRIu64 "%10s\n", - location_string, (uint64_t)m_allocated, + fprintf (stderr, "%-48s " PRsa (9) ":%5.1f%%" + PRsa (9) PRsa (9) ":%5.1f%%" + PRsa (11) PRsa (11) "%10s\n", + 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); @@ -258,7 +260,6 @@ { 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. */ @@ -288,10 +289,10 @@ #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 @@ -306,7 +307,7 @@ 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; @@ -322,20 +323,41 @@ /* 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 */ @@ -394,6 +416,7 @@ 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); @@ -413,7 +436,7 @@ 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); @@ -436,11 +459,25 @@ { 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 @@ -920,4 +957,123 @@ 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 */