Line data Source code
1 : /* Simple bitmaps.
2 : Copyright (C) 1999-2023 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify it under
7 : the terms of the GNU General Public License as published by the Free
8 : Software Foundation; either version 3, or (at your option) any later
9 : version.
10 :
11 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with GCC; see the file COPYING3. If not see
18 : <http://www.gnu.org/licenses/>. */
19 :
20 : #ifndef GCC_SBITMAP_H
21 : #define GCC_SBITMAP_H
22 :
23 : /* Implementation of sets using simple bitmap vectors.
24 :
25 : This set representation is suitable for non-sparse sets with a known
26 : (a priori) universe. The set is represented as a simple array of the
27 : host's fastest unsigned integer. For a given member I in the set:
28 : - the element for I will be at sbitmap[I / (bits per element)]
29 : - the position for I within element is I % (bits per element)
30 :
31 : This representation is very space-efficient for large non-sparse sets
32 : with random access patterns.
33 :
34 : The following operations can be performed in O(1) time:
35 :
36 : * set_size : SBITMAP_SIZE
37 : * member_p : bitmap_bit_p
38 : * add_member : bitmap_set_bit
39 : * remove_member : bitmap_clear_bit
40 :
41 : Most other operations on this set representation are O(U) where U is
42 : the size of the set universe:
43 :
44 : * clear : bitmap_clear
45 : * choose_one : bitmap_first_set_bit /
46 : bitmap_last_set_bit
47 : * forall : EXECUTE_IF_SET_IN_BITMAP
48 : * set_copy : bitmap_copy
49 : * set_intersection : bitmap_and
50 : * set_union : bitmap_ior
51 : * set_difference : bitmap_and_compl
52 : * set_disjuction : (not implemented)
53 : * set_compare : bitmap_equal_p
54 : * bit_in_range_p : bitmap_bit_in_range_p
55 :
56 : Some operations on 3 sets that occur frequently in data flow problems
57 : are also implemented:
58 :
59 : * A | (B & C) : bitmap_or_and
60 : * A | (B & ~C) : bitmap_ior_and_compl
61 : * A & (B | C) : bitmap_and_or
62 :
63 : Most of the set functions have two variants: One that returns non-zero
64 : if members were added or removed from the target set, and one that just
65 : performs the operation without feedback. The former operations are a
66 : bit more expensive but the result can often be used to avoid iterations
67 : on other sets.
68 :
69 : Allocating a bitmap is done with sbitmap_alloc, and resizing is
70 : performed with sbitmap_resize.
71 :
72 : The storage requirements for simple bitmap sets is O(U) where U is the
73 : size of the set universe (colloquially the number of bits in the bitmap).
74 :
75 : This set representation works well for relatively small data flow problems
76 : (there are special routines for that, see sbitmap_vector_*). The set
77 : operations can be vectorized and there is almost no computating overhead,
78 : so that even sparse simple bitmap sets outperform dedicated sparse set
79 : representations like linked-list bitmaps. For larger problems, the size
80 : overhead of simple bitmap sets gets too high and other set representations
81 : have to be used. */
82 :
83 : #define SBITMAP_ELT_BITS (HOST_BITS_PER_WIDEST_FAST_INT * 1u)
84 : #define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
85 :
86 : struct simple_bitmap_def
87 : {
88 : unsigned int n_bits; /* Number of bits. */
89 : unsigned int size; /* Size in elements. */
90 : SBITMAP_ELT_TYPE elms[1]; /* The elements. */
91 : };
92 :
93 : /* Return the set size needed for N elements. */
94 : #define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS)
95 :
96 : /* Return the number of bits in BITMAP. */
97 : #define SBITMAP_SIZE(BITMAP) ((BITMAP)->n_bits)
98 :
99 : /* Verify that access at INDEX in bitmap MAP is valid. */
100 :
101 : inline void
102 48 : bitmap_check_index (const_sbitmap map, int index)
103 : {
104 48 : gcc_checking_assert (index >= 0);
105 48 : gcc_checking_assert ((unsigned int)index < map->n_bits);
106 48 : }
107 :
108 : /* Verify that bitmaps A and B have same size. */
109 :
110 : inline void
111 : bitmap_check_sizes (const_sbitmap a, const_sbitmap b)
112 : {
113 : gcc_checking_assert (a->n_bits == b->n_bits);
114 : }
115 :
116 : /* Test if bit number bitno in the bitmap is set. */
117 : inline bool
118 32 : bitmap_bit_p (const_sbitmap map, int bitno)
119 : {
120 32 : bitmap_check_index (map, bitno);
121 :
122 32 : size_t i = bitno / SBITMAP_ELT_BITS;
123 32 : unsigned int s = bitno % SBITMAP_ELT_BITS;
124 32 : return (map->elms[i] >> s) & (SBITMAP_ELT_TYPE) 1;
125 : }
126 :
127 : /* Set bit number BITNO in the sbitmap MAP.
128 : Return true if the bit changed. */
129 :
130 : inline bool
131 16 : bitmap_set_bit (sbitmap map, int bitno)
132 : {
133 16 : bitmap_check_index (map, bitno);
134 :
135 16 : size_t i = bitno / SBITMAP_ELT_BITS;
136 16 : unsigned int s = bitno % SBITMAP_ELT_BITS;
137 16 : if (map->elms[i] & ((SBITMAP_ELT_TYPE) 1 << s))
138 : return false;
139 16 : map->elms[i] |= (SBITMAP_ELT_TYPE) 1 << s;
140 16 : return true;
141 : }
142 :
143 : /* Reset bit number BITNO in the sbitmap MAP.
144 : Return true if the bit changed. */
145 :
146 : inline bool
147 : bitmap_clear_bit (sbitmap map, int bitno)
148 : {
149 : bitmap_check_index (map, bitno);
150 :
151 : size_t i = bitno / SBITMAP_ELT_BITS;
152 : unsigned int s = bitno % SBITMAP_ELT_BITS;
153 : if (!(map->elms[i] & ((SBITMAP_ELT_TYPE) 1 << s)))
154 : return false;
155 : map->elms[i] &= ~((SBITMAP_ELT_TYPE) 1 << s);
156 : return true;
157 : }
158 :
159 : /* The iterator for sbitmap. */
160 : struct sbitmap_iterator {
161 : /* The pointer to the first word of the bitmap. */
162 : const SBITMAP_ELT_TYPE *ptr;
163 :
164 : /* The size of the bitmap. */
165 : unsigned int size;
166 :
167 : /* The current word index. */
168 : unsigned int word_num;
169 :
170 : /* The current bit index (not modulo SBITMAP_ELT_BITS). */
171 : unsigned int bit_num;
172 :
173 : /* The words currently visited. */
174 : SBITMAP_ELT_TYPE word;
175 : };
176 :
177 : /* Initialize the iterator I with sbitmap BMP and the initial index
178 : MIN. */
179 :
180 : inline void
181 : bmp_iter_set_init (sbitmap_iterator *i, const_sbitmap bmp,
182 : unsigned int min, unsigned *bit_no ATTRIBUTE_UNUSED)
183 : {
184 : i->word_num = min / (unsigned int) SBITMAP_ELT_BITS;
185 : i->bit_num = min;
186 : i->size = bmp->size;
187 : i->ptr = bmp->elms;
188 :
189 : if (i->word_num >= i->size)
190 : i->word = 0;
191 : else
192 : i->word = (i->ptr[i->word_num]
193 : >> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS));
194 : }
195 :
196 : /* Return true if we have more bits to visit, in which case *N is set
197 : to the index of the bit to be visited. Otherwise, return
198 : false. */
199 :
200 : inline bool
201 : bmp_iter_set (sbitmap_iterator *i, unsigned int *n)
202 : {
203 : /* Skip words that are zeros. */
204 : for (; i->word == 0; i->word = i->ptr[i->word_num])
205 : {
206 : i->word_num++;
207 :
208 : /* If we have reached the end, break. */
209 : if (i->word_num >= i->size)
210 : return false;
211 :
212 : i->bit_num = i->word_num * SBITMAP_ELT_BITS;
213 : }
214 :
215 : /* Skip bits that are zero. */
216 : for (; (i->word & 1) == 0; i->word >>= 1)
217 : i->bit_num++;
218 :
219 : *n = i->bit_num;
220 :
221 : return true;
222 : }
223 :
224 : /* Advance to the next bit. */
225 :
226 : inline void
227 : bmp_iter_next (sbitmap_iterator *i, unsigned *bit_no ATTRIBUTE_UNUSED)
228 : {
229 : i->word >>= 1;
230 : i->bit_num++;
231 : }
232 :
233 : /* Loop over all elements of SBITMAP, starting with MIN. In each
234 : iteration, N is set to the index of the bit being visited. ITER is
235 : an instance of sbitmap_iterator used to iterate the bitmap. */
236 :
237 : #ifndef EXECUTE_IF_SET_IN_BITMAP
238 : /* See bitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP. */
239 : #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \
240 : for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \
241 : bmp_iter_set (&(ITER), &(BITNUM)); \
242 : bmp_iter_next (&(ITER), &(BITNUM)))
243 : #endif
244 :
245 : inline void sbitmap_free (sbitmap map)
246 : {
247 : free (map);
248 : }
249 :
250 : inline void sbitmap_vector_free (sbitmap * vec)
251 : {
252 : free (vec);
253 : }
254 :
255 : extern void dump_bitmap (FILE *, const_sbitmap);
256 : extern void debug_raw (const simple_bitmap_def &ref);
257 : extern void debug_raw (const simple_bitmap_def *ptr);
258 : extern void dump_bitmap_file (FILE *, const_sbitmap);
259 : extern void debug (const simple_bitmap_def &ref);
260 : extern void debug (const simple_bitmap_def *ptr);
261 : extern void dump_bitmap_vector (FILE *, const char *, const char *, sbitmap *,
262 : int);
263 : extern sbitmap sbitmap_alloc (unsigned int);
264 : extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int);
265 : extern sbitmap sbitmap_resize (sbitmap, unsigned int, int);
266 : extern void bitmap_copy (sbitmap, const_sbitmap);
267 : extern bool bitmap_equal_p (const_sbitmap, const_sbitmap);
268 : extern unsigned int bitmap_count_bits (const_sbitmap);
269 : extern bool bitmap_empty_p (const_sbitmap);
270 : extern void bitmap_clear (sbitmap);
271 : extern void bitmap_clear_range (sbitmap, unsigned, unsigned);
272 : extern void bitmap_set_range (sbitmap, unsigned, unsigned);
273 : extern void bitmap_ones (sbitmap);
274 : extern void bitmap_vector_clear (sbitmap *, unsigned int);
275 : extern void bitmap_vector_ones (sbitmap *, unsigned int);
276 :
277 : extern bool bitmap_ior_and_compl (sbitmap, const_sbitmap,
278 : const_sbitmap, const_sbitmap);
279 : extern void bitmap_and_compl (sbitmap, const_sbitmap, const_sbitmap);
280 : extern void bitmap_not (sbitmap, const_sbitmap);
281 : extern bool bitmap_or_and (sbitmap, const_sbitmap,
282 : const_sbitmap, const_sbitmap);
283 : extern bool bitmap_and_or (sbitmap, const_sbitmap,
284 : const_sbitmap, const_sbitmap);
285 : extern bool bitmap_intersect_p (const_sbitmap, const_sbitmap);
286 : extern bool bitmap_and (sbitmap, const_sbitmap, const_sbitmap);
287 : extern bool bitmap_ior (sbitmap, const_sbitmap, const_sbitmap);
288 : extern bool bitmap_xor (sbitmap, const_sbitmap, const_sbitmap);
289 : extern bool bitmap_subset_p (const_sbitmap, const_sbitmap);
290 : extern bool bitmap_bit_in_range_p (const_sbitmap, unsigned int, unsigned int);
291 :
292 : extern int bitmap_first_set_bit (const_sbitmap);
293 : extern int bitmap_last_set_bit (const_sbitmap);
294 :
295 : extern void debug_bitmap (const_sbitmap);
296 : extern sbitmap sbitmap_realloc (sbitmap, unsigned int);
297 :
298 : /* a class that ties the lifetime of a sbitmap to its scope. */
299 : class auto_sbitmap
300 : {
301 : public:
302 : explicit auto_sbitmap (unsigned int size) :
303 : m_bitmap (sbitmap_alloc (size)) {}
304 : ~auto_sbitmap () { sbitmap_free (m_bitmap); }
305 :
306 : /* Allow calling sbitmap functions on our bitmap. */
307 : operator sbitmap () { return m_bitmap; }
308 : operator const_sbitmap () const { return m_bitmap; }
309 :
310 : private:
311 : /* Prevent making a copy that refers to our sbitmap. */
312 : auto_sbitmap (const auto_sbitmap &);
313 : auto_sbitmap &operator = (const auto_sbitmap &);
314 : auto_sbitmap (auto_sbitmap &&);
315 : auto_sbitmap &operator = (auto_sbitmap &&);
316 :
317 : /* The bitmap we are managing. */
318 : sbitmap m_bitmap;
319 : };
320 :
321 : #endif /* ! GCC_SBITMAP_H */
|
