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 | bitmap_check_index (const_sbitmap map, int index) |
103 | { |
104 | gcc_checking_assert (index >= 0); |
105 | gcc_checking_assert ((unsigned int)index < map->n_bits); |
106 | } |
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 | bitmap_bit_p (const_sbitmap map, int bitno) |
119 | { |
120 | bitmap_check_index (map, index: bitno); |
121 | |
122 | size_t i = bitno / SBITMAP_ELT_BITS; |
123 | unsigned int s = bitno % SBITMAP_ELT_BITS; |
124 | 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 | bitmap_set_bit (sbitmap map, int bitno) |
132 | { |
133 | bitmap_check_index (map, index: bitno); |
134 | |
135 | size_t i = bitno / SBITMAP_ELT_BITS; |
136 | unsigned int s = bitno % SBITMAP_ELT_BITS; |
137 | if (map->elms[i] & ((SBITMAP_ELT_TYPE) 1 << s)) |
138 | return false; |
139 | map->elms[i] |= (SBITMAP_ELT_TYPE) 1 << s; |
140 | 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, index: 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 (ptr: map); |
248 | } |
249 | |
250 | inline void sbitmap_vector_free (sbitmap * vec) |
251 | { |
252 | free (ptr: 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 (map: 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 */ |
322 | |