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