|
0
|
1 /* Functions to support general ended bitmaps.
|
|
|
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
|
|
|
3 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
|
|
|
4
|
|
|
5 This file is part of GCC.
|
|
|
6
|
|
|
7 GCC is free software; you can redistribute it and/or modify it under
|
|
|
8 the terms of the GNU General Public License as published by the Free
|
|
|
9 Software Foundation; either version 3, or (at your option) any later
|
|
|
10 version.
|
|
|
11
|
|
|
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
15 for more details.
|
|
|
16
|
|
|
17 You should have received a copy of the GNU General Public License
|
|
|
18 along with GCC; see the file COPYING3. If not see
|
|
|
19 <http://www.gnu.org/licenses/>. */
|
|
|
20
|
|
|
21 #ifndef GCC_BITMAP_H
|
|
|
22 #define GCC_BITMAP_H
|
|
|
23 #include "hashtab.h"
|
|
|
24 #include "statistics.h"
|
|
|
25 #include "obstack.h"
|
|
|
26
|
|
|
27 /* Fundamental storage type for bitmap. */
|
|
|
28
|
|
|
29 typedef unsigned long BITMAP_WORD;
|
|
|
30 /* BITMAP_WORD_BITS needs to be unsigned, but cannot contain casts as
|
|
|
31 it is used in preprocessor directives -- hence the 1u. */
|
|
|
32 #define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u)
|
|
|
33
|
|
|
34 /* Number of words to use for each element in the linked list. */
|
|
|
35
|
|
|
36 #ifndef BITMAP_ELEMENT_WORDS
|
|
|
37 #define BITMAP_ELEMENT_WORDS ((128 + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
|
|
|
38 #endif
|
|
|
39
|
|
|
40 /* Number of bits in each actual element of a bitmap. */
|
|
|
41
|
|
|
42 #define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)
|
|
|
43
|
|
|
44 /* Obstack for allocating bitmaps and elements from. */
|
|
|
45 typedef struct bitmap_obstack GTY (())
|
|
|
46 {
|
|
|
47 struct bitmap_element_def *elements;
|
|
|
48 struct bitmap_head_def *heads;
|
|
|
49 struct obstack GTY ((skip)) obstack;
|
|
|
50 } bitmap_obstack;
|
|
|
51
|
|
|
52 /* Bitmap set element. We use a linked list to hold only the bits that
|
|
|
53 are set. This allows for use to grow the bitset dynamically without
|
|
|
54 having to realloc and copy a giant bit array.
|
|
|
55
|
|
|
56 The free list is implemented as a list of lists. There is one
|
|
|
57 outer list connected together by prev fields. Each element of that
|
|
|
58 outer is an inner list (that may consist only of the outer list
|
|
|
59 element) that are connected by the next fields. The prev pointer
|
|
|
60 is undefined for interior elements. This allows
|
|
|
61 bitmap_elt_clear_from to be implemented in unit time rather than
|
|
|
62 linear in the number of elements to be freed. */
|
|
|
63
|
|
|
64 typedef struct bitmap_element_def GTY(())
|
|
|
65 {
|
|
|
66 struct bitmap_element_def *next; /* Next element. */
|
|
|
67 struct bitmap_element_def *prev; /* Previous element. */
|
|
|
68 unsigned int indx; /* regno/BITMAP_ELEMENT_ALL_BITS. */
|
|
|
69 BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */
|
|
|
70 } bitmap_element;
|
|
|
71
|
|
|
72 struct bitmap_descriptor;
|
|
|
73 /* Head of bitmap linked list. gengtype ignores ifdefs, but for
|
|
|
74 statistics we need to add a bitmap descriptor pointer. As it is
|
|
|
75 not collected, we can just GTY((skip)) it. */
|
|
|
76
|
|
|
77 typedef struct bitmap_head_def GTY(()) {
|
|
|
78 bitmap_element *first; /* First element in linked list. */
|
|
|
79 bitmap_element *current; /* Last element looked at. */
|
|
|
80 unsigned int indx; /* Index of last element looked at. */
|
|
|
81 bitmap_obstack *obstack; /* Obstack to allocate elements from.
|
|
|
82 If NULL, then use ggc_alloc. */
|
|
|
83 #ifdef GATHER_STATISTICS
|
|
|
84 struct bitmap_descriptor GTY((skip)) *desc;
|
|
|
85 #endif
|
|
|
86 } bitmap_head;
|
|
|
87
|
|
|
88 /* Global data */
|
|
|
89 extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */
|
|
|
90 extern bitmap_obstack bitmap_default_obstack; /* Default bitmap obstack */
|
|
|
91
|
|
|
92 /* Clear a bitmap by freeing up the linked list. */
|
|
|
93 extern void bitmap_clear (bitmap);
|
|
|
94
|
|
|
95 /* Copy a bitmap to another bitmap. */
|
|
|
96 extern void bitmap_copy (bitmap, const_bitmap);
|
|
|
97
|
|
|
98 /* True if two bitmaps are identical. */
|
|
|
99 extern bool bitmap_equal_p (const_bitmap, const_bitmap);
|
|
|
100
|
|
|
101 /* True if the bitmaps intersect (their AND is non-empty). */
|
|
|
102 extern bool bitmap_intersect_p (const_bitmap, const_bitmap);
|
|
|
103
|
|
|
104 /* True if the complement of the second intersects the first (their
|
|
|
105 AND_COMPL is non-empty). */
|
|
|
106 extern bool bitmap_intersect_compl_p (const_bitmap, const_bitmap);
|
|
|
107
|
|
|
108 /* True if MAP is an empty bitmap. */
|
|
|
109 #define bitmap_empty_p(MAP) (!(MAP)->first)
|
|
|
110
|
|
|
111 /* True if the bitmap has only a single bit set. */
|
|
|
112 extern bool bitmap_single_bit_set_p (const_bitmap);
|
|
|
113
|
|
|
114 /* Count the number of bits set in the bitmap. */
|
|
|
115 extern unsigned long bitmap_count_bits (const_bitmap);
|
|
|
116
|
|
|
117 /* Boolean operations on bitmaps. The _into variants are two operand
|
|
|
118 versions that modify the first source operand. The other variants
|
|
|
119 are three operand versions that to not destroy the source bitmaps.
|
|
|
120 The operations supported are &, & ~, |, ^. */
|
|
|
121 extern void bitmap_and (bitmap, const_bitmap, const_bitmap);
|
|
|
122 extern void bitmap_and_into (bitmap, const_bitmap);
|
|
|
123 extern bool bitmap_and_compl (bitmap, const_bitmap, const_bitmap);
|
|
|
124 extern bool bitmap_and_compl_into (bitmap, const_bitmap);
|
|
|
125 #define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A)
|
|
|
126 extern void bitmap_compl_and_into (bitmap, const_bitmap);
|
|
|
127 extern void bitmap_clear_range (bitmap, unsigned int, unsigned int);
|
|
|
128 extern void bitmap_set_range (bitmap, unsigned int, unsigned int);
|
|
|
129 extern bool bitmap_ior (bitmap, const_bitmap, const_bitmap);
|
|
|
130 extern bool bitmap_ior_into (bitmap, const_bitmap);
|
|
|
131 extern void bitmap_xor (bitmap, const_bitmap, const_bitmap);
|
|
|
132 extern void bitmap_xor_into (bitmap, const_bitmap);
|
|
|
133
|
|
|
134 /* DST = A | (B & ~C). Return true if DST changes. */
|
|
|
135 extern bool bitmap_ior_and_compl (bitmap DST, const_bitmap A, const_bitmap B, const_bitmap C);
|
|
|
136 /* A |= (B & ~C). Return true if A changes. */
|
|
|
137 extern bool bitmap_ior_and_compl_into (bitmap DST, const_bitmap B, const_bitmap C);
|
|
|
138
|
|
|
139 /* Clear a single bit in a bitmap. Return true if the bit changed. */
|
|
|
140 extern bool bitmap_clear_bit (bitmap, int);
|
|
|
141
|
|
|
142 /* Set a single bit in a bitmap. Return true if the bit changed. */
|
|
|
143 extern bool bitmap_set_bit (bitmap, int);
|
|
|
144
|
|
|
145 /* Return true if a register is set in a register set. */
|
|
|
146 extern int bitmap_bit_p (bitmap, int);
|
|
|
147
|
|
|
148 /* Debug functions to print a bitmap linked list. */
|
|
|
149 extern void debug_bitmap (const_bitmap);
|
|
|
150 extern void debug_bitmap_file (FILE *, const_bitmap);
|
|
|
151
|
|
|
152 /* Print a bitmap. */
|
|
|
153 extern void bitmap_print (FILE *, const_bitmap, const char *, const char *);
|
|
|
154
|
|
|
155 /* Initialize and release a bitmap obstack. */
|
|
|
156 extern void bitmap_obstack_initialize (bitmap_obstack *);
|
|
|
157 extern void bitmap_obstack_release (bitmap_obstack *);
|
|
|
158 extern void bitmap_register (bitmap MEM_STAT_DECL);
|
|
|
159 extern void dump_bitmap_statistics (void);
|
|
|
160
|
|
|
161 /* Initialize a bitmap header. OBSTACK indicates the bitmap obstack
|
|
|
162 to allocate from, NULL for GC'd bitmap. */
|
|
|
163
|
|
|
164 static inline void
|
|
|
165 bitmap_initialize_stat (bitmap head, bitmap_obstack *obstack MEM_STAT_DECL)
|
|
|
166 {
|
|
|
167 head->first = head->current = NULL;
|
|
|
168 head->obstack = obstack;
|
|
|
169 #ifdef GATHER_STATISTICS
|
|
|
170 bitmap_register (head PASS_MEM_STAT);
|
|
|
171 #endif
|
|
|
172 }
|
|
|
173 #define bitmap_initialize(h,o) bitmap_initialize_stat (h,o MEM_STAT_INFO)
|
|
|
174
|
|
|
175 /* Allocate and free bitmaps from obstack, malloc and gc'd memory. */
|
|
|
176 extern bitmap bitmap_obstack_alloc_stat (bitmap_obstack *obstack MEM_STAT_DECL);
|
|
|
177 #define bitmap_obstack_alloc(t) bitmap_obstack_alloc_stat (t MEM_STAT_INFO)
|
|
|
178 extern bitmap bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL);
|
|
|
179 #define bitmap_gc_alloc() bitmap_gc_alloc_stat (ALONE_MEM_STAT_INFO)
|
|
|
180 extern void bitmap_obstack_free (bitmap);
|
|
|
181
|
|
|
182 /* A few compatibility/functions macros for compatibility with sbitmaps */
|
|
|
183 #define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n")
|
|
|
184 #define bitmap_zero(a) bitmap_clear (a)
|
|
|
185 extern unsigned bitmap_first_set_bit (const_bitmap);
|
|
|
186
|
|
|
187 /* Compute bitmap hash (for purposes of hashing etc.) */
|
|
|
188 extern hashval_t bitmap_hash(const_bitmap);
|
|
|
189
|
|
|
190 /* Allocate a bitmap from a bit obstack. */
|
|
|
191 #define BITMAP_ALLOC(OBSTACK) bitmap_obstack_alloc (OBSTACK)
|
|
|
192
|
|
|
193 /* Allocate a gc'd bitmap. */
|
|
|
194 #define BITMAP_GGC_ALLOC() bitmap_gc_alloc ()
|
|
|
195
|
|
|
196 /* Do any cleanup needed on a bitmap when it is no longer used. */
|
|
|
197 #define BITMAP_FREE(BITMAP) \
|
|
|
198 ((void) (bitmap_obstack_free ((bitmap) BITMAP), (BITMAP) = (bitmap) NULL))
|
|
|
199
|
|
|
200 /* Iterator for bitmaps. */
|
|
|
201
|
|
|
202 typedef struct
|
|
|
203 {
|
|
|
204 /* Pointer to the current bitmap element. */
|
|
|
205 bitmap_element *elt1;
|
|
|
206
|
|
|
207 /* Pointer to 2nd bitmap element when two are involved. */
|
|
|
208 bitmap_element *elt2;
|
|
|
209
|
|
|
210 /* Word within the current element. */
|
|
|
211 unsigned word_no;
|
|
|
212
|
|
|
213 /* Contents of the actually processed word. When finding next bit
|
|
|
214 it is shifted right, so that the actual bit is always the least
|
|
|
215 significant bit of ACTUAL. */
|
|
|
216 BITMAP_WORD bits;
|
|
|
217 } bitmap_iterator;
|
|
|
218
|
|
|
219 /* Initialize a single bitmap iterator. START_BIT is the first bit to
|
|
|
220 iterate from. */
|
|
|
221
|
|
|
222 static inline void
|
|
|
223 bmp_iter_set_init (bitmap_iterator *bi, const_bitmap map,
|
|
|
224 unsigned start_bit, unsigned *bit_no)
|
|
|
225 {
|
|
|
226 bi->elt1 = map->first;
|
|
|
227 bi->elt2 = NULL;
|
|
|
228
|
|
|
229 /* Advance elt1 until it is not before the block containing start_bit. */
|
|
|
230 while (1)
|
|
|
231 {
|
|
|
232 if (!bi->elt1)
|
|
|
233 {
|
|
|
234 bi->elt1 = &bitmap_zero_bits;
|
|
|
235 break;
|
|
|
236 }
|
|
|
237
|
|
|
238 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
|
|
|
239 break;
|
|
|
240 bi->elt1 = bi->elt1->next;
|
|
|
241 }
|
|
|
242
|
|
|
243 /* We might have gone past the start bit, so reinitialize it. */
|
|
|
244 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
|
|
|
245 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
|
|
|
246
|
|
|
247 /* Initialize for what is now start_bit. */
|
|
|
248 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
|
|
|
249 bi->bits = bi->elt1->bits[bi->word_no];
|
|
|
250 bi->bits >>= start_bit % BITMAP_WORD_BITS;
|
|
|
251
|
|
|
252 /* If this word is zero, we must make sure we're not pointing at the
|
|
|
253 first bit, otherwise our incrementing to the next word boundary
|
|
|
254 will fail. It won't matter if this increment moves us into the
|
|
|
255 next word. */
|
|
|
256 start_bit += !bi->bits;
|
|
|
257
|
|
|
258 *bit_no = start_bit;
|
|
|
259 }
|
|
|
260
|
|
|
261 /* Initialize an iterator to iterate over the intersection of two
|
|
|
262 bitmaps. START_BIT is the bit to commence from. */
|
|
|
263
|
|
|
264 static inline void
|
|
|
265 bmp_iter_and_init (bitmap_iterator *bi, const_bitmap map1, const_bitmap map2,
|
|
|
266 unsigned start_bit, unsigned *bit_no)
|
|
|
267 {
|
|
|
268 bi->elt1 = map1->first;
|
|
|
269 bi->elt2 = map2->first;
|
|
|
270
|
|
|
271 /* Advance elt1 until it is not before the block containing
|
|
|
272 start_bit. */
|
|
|
273 while (1)
|
|
|
274 {
|
|
|
275 if (!bi->elt1)
|
|
|
276 {
|
|
|
277 bi->elt2 = NULL;
|
|
|
278 break;
|
|
|
279 }
|
|
|
280
|
|
|
281 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
|
|
|
282 break;
|
|
|
283 bi->elt1 = bi->elt1->next;
|
|
|
284 }
|
|
|
285
|
|
|
286 /* Advance elt2 until it is not before elt1. */
|
|
|
287 while (1)
|
|
|
288 {
|
|
|
289 if (!bi->elt2)
|
|
|
290 {
|
|
|
291 bi->elt1 = bi->elt2 = &bitmap_zero_bits;
|
|
|
292 break;
|
|
|
293 }
|
|
|
294
|
|
|
295 if (bi->elt2->indx >= bi->elt1->indx)
|
|
|
296 break;
|
|
|
297 bi->elt2 = bi->elt2->next;
|
|
|
298 }
|
|
|
299
|
|
|
300 /* If we're at the same index, then we have some intersecting bits. */
|
|
|
301 if (bi->elt1->indx == bi->elt2->indx)
|
|
|
302 {
|
|
|
303 /* We might have advanced beyond the start_bit, so reinitialize
|
|
|
304 for that. */
|
|
|
305 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
|
|
|
306 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
|
|
|
307
|
|
|
308 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
|
|
|
309 bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
|
|
|
310 bi->bits >>= start_bit % BITMAP_WORD_BITS;
|
|
|
311 }
|
|
|
312 else
|
|
|
313 {
|
|
|
314 /* Otherwise we must immediately advance elt1, so initialize for
|
|
|
315 that. */
|
|
|
316 bi->word_no = BITMAP_ELEMENT_WORDS - 1;
|
|
|
317 bi->bits = 0;
|
|
|
318 }
|
|
|
319
|
|
|
320 /* If this word is zero, we must make sure we're not pointing at the
|
|
|
321 first bit, otherwise our incrementing to the next word boundary
|
|
|
322 will fail. It won't matter if this increment moves us into the
|
|
|
323 next word. */
|
|
|
324 start_bit += !bi->bits;
|
|
|
325
|
|
|
326 *bit_no = start_bit;
|
|
|
327 }
|
|
|
328
|
|
|
329 /* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2.
|
|
|
330 */
|
|
|
331
|
|
|
332 static inline void
|
|
|
333 bmp_iter_and_compl_init (bitmap_iterator *bi, const_bitmap map1, const_bitmap map2,
|
|
|
334 unsigned start_bit, unsigned *bit_no)
|
|
|
335 {
|
|
|
336 bi->elt1 = map1->first;
|
|
|
337 bi->elt2 = map2->first;
|
|
|
338
|
|
|
339 /* Advance elt1 until it is not before the block containing start_bit. */
|
|
|
340 while (1)
|
|
|
341 {
|
|
|
342 if (!bi->elt1)
|
|
|
343 {
|
|
|
344 bi->elt1 = &bitmap_zero_bits;
|
|
|
345 break;
|
|
|
346 }
|
|
|
347
|
|
|
348 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
|
|
|
349 break;
|
|
|
350 bi->elt1 = bi->elt1->next;
|
|
|
351 }
|
|
|
352
|
|
|
353 /* Advance elt2 until it is not before elt1. */
|
|
|
354 while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
|
|
|
355 bi->elt2 = bi->elt2->next;
|
|
|
356
|
|
|
357 /* We might have advanced beyond the start_bit, so reinitialize for
|
|
|
358 that. */
|
|
|
359 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
|
|
|
360 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
|
|
|
361
|
|
|
362 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
|
|
|
363 bi->bits = bi->elt1->bits[bi->word_no];
|
|
|
364 if (bi->elt2 && bi->elt1->indx == bi->elt2->indx)
|
|
|
365 bi->bits &= ~bi->elt2->bits[bi->word_no];
|
|
|
366 bi->bits >>= start_bit % BITMAP_WORD_BITS;
|
|
|
367
|
|
|
368 /* If this word is zero, we must make sure we're not pointing at the
|
|
|
369 first bit, otherwise our incrementing to the next word boundary
|
|
|
370 will fail. It won't matter if this increment moves us into the
|
|
|
371 next word. */
|
|
|
372 start_bit += !bi->bits;
|
|
|
373
|
|
|
374 *bit_no = start_bit;
|
|
|
375 }
|
|
|
376
|
|
|
377 /* Advance to the next bit in BI. We don't advance to the next
|
|
|
378 nonzero bit yet. */
|
|
|
379
|
|
|
380 static inline void
|
|
|
381 bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no)
|
|
|
382 {
|
|
|
383 bi->bits >>= 1;
|
|
|
384 *bit_no += 1;
|
|
|
385 }
|
|
|
386
|
|
|
387 /* Advance to the next nonzero bit of a single bitmap, we will have
|
|
|
388 already advanced past the just iterated bit. Return true if there
|
|
|
389 is a bit to iterate. */
|
|
|
390
|
|
|
391 static inline bool
|
|
|
392 bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no)
|
|
|
393 {
|
|
|
394 /* If our current word is nonzero, it contains the bit we want. */
|
|
|
395 if (bi->bits)
|
|
|
396 {
|
|
|
397 next_bit:
|
|
|
398 while (!(bi->bits & 1))
|
|
|
399 {
|
|
|
400 bi->bits >>= 1;
|
|
|
401 *bit_no += 1;
|
|
|
402 }
|
|
|
403 return true;
|
|
|
404 }
|
|
|
405
|
|
|
406 /* Round up to the word boundary. We might have just iterated past
|
|
|
407 the end of the last word, hence the -1. It is not possible for
|
|
|
408 bit_no to point at the beginning of the now last word. */
|
|
|
409 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
|
|
|
410 / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
|
|
|
411 bi->word_no++;
|
|
|
412
|
|
|
413 while (1)
|
|
|
414 {
|
|
|
415 /* Find the next nonzero word in this elt. */
|
|
|
416 while (bi->word_no != BITMAP_ELEMENT_WORDS)
|
|
|
417 {
|
|
|
418 bi->bits = bi->elt1->bits[bi->word_no];
|
|
|
419 if (bi->bits)
|
|
|
420 goto next_bit;
|
|
|
421 *bit_no += BITMAP_WORD_BITS;
|
|
|
422 bi->word_no++;
|
|
|
423 }
|
|
|
424
|
|
|
425 /* Advance to the next element. */
|
|
|
426 bi->elt1 = bi->elt1->next;
|
|
|
427 if (!bi->elt1)
|
|
|
428 return false;
|
|
|
429 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
|
|
|
430 bi->word_no = 0;
|
|
|
431 }
|
|
|
432 }
|
|
|
433
|
|
|
434 /* Advance to the next nonzero bit of an intersecting pair of
|
|
|
435 bitmaps. We will have already advanced past the just iterated bit.
|
|
|
436 Return true if there is a bit to iterate. */
|
|
|
437
|
|
|
438 static inline bool
|
|
|
439 bmp_iter_and (bitmap_iterator *bi, unsigned *bit_no)
|
|
|
440 {
|
|
|
441 /* If our current word is nonzero, it contains the bit we want. */
|
|
|
442 if (bi->bits)
|
|
|
443 {
|
|
|
444 next_bit:
|
|
|
445 while (!(bi->bits & 1))
|
|
|
446 {
|
|
|
447 bi->bits >>= 1;
|
|
|
448 *bit_no += 1;
|
|
|
449 }
|
|
|
450 return true;
|
|
|
451 }
|
|
|
452
|
|
|
453 /* Round up to the word boundary. We might have just iterated past
|
|
|
454 the end of the last word, hence the -1. It is not possible for
|
|
|
455 bit_no to point at the beginning of the now last word. */
|
|
|
456 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
|
|
|
457 / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
|
|
|
458 bi->word_no++;
|
|
|
459
|
|
|
460 while (1)
|
|
|
461 {
|
|
|
462 /* Find the next nonzero word in this elt. */
|
|
|
463 while (bi->word_no != BITMAP_ELEMENT_WORDS)
|
|
|
464 {
|
|
|
465 bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
|
|
|
466 if (bi->bits)
|
|
|
467 goto next_bit;
|
|
|
468 *bit_no += BITMAP_WORD_BITS;
|
|
|
469 bi->word_no++;
|
|
|
470 }
|
|
|
471
|
|
|
472 /* Advance to the next identical element. */
|
|
|
473 do
|
|
|
474 {
|
|
|
475 /* Advance elt1 while it is less than elt2. We always want
|
|
|
476 to advance one elt. */
|
|
|
477 do
|
|
|
478 {
|
|
|
479 bi->elt1 = bi->elt1->next;
|
|
|
480 if (!bi->elt1)
|
|
|
481 return false;
|
|
|
482 }
|
|
|
483 while (bi->elt1->indx < bi->elt2->indx);
|
|
|
484
|
|
|
485 /* Advance elt2 to be no less than elt1. This might not
|
|
|
486 advance. */
|
|
|
487 while (bi->elt2->indx < bi->elt1->indx)
|
|
|
488 {
|
|
|
489 bi->elt2 = bi->elt2->next;
|
|
|
490 if (!bi->elt2)
|
|
|
491 return false;
|
|
|
492 }
|
|
|
493 }
|
|
|
494 while (bi->elt1->indx != bi->elt2->indx);
|
|
|
495
|
|
|
496 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
|
|
|
497 bi->word_no = 0;
|
|
|
498 }
|
|
|
499 }
|
|
|
500
|
|
|
501 /* Advance to the next nonzero bit in the intersection of
|
|
|
502 complemented bitmaps. We will have already advanced past the just
|
|
|
503 iterated bit. */
|
|
|
504
|
|
|
505 static inline bool
|
|
|
506 bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no)
|
|
|
507 {
|
|
|
508 /* If our current word is nonzero, it contains the bit we want. */
|
|
|
509 if (bi->bits)
|
|
|
510 {
|
|
|
511 next_bit:
|
|
|
512 while (!(bi->bits & 1))
|
|
|
513 {
|
|
|
514 bi->bits >>= 1;
|
|
|
515 *bit_no += 1;
|
|
|
516 }
|
|
|
517 return true;
|
|
|
518 }
|
|
|
519
|
|
|
520 /* Round up to the word boundary. We might have just iterated past
|
|
|
521 the end of the last word, hence the -1. It is not possible for
|
|
|
522 bit_no to point at the beginning of the now last word. */
|
|
|
523 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
|
|
|
524 / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
|
|
|
525 bi->word_no++;
|
|
|
526
|
|
|
527 while (1)
|
|
|
528 {
|
|
|
529 /* Find the next nonzero word in this elt. */
|
|
|
530 while (bi->word_no != BITMAP_ELEMENT_WORDS)
|
|
|
531 {
|
|
|
532 bi->bits = bi->elt1->bits[bi->word_no];
|
|
|
533 if (bi->elt2 && bi->elt2->indx == bi->elt1->indx)
|
|
|
534 bi->bits &= ~bi->elt2->bits[bi->word_no];
|
|
|
535 if (bi->bits)
|
|
|
536 goto next_bit;
|
|
|
537 *bit_no += BITMAP_WORD_BITS;
|
|
|
538 bi->word_no++;
|
|
|
539 }
|
|
|
540
|
|
|
541 /* Advance to the next element of elt1. */
|
|
|
542 bi->elt1 = bi->elt1->next;
|
|
|
543 if (!bi->elt1)
|
|
|
544 return false;
|
|
|
545
|
|
|
546 /* Advance elt2 until it is no less than elt1. */
|
|
|
547 while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
|
|
|
548 bi->elt2 = bi->elt2->next;
|
|
|
549
|
|
|
550 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
|
|
|
551 bi->word_no = 0;
|
|
|
552 }
|
|
|
553 }
|
|
|
554
|
|
|
555 /* Loop over all bits set in BITMAP, starting with MIN and setting
|
|
|
556 BITNUM to the bit number. ITER is a bitmap iterator. BITNUM
|
|
|
557 should be treated as a read-only variable as it contains loop
|
|
|
558 state. */
|
|
|
559
|
|
|
560 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \
|
|
|
561 for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \
|
|
|
562 bmp_iter_set (&(ITER), &(BITNUM)); \
|
|
|
563 bmp_iter_next (&(ITER), &(BITNUM)))
|
|
|
564
|
|
|
565 /* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN
|
|
|
566 and setting BITNUM to the bit number. ITER is a bitmap iterator.
|
|
|
567 BITNUM should be treated as a read-only variable as it contains
|
|
|
568 loop state. */
|
|
|
569
|
|
|
570 #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
|
|
|
571 for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
|
|
|
572 &(BITNUM)); \
|
|
|
573 bmp_iter_and (&(ITER), &(BITNUM)); \
|
|
|
574 bmp_iter_next (&(ITER), &(BITNUM)))
|
|
|
575
|
|
|
576 /* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN
|
|
|
577 and setting BITNUM to the bit number. ITER is a bitmap iterator.
|
|
|
578 BITNUM should be treated as a read-only variable as it contains
|
|
|
579 loop state. */
|
|
|
580
|
|
|
581 #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
|
|
|
582 for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
|
|
|
583 &(BITNUM)); \
|
|
|
584 bmp_iter_and_compl (&(ITER), &(BITNUM)); \
|
|
|
585 bmp_iter_next (&(ITER), &(BITNUM)))
|
|
|
586
|
|
|
587 #endif /* GCC_BITMAP_H */
|
