Branch data Line data Source code
1 : : /* Simple bitmaps.
2 : : Copyright (C) 1999-2024 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 : 26776893031 : bitmap_check_index (const_sbitmap map, int index)
103 : : {
104 : 26776893031 : gcc_checking_assert (index >= 0);
105 : 26776893031 : gcc_checking_assert ((unsigned int)index < map->n_bits);
106 : 26776893031 : }
107 : :
108 : : /* Verify that bitmaps A and B have same size. */
109 : :
110 : : inline void
111 : 338525409 : bitmap_check_sizes (const_sbitmap a, const_sbitmap b)
112 : : {
113 : 338525409 : gcc_checking_assert (a->n_bits == b->n_bits);
114 : 338525409 : }
115 : :
116 : : /* Test if bit number bitno in the bitmap is set. */
117 : : inline bool
118 : 15351405508 : bitmap_bit_p (const_sbitmap map, int bitno)
119 : : {
120 : 15351405508 : bitmap_check_index (map, bitno);
121 : :
122 : 15351405508 : size_t i = bitno / SBITMAP_ELT_BITS;
123 : 15351405508 : unsigned int s = bitno % SBITMAP_ELT_BITS;
124 : 15349222699 : 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 : 10754950247 : bitmap_set_bit (sbitmap map, int bitno)
132 : : {
133 : 10754950247 : bitmap_check_index (map, bitno);
134 : :
135 : 10754950247 : size_t i = bitno / SBITMAP_ELT_BITS;
136 : 10754950247 : unsigned int s = bitno % SBITMAP_ELT_BITS;
137 : 10754950247 : if (map->elms[i] & ((SBITMAP_ELT_TYPE) 1 << s))
138 : : return false;
139 : 9392505039 : map->elms[i] |= (SBITMAP_ELT_TYPE) 1 << s;
140 : 9392505039 : 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 : 638874804 : bitmap_clear_bit (sbitmap map, int bitno)
148 : : {
149 : 638874804 : bitmap_check_index (map, bitno);
150 : :
151 : 638874804 : size_t i = bitno / SBITMAP_ELT_BITS;
152 : 638874804 : unsigned int s = bitno % SBITMAP_ELT_BITS;
153 : 638874804 : if (!(map->elms[i] & ((SBITMAP_ELT_TYPE) 1 << s)))
154 : : return false;
155 : 433472185 : map->elms[i] &= ~((SBITMAP_ELT_TYPE) 1 << s);
156 : 433472185 : 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 : 80250840 : bmp_iter_set_init (sbitmap_iterator *i, const_sbitmap bmp,
182 : : unsigned int min, unsigned *bit_no ATTRIBUTE_UNUSED)
183 : : {
184 : 80250840 : i->word_num = min / (unsigned int) SBITMAP_ELT_BITS;
185 : 80250840 : i->bit_num = min;
186 : 80250840 : i->size = bmp->size;
187 : 80250840 : i->ptr = bmp->elms;
188 : :
189 : 80249551 : if (i->word_num >= i->size)
190 : 1 : i->word = 0;
191 : : else
192 : 80250680 : i->word = (i->ptr[i->word_num]
193 : 159 : >> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS));
194 : 159 : }
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 : 433180796 : bmp_iter_set (sbitmap_iterator *i, unsigned int *n)
202 : : {
203 : : /* Skip words that are zeros. */
204 : 495005991 : for (; i->word == 0; i->word = i->ptr[i->word_num])
205 : : {
206 : 141536353 : i->word_num++;
207 : :
208 : : /* If we have reached the end, break. */
209 : 141536353 : if (i->word_num >= i->size)
210 : : return false;
211 : :
212 : 61825195 : i->bit_num = i->word_num * SBITMAP_ELT_BITS;
213 : : }
214 : :
215 : : /* Skip bits that are zero. */
216 : 807696444 : for (; (i->word & 1) == 0; i->word >>= 1)
217 : 454226806 : i->bit_num++;
218 : :
219 : 353469638 : *n = i->bit_num;
220 : :
221 : 353469638 : return true;
222 : : }
223 : :
224 : : /* Advance to the next bit. */
225 : :
226 : : inline void
227 : 352929956 : bmp_iter_next (sbitmap_iterator *i, unsigned *bit_no ATTRIBUTE_UNUSED)
228 : : {
229 : 352929956 : i->word >>= 1;
230 : 352929956 : i->bit_num++;
231 : 352929956 : }
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 : 826021545 : inline void sbitmap_free (sbitmap map)
246 : : {
247 : 798176388 : free (map);
248 : 580652 : }
249 : :
250 : 5120969 : inline void sbitmap_vector_free (sbitmap * vec)
251 : : {
252 : 3113989 : free (vec);
253 : 807115 : }
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 : 751608108 : explicit auto_sbitmap (unsigned int size) :
303 : 761748917 : m_bitmap (sbitmap_alloc (size)) {}
304 : 743914584 : ~auto_sbitmap () { sbitmap_free (m_bitmap); }
305 : :
306 : : /* Allow calling sbitmap functions on our bitmap. */
307 : 3507897140 : operator sbitmap () { return m_bitmap; }
308 : 540032 : 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 */
|
