1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997-2013 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 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "obstack.h"
24 #include "ggc.h"
25 #include "bitmap.h"
26 #include "hashtab.h"
27 #include "vec.h"
28
29 /* Store information about each particular bitmap, per allocation site. */
30 struct bitmap_descriptor_d
31 {
32 int id;
33 const char *function;
34 const char *file;
35 int line;
36 int created;
37 unsigned HOST_WIDEST_INT allocated;
38 unsigned HOST_WIDEST_INT peak;
39 unsigned HOST_WIDEST_INT current;
40 unsigned HOST_WIDEST_INT nsearches;
41 unsigned HOST_WIDEST_INT search_iter;
42 };
43
44 typedef struct bitmap_descriptor_d *bitmap_descriptor;
45 typedef const struct bitmap_descriptor_d *const_bitmap_descriptor;
46
47 /* Next available unique id number for bitmap desciptors. */
48 static int next_bitmap_desc_id = 0;
49
50 /* Vector mapping descriptor ids to descriptors. */
51 static vec<bitmap_descriptor> bitmap_descriptors;
52
53 /* Hashtable mapping bitmap names to descriptors. */
54 static htab_t bitmap_desc_hash;
55
56 /* Hashtable helpers. */
57 static hashval_t
hash_descriptor(const void * p)58 hash_descriptor (const void *p)
59 {
60 const_bitmap_descriptor d = (const_bitmap_descriptor) p;
61 return htab_hash_pointer (d->file) + d->line;
62 }
63 struct loc
64 {
65 const char *file;
66 const char *function;
67 int line;
68 };
69 static int
eq_descriptor(const void * p1,const void * p2)70 eq_descriptor (const void *p1, const void *p2)
71 {
72 const_bitmap_descriptor d = (const_bitmap_descriptor) p1;
73 const struct loc *const l = (const struct loc *) p2;
74 return d->file == l->file && d->function == l->function && d->line == l->line;
75 }
76
77 /* For given file and line, return descriptor, create new if needed. */
78 static bitmap_descriptor
get_bitmap_descriptor(const char * file,int line,const char * function)79 get_bitmap_descriptor (const char *file, int line, const char *function)
80 {
81 bitmap_descriptor *slot;
82 struct loc loc;
83
84 loc.file = file;
85 loc.function = function;
86 loc.line = line;
87
88 if (!bitmap_desc_hash)
89 bitmap_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
90
91 slot = (bitmap_descriptor *)
92 htab_find_slot_with_hash (bitmap_desc_hash, &loc,
93 htab_hash_pointer (file) + line,
94 INSERT);
95 if (*slot)
96 return *slot;
97
98 *slot = XCNEW (struct bitmap_descriptor_d);
99 bitmap_descriptors.safe_push (*slot);
100 (*slot)->id = next_bitmap_desc_id++;
101 (*slot)->file = file;
102 (*slot)->function = function;
103 (*slot)->line = line;
104 return *slot;
105 }
106
107 /* Register new bitmap. */
108 void
bitmap_register(bitmap b MEM_STAT_DECL)109 bitmap_register (bitmap b MEM_STAT_DECL)
110 {
111 bitmap_descriptor desc = get_bitmap_descriptor (ALONE_FINAL_PASS_MEM_STAT);
112 desc->created++;
113 b->descriptor_id = desc->id;
114 }
115
116 /* Account the overhead. */
117 static void
register_overhead(bitmap b,int amount)118 register_overhead (bitmap b, int amount)
119 {
120 bitmap_descriptor desc = bitmap_descriptors[b->descriptor_id];
121 desc->current += amount;
122 if (amount > 0)
123 desc->allocated += amount;
124 if (desc->peak < desc->current)
125 desc->peak = desc->current;
126 }
127
128 /* Global data */
129 bitmap_element bitmap_zero_bits; /* An element of all zero bits. */
130 bitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */
131 static int bitmap_default_obstack_depth;
132 static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of
133 GC'd elements. */
134
135 static void bitmap_elem_to_freelist (bitmap, bitmap_element *);
136 static void bitmap_element_free (bitmap, bitmap_element *);
137 static bitmap_element *bitmap_element_allocate (bitmap);
138 static int bitmap_element_zerop (const bitmap_element *);
139 static void bitmap_element_link (bitmap, bitmap_element *);
140 static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int);
141 static void bitmap_elt_clear_from (bitmap, bitmap_element *);
142 static bitmap_element *bitmap_find_bit (bitmap, unsigned int);
143
144
145 /* Add ELEM to the appropriate freelist. */
146 static inline void
bitmap_elem_to_freelist(bitmap head,bitmap_element * elt)147 bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
148 {
149 bitmap_obstack *bit_obstack = head->obstack;
150
151 elt->next = NULL;
152 if (bit_obstack)
153 {
154 elt->prev = bit_obstack->elements;
155 bit_obstack->elements = elt;
156 }
157 else
158 {
159 elt->prev = bitmap_ggc_free;
160 bitmap_ggc_free = elt;
161 }
162 }
163
164 /* Free a bitmap element. Since these are allocated off the
165 bitmap_obstack, "free" actually means "put onto the freelist". */
166
167 static inline void
bitmap_element_free(bitmap head,bitmap_element * elt)168 bitmap_element_free (bitmap head, bitmap_element *elt)
169 {
170 bitmap_element *next = elt->next;
171 bitmap_element *prev = elt->prev;
172
173 if (prev)
174 prev->next = next;
175
176 if (next)
177 next->prev = prev;
178
179 if (head->first == elt)
180 head->first = next;
181
182 /* Since the first thing we try is to insert before current,
183 make current the next entry in preference to the previous. */
184 if (head->current == elt)
185 {
186 head->current = next != 0 ? next : prev;
187 if (head->current)
188 head->indx = head->current->indx;
189 else
190 head->indx = 0;
191 }
192
193 if (GATHER_STATISTICS)
194 register_overhead (head, -((int)sizeof (bitmap_element)));
195
196 bitmap_elem_to_freelist (head, elt);
197 }
198
199 /* Allocate a bitmap element. The bits are cleared, but nothing else is. */
200
201 static inline bitmap_element *
bitmap_element_allocate(bitmap head)202 bitmap_element_allocate (bitmap head)
203 {
204 bitmap_element *element;
205 bitmap_obstack *bit_obstack = head->obstack;
206
207 if (bit_obstack)
208 {
209 element = bit_obstack->elements;
210
211 if (element)
212 /* Use up the inner list first before looking at the next
213 element of the outer list. */
214 if (element->next)
215 {
216 bit_obstack->elements = element->next;
217 bit_obstack->elements->prev = element->prev;
218 }
219 else
220 /* Inner list was just a singleton. */
221 bit_obstack->elements = element->prev;
222 else
223 element = XOBNEW (&bit_obstack->obstack, bitmap_element);
224 }
225 else
226 {
227 element = bitmap_ggc_free;
228 if (element)
229 /* Use up the inner list first before looking at the next
230 element of the outer list. */
231 if (element->next)
232 {
233 bitmap_ggc_free = element->next;
234 bitmap_ggc_free->prev = element->prev;
235 }
236 else
237 /* Inner list was just a singleton. */
238 bitmap_ggc_free = element->prev;
239 else
240 element = ggc_alloc_bitmap_element_def ();
241 }
242
243 if (GATHER_STATISTICS)
244 register_overhead (head, sizeof (bitmap_element));
245
246 memset (element->bits, 0, sizeof (element->bits));
247
248 return element;
249 }
250
251 /* Remove ELT and all following elements from bitmap HEAD. */
252
253 void
bitmap_elt_clear_from(bitmap head,bitmap_element * elt)254 bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
255 {
256 bitmap_element *prev;
257 bitmap_obstack *bit_obstack = head->obstack;
258
259 if (!elt) return;
260
261 if (GATHER_STATISTICS)
262 {
263 int n = 0;
264 for (prev = elt; prev; prev = prev->next)
265 n++;
266 register_overhead (head, -sizeof (bitmap_element) * n);
267 }
268
269 prev = elt->prev;
270 if (prev)
271 {
272 prev->next = NULL;
273 if (head->current->indx > prev->indx)
274 {
275 head->current = prev;
276 head->indx = prev->indx;
277 }
278 }
279 else
280 {
281 head->first = NULL;
282 head->current = NULL;
283 head->indx = 0;
284 }
285
286 /* Put the entire list onto the free list in one operation. */
287 if (bit_obstack)
288 {
289 elt->prev = bit_obstack->elements;
290 bit_obstack->elements = elt;
291 }
292 else
293 {
294 elt->prev = bitmap_ggc_free;
295 bitmap_ggc_free = elt;
296 }
297 }
298
299 /* Clear a bitmap by freeing the linked list. */
300
301 void
bitmap_clear(bitmap head)302 bitmap_clear (bitmap head)
303 {
304 if (head->first)
305 bitmap_elt_clear_from (head, head->first);
306 }
307
308 /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
309 the default bitmap obstack. */
310
311 void
bitmap_obstack_initialize(bitmap_obstack * bit_obstack)312 bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
313 {
314 if (!bit_obstack)
315 {
316 if (bitmap_default_obstack_depth++)
317 return;
318 bit_obstack = &bitmap_default_obstack;
319 }
320
321 #if !defined(__GNUC__) || (__GNUC__ < 2)
322 #define __alignof__(type) 0
323 #endif
324
325 bit_obstack->elements = NULL;
326 bit_obstack->heads = NULL;
327 obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE,
328 __alignof__ (bitmap_element),
329 obstack_chunk_alloc,
330 obstack_chunk_free);
331 }
332
333 /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL,
334 release the default bitmap obstack. */
335
336 void
bitmap_obstack_release(bitmap_obstack * bit_obstack)337 bitmap_obstack_release (bitmap_obstack *bit_obstack)
338 {
339 if (!bit_obstack)
340 {
341 if (--bitmap_default_obstack_depth)
342 {
343 gcc_assert (bitmap_default_obstack_depth > 0);
344 return;
345 }
346 bit_obstack = &bitmap_default_obstack;
347 }
348
349 bit_obstack->elements = NULL;
350 bit_obstack->heads = NULL;
351 obstack_free (&bit_obstack->obstack, NULL);
352 }
353
354 /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create
355 it on the default bitmap obstack. */
356
357 bitmap
bitmap_obstack_alloc_stat(bitmap_obstack * bit_obstack MEM_STAT_DECL)358 bitmap_obstack_alloc_stat (bitmap_obstack *bit_obstack MEM_STAT_DECL)
359 {
360 bitmap map;
361
362 if (!bit_obstack)
363 bit_obstack = &bitmap_default_obstack;
364 map = bit_obstack->heads;
365 if (map)
366 bit_obstack->heads = (struct bitmap_head_def *) map->first;
367 else
368 map = XOBNEW (&bit_obstack->obstack, bitmap_head);
369 bitmap_initialize_stat (map, bit_obstack PASS_MEM_STAT);
370
371 if (GATHER_STATISTICS)
372 register_overhead (map, sizeof (bitmap_head));
373
374 return map;
375 }
376
377 /* Create a new GCd bitmap. */
378
379 bitmap
bitmap_gc_alloc_stat(ALONE_MEM_STAT_DECL)380 bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL)
381 {
382 bitmap map;
383
384 map = ggc_alloc_bitmap_head_def ();
385 bitmap_initialize_stat (map, NULL PASS_MEM_STAT);
386
387 if (GATHER_STATISTICS)
388 register_overhead (map, sizeof (bitmap_head));
389
390 return map;
391 }
392
393 /* Release an obstack allocated bitmap. */
394
395 void
bitmap_obstack_free(bitmap map)396 bitmap_obstack_free (bitmap map)
397 {
398 if (map)
399 {
400 bitmap_clear (map);
401 map->first = (bitmap_element *) map->obstack->heads;
402
403 if (GATHER_STATISTICS)
404 register_overhead (map, -((int)sizeof (bitmap_head)));
405
406 map->obstack->heads = map;
407 }
408 }
409
410
411 /* Return nonzero if all bits in an element are zero. */
412
413 static inline int
bitmap_element_zerop(const bitmap_element * element)414 bitmap_element_zerop (const bitmap_element *element)
415 {
416 #if BITMAP_ELEMENT_WORDS == 2
417 return (element->bits[0] | element->bits[1]) == 0;
418 #else
419 unsigned i;
420
421 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
422 if (element->bits[i] != 0)
423 return 0;
424
425 return 1;
426 #endif
427 }
428
429 /* Link the bitmap element into the current bitmap linked list. */
430
431 static inline void
bitmap_element_link(bitmap head,bitmap_element * element)432 bitmap_element_link (bitmap head, bitmap_element *element)
433 {
434 unsigned int indx = element->indx;
435 bitmap_element *ptr;
436
437 /* If this is the first and only element, set it in. */
438 if (head->first == 0)
439 {
440 element->next = element->prev = 0;
441 head->first = element;
442 }
443
444 /* If this index is less than that of the current element, it goes someplace
445 before the current element. */
446 else if (indx < head->indx)
447 {
448 for (ptr = head->current;
449 ptr->prev != 0 && ptr->prev->indx > indx;
450 ptr = ptr->prev)
451 ;
452
453 if (ptr->prev)
454 ptr->prev->next = element;
455 else
456 head->first = element;
457
458 element->prev = ptr->prev;
459 element->next = ptr;
460 ptr->prev = element;
461 }
462
463 /* Otherwise, it must go someplace after the current element. */
464 else
465 {
466 for (ptr = head->current;
467 ptr->next != 0 && ptr->next->indx < indx;
468 ptr = ptr->next)
469 ;
470
471 if (ptr->next)
472 ptr->next->prev = element;
473
474 element->next = ptr->next;
475 element->prev = ptr;
476 ptr->next = element;
477 }
478
479 /* Set up so this is the first element searched. */
480 head->current = element;
481 head->indx = indx;
482 }
483
484 /* Insert a new uninitialized element into bitmap HEAD after element
485 ELT. If ELT is NULL, insert the element at the start. Return the
486 new element. */
487
488 static bitmap_element *
bitmap_elt_insert_after(bitmap head,bitmap_element * elt,unsigned int indx)489 bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx)
490 {
491 bitmap_element *node = bitmap_element_allocate (head);
492 node->indx = indx;
493
494 if (!elt)
495 {
496 if (!head->current)
497 {
498 head->current = node;
499 head->indx = indx;
500 }
501 node->next = head->first;
502 if (node->next)
503 node->next->prev = node;
504 head->first = node;
505 node->prev = NULL;
506 }
507 else
508 {
509 gcc_checking_assert (head->current);
510 node->next = elt->next;
511 if (node->next)
512 node->next->prev = node;
513 elt->next = node;
514 node->prev = elt;
515 }
516 return node;
517 }
518
519 /* Copy a bitmap to another bitmap. */
520
521 void
bitmap_copy(bitmap to,const_bitmap from)522 bitmap_copy (bitmap to, const_bitmap from)
523 {
524 const bitmap_element *from_ptr;
525 bitmap_element *to_ptr = 0;
526
527 bitmap_clear (to);
528
529 /* Copy elements in forward direction one at a time. */
530 for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
531 {
532 bitmap_element *to_elt = bitmap_element_allocate (to);
533
534 to_elt->indx = from_ptr->indx;
535 memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits));
536
537 /* Here we have a special case of bitmap_element_link, for the case
538 where we know the links are being entered in sequence. */
539 if (to_ptr == 0)
540 {
541 to->first = to->current = to_elt;
542 to->indx = from_ptr->indx;
543 to_elt->next = to_elt->prev = 0;
544 }
545 else
546 {
547 to_elt->prev = to_ptr;
548 to_elt->next = 0;
549 to_ptr->next = to_elt;
550 }
551
552 to_ptr = to_elt;
553 }
554 }
555
556 /* Find a bitmap element that would hold a bitmap's bit.
557 Update the `current' field even if we can't find an element that
558 would hold the bitmap's bit to make eventual allocation
559 faster. */
560
561 static inline bitmap_element *
bitmap_find_bit(bitmap head,unsigned int bit)562 bitmap_find_bit (bitmap head, unsigned int bit)
563 {
564 bitmap_element *element;
565 unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
566
567 if (head->current == NULL
568 || head->indx == indx)
569 return head->current;
570 if (head->current == head->first
571 && head->first->next == NULL)
572 return NULL;
573
574 /* This bitmap has more than one element, and we're going to look
575 through the elements list. Count that as a search. */
576 if (GATHER_STATISTICS)
577 bitmap_descriptors[head->descriptor_id]->nsearches++;
578
579 if (head->indx < indx)
580 /* INDX is beyond head->indx. Search from head->current
581 forward. */
582 for (element = head->current;
583 element->next != 0 && element->indx < indx;
584 element = element->next)
585 {
586 if (GATHER_STATISTICS)
587 bitmap_descriptors[head->descriptor_id]->search_iter++;
588 }
589
590 else if (head->indx / 2 < indx)
591 /* INDX is less than head->indx and closer to head->indx than to
592 0. Search from head->current backward. */
593 for (element = head->current;
594 element->prev != 0 && element->indx > indx;
595 element = element->prev)
596 {
597 if (GATHER_STATISTICS)
598 bitmap_descriptors[head->descriptor_id]->search_iter++;
599 }
600
601 else
602 /* INDX is less than head->indx and closer to 0 than to
603 head->indx. Search from head->first forward. */
604 for (element = head->first;
605 element->next != 0 && element->indx < indx;
606 element = element->next)
607 if (GATHER_STATISTICS)
608 {
609 bitmap_descriptors[head->descriptor_id]->search_iter++;
610 }
611
612 /* `element' is the nearest to the one we want. If it's not the one we
613 want, the one we want doesn't exist. */
614 head->current = element;
615 head->indx = element->indx;
616 if (element != 0 && element->indx != indx)
617 element = 0;
618
619 return element;
620 }
621
622 /* Clear a single bit in a bitmap. Return true if the bit changed. */
623
624 bool
bitmap_clear_bit(bitmap head,int bit)625 bitmap_clear_bit (bitmap head, int bit)
626 {
627 bitmap_element *const ptr = bitmap_find_bit (head, bit);
628
629 if (ptr != 0)
630 {
631 unsigned bit_num = bit % BITMAP_WORD_BITS;
632 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
633 BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
634 bool res = (ptr->bits[word_num] & bit_val) != 0;
635 if (res)
636 {
637 ptr->bits[word_num] &= ~bit_val;
638 /* If we cleared the entire word, free up the element. */
639 if (!ptr->bits[word_num]
640 && bitmap_element_zerop (ptr))
641 bitmap_element_free (head, ptr);
642 }
643
644 return res;
645 }
646
647 return false;
648 }
649
650 /* Set a single bit in a bitmap. Return true if the bit changed. */
651
652 bool
bitmap_set_bit(bitmap head,int bit)653 bitmap_set_bit (bitmap head, int bit)
654 {
655 bitmap_element *ptr = bitmap_find_bit (head, bit);
656 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
657 unsigned bit_num = bit % BITMAP_WORD_BITS;
658 BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
659
660 if (ptr == 0)
661 {
662 ptr = bitmap_element_allocate (head);
663 ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
664 ptr->bits[word_num] = bit_val;
665 bitmap_element_link (head, ptr);
666 return true;
667 }
668 else
669 {
670 bool res = (ptr->bits[word_num] & bit_val) == 0;
671 if (res)
672 ptr->bits[word_num] |= bit_val;
673 return res;
674 }
675 }
676
677 /* Return whether a bit is set within a bitmap. */
678
679 int
bitmap_bit_p(bitmap head,int bit)680 bitmap_bit_p (bitmap head, int bit)
681 {
682 bitmap_element *ptr;
683 unsigned bit_num;
684 unsigned word_num;
685
686 ptr = bitmap_find_bit (head, bit);
687 if (ptr == 0)
688 return 0;
689
690 bit_num = bit % BITMAP_WORD_BITS;
691 word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
692
693 return (ptr->bits[word_num] >> bit_num) & 1;
694 }
695
696 #if GCC_VERSION < 3400
697 /* Table of number of set bits in a character, indexed by value of char. */
698 static const unsigned char popcount_table[] =
699 {
700 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
701 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
702 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
703 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
704 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
705 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
706 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
707 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
708 };
709
710 static unsigned long
bitmap_popcount(BITMAP_WORD a)711 bitmap_popcount (BITMAP_WORD a)
712 {
713 unsigned long ret = 0;
714 unsigned i;
715
716 /* Just do this the table way for now */
717 for (i = 0; i < BITMAP_WORD_BITS; i+= 8)
718 ret += popcount_table[(a >> i) & 0xff];
719 return ret;
720 }
721 #endif
722 /* Count the number of bits set in the bitmap, and return it. */
723
724 unsigned long
bitmap_count_bits(const_bitmap a)725 bitmap_count_bits (const_bitmap a)
726 {
727 unsigned long count = 0;
728 const bitmap_element *elt;
729 unsigned ix;
730
731 for (elt = a->first; elt; elt = elt->next)
732 {
733 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
734 {
735 #if GCC_VERSION >= 3400
736 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
737 of BITMAP_WORD is not material. */
738 count += __builtin_popcountl (elt->bits[ix]);
739 #else
740 count += bitmap_popcount (elt->bits[ix]);
741 #endif
742 }
743 }
744 return count;
745 }
746
747 /* Return true if the bitmap has a single bit set. Otherwise return
748 false. */
749
750 bool
bitmap_single_bit_set_p(const_bitmap a)751 bitmap_single_bit_set_p (const_bitmap a)
752 {
753 unsigned long count = 0;
754 const bitmap_element *elt;
755 unsigned ix;
756
757 if (bitmap_empty_p (a))
758 return false;
759
760 elt = a->first;
761 /* As there are no completely empty bitmap elements, a second one
762 means we have more than one bit set. */
763 if (elt->next != NULL)
764 return false;
765
766 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
767 {
768 #if GCC_VERSION >= 3400
769 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
770 of BITMAP_WORD is not material. */
771 count += __builtin_popcountl (elt->bits[ix]);
772 #else
773 count += bitmap_popcount (elt->bits[ix]);
774 #endif
775 if (count > 1)
776 return false;
777 }
778
779 return count == 1;
780 }
781
782
783 /* Return the bit number of the first set bit in the bitmap. The
784 bitmap must be non-empty. */
785
786 unsigned
bitmap_first_set_bit(const_bitmap a)787 bitmap_first_set_bit (const_bitmap a)
788 {
789 const bitmap_element *elt = a->first;
790 unsigned bit_no;
791 BITMAP_WORD word;
792 unsigned ix;
793
794 gcc_checking_assert (elt);
795 bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
796 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
797 {
798 word = elt->bits[ix];
799 if (word)
800 goto found_bit;
801 }
802 gcc_unreachable ();
803 found_bit:
804 bit_no += ix * BITMAP_WORD_BITS;
805
806 #if GCC_VERSION >= 3004
807 gcc_assert (sizeof(long) == sizeof (word));
808 bit_no += __builtin_ctzl (word);
809 #else
810 /* Binary search for the first set bit. */
811 #if BITMAP_WORD_BITS > 64
812 #error "Fill out the table."
813 #endif
814 #if BITMAP_WORD_BITS > 32
815 if (!(word & 0xffffffff))
816 word >>= 32, bit_no += 32;
817 #endif
818 if (!(word & 0xffff))
819 word >>= 16, bit_no += 16;
820 if (!(word & 0xff))
821 word >>= 8, bit_no += 8;
822 if (!(word & 0xf))
823 word >>= 4, bit_no += 4;
824 if (!(word & 0x3))
825 word >>= 2, bit_no += 2;
826 if (!(word & 0x1))
827 word >>= 1, bit_no += 1;
828
829 gcc_checking_assert (word & 1);
830 #endif
831 return bit_no;
832 }
833
834 /* Return the bit number of the first set bit in the bitmap. The
835 bitmap must be non-empty. */
836
837 unsigned
bitmap_last_set_bit(const_bitmap a)838 bitmap_last_set_bit (const_bitmap a)
839 {
840 const bitmap_element *elt = a->current ? a->current : a->first;
841 unsigned bit_no;
842 BITMAP_WORD word;
843 int ix;
844
845 gcc_checking_assert (elt);
846 while (elt->next)
847 elt = elt->next;
848 bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
849 for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--)
850 {
851 word = elt->bits[ix];
852 if (word)
853 goto found_bit;
854 }
855 gcc_unreachable ();
856 found_bit:
857 bit_no += ix * BITMAP_WORD_BITS;
858 #if GCC_VERSION >= 3004
859 gcc_assert (sizeof(long) == sizeof (word));
860 bit_no += BITMAP_WORD_BITS - __builtin_clzl (word) - 1;
861 #else
862 /* Hopefully this is a twos-complement host... */
863 BITMAP_WORD x = word;
864 x |= (x >> 1);
865 x |= (x >> 2);
866 x |= (x >> 4);
867 x |= (x >> 8);
868 x |= (x >> 16);
869 #if BITMAP_WORD_BITS > 32
870 x |= (x >> 32);
871 #endif
872 bit_no += bitmap_popcount (x) - 1;
873 #endif
874
875 return bit_no;
876 }
877
878
879 /* DST = A & B. */
880
881 void
bitmap_and(bitmap dst,const_bitmap a,const_bitmap b)882 bitmap_and (bitmap dst, const_bitmap a, const_bitmap b)
883 {
884 bitmap_element *dst_elt = dst->first;
885 const bitmap_element *a_elt = a->first;
886 const bitmap_element *b_elt = b->first;
887 bitmap_element *dst_prev = NULL;
888
889 gcc_assert (dst != a && dst != b);
890
891 if (a == b)
892 {
893 bitmap_copy (dst, a);
894 return;
895 }
896
897 while (a_elt && b_elt)
898 {
899 if (a_elt->indx < b_elt->indx)
900 a_elt = a_elt->next;
901 else if (b_elt->indx < a_elt->indx)
902 b_elt = b_elt->next;
903 else
904 {
905 /* Matching elts, generate A & B. */
906 unsigned ix;
907 BITMAP_WORD ior = 0;
908
909 if (!dst_elt)
910 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
911 else
912 dst_elt->indx = a_elt->indx;
913 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
914 {
915 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
916
917 dst_elt->bits[ix] = r;
918 ior |= r;
919 }
920 if (ior)
921 {
922 dst_prev = dst_elt;
923 dst_elt = dst_elt->next;
924 }
925 a_elt = a_elt->next;
926 b_elt = b_elt->next;
927 }
928 }
929 /* Ensure that dst->current is valid. */
930 dst->current = dst->first;
931 bitmap_elt_clear_from (dst, dst_elt);
932 gcc_checking_assert (!dst->current == !dst->first);
933 if (dst->current)
934 dst->indx = dst->current->indx;
935 }
936
937 /* A &= B. Return true if A changed. */
938
939 bool
bitmap_and_into(bitmap a,const_bitmap b)940 bitmap_and_into (bitmap a, const_bitmap b)
941 {
942 bitmap_element *a_elt = a->first;
943 const bitmap_element *b_elt = b->first;
944 bitmap_element *next;
945 bool changed = false;
946
947 if (a == b)
948 return false;
949
950 while (a_elt && b_elt)
951 {
952 if (a_elt->indx < b_elt->indx)
953 {
954 next = a_elt->next;
955 bitmap_element_free (a, a_elt);
956 a_elt = next;
957 changed = true;
958 }
959 else if (b_elt->indx < a_elt->indx)
960 b_elt = b_elt->next;
961 else
962 {
963 /* Matching elts, generate A &= B. */
964 unsigned ix;
965 BITMAP_WORD ior = 0;
966
967 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
968 {
969 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
970 if (a_elt->bits[ix] != r)
971 changed = true;
972 a_elt->bits[ix] = r;
973 ior |= r;
974 }
975 next = a_elt->next;
976 if (!ior)
977 bitmap_element_free (a, a_elt);
978 a_elt = next;
979 b_elt = b_elt->next;
980 }
981 }
982
983 if (a_elt)
984 {
985 changed = true;
986 bitmap_elt_clear_from (a, a_elt);
987 }
988
989 gcc_checking_assert (!a->current == !a->first
990 && (!a->current || a->indx == a->current->indx));
991
992 return changed;
993 }
994
995
996 /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
997 if non-NULL. CHANGED is true if the destination bitmap had already been
998 changed; the new value of CHANGED is returned. */
999
1000 static inline bool
bitmap_elt_copy(bitmap dst,bitmap_element * dst_elt,bitmap_element * dst_prev,const bitmap_element * src_elt,bool changed)1001 bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
1002 const bitmap_element *src_elt, bool changed)
1003 {
1004 if (!changed && dst_elt && dst_elt->indx == src_elt->indx)
1005 {
1006 unsigned ix;
1007
1008 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1009 if (src_elt->bits[ix] != dst_elt->bits[ix])
1010 {
1011 dst_elt->bits[ix] = src_elt->bits[ix];
1012 changed = true;
1013 }
1014 }
1015 else
1016 {
1017 changed = true;
1018 if (!dst_elt)
1019 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src_elt->indx);
1020 else
1021 dst_elt->indx = src_elt->indx;
1022 memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits));
1023 }
1024 return changed;
1025 }
1026
1027
1028
1029 /* DST = A & ~B */
1030
1031 bool
bitmap_and_compl(bitmap dst,const_bitmap a,const_bitmap b)1032 bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b)
1033 {
1034 bitmap_element *dst_elt = dst->first;
1035 const bitmap_element *a_elt = a->first;
1036 const bitmap_element *b_elt = b->first;
1037 bitmap_element *dst_prev = NULL;
1038 bitmap_element **dst_prev_pnext = &dst->first;
1039 bool changed = false;
1040
1041 gcc_assert (dst != a && dst != b);
1042
1043 if (a == b)
1044 {
1045 changed = !bitmap_empty_p (dst);
1046 bitmap_clear (dst);
1047 return changed;
1048 }
1049
1050 while (a_elt)
1051 {
1052 while (b_elt && b_elt->indx < a_elt->indx)
1053 b_elt = b_elt->next;
1054
1055 if (!b_elt || b_elt->indx > a_elt->indx)
1056 {
1057 changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed);
1058 dst_prev = *dst_prev_pnext;
1059 dst_prev_pnext = &dst_prev->next;
1060 dst_elt = *dst_prev_pnext;
1061 a_elt = a_elt->next;
1062 }
1063
1064 else
1065 {
1066 /* Matching elts, generate A & ~B. */
1067 unsigned ix;
1068 BITMAP_WORD ior = 0;
1069
1070 if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1071 {
1072 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1073 {
1074 BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1075
1076 if (dst_elt->bits[ix] != r)
1077 {
1078 changed = true;
1079 dst_elt->bits[ix] = r;
1080 }
1081 ior |= r;
1082 }
1083 }
1084 else
1085 {
1086 bool new_element;
1087 if (!dst_elt || dst_elt->indx > a_elt->indx)
1088 {
1089 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1090 new_element = true;
1091 }
1092 else
1093 {
1094 dst_elt->indx = a_elt->indx;
1095 new_element = false;
1096 }
1097
1098 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1099 {
1100 BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1101
1102 dst_elt->bits[ix] = r;
1103 ior |= r;
1104 }
1105
1106 if (ior)
1107 changed = true;
1108 else
1109 {
1110 changed |= !new_element;
1111 bitmap_element_free (dst, dst_elt);
1112 dst_elt = *dst_prev_pnext;
1113 }
1114 }
1115
1116 if (ior)
1117 {
1118 dst_prev = *dst_prev_pnext;
1119 dst_prev_pnext = &dst_prev->next;
1120 dst_elt = *dst_prev_pnext;
1121 }
1122 a_elt = a_elt->next;
1123 b_elt = b_elt->next;
1124 }
1125 }
1126
1127 /* Ensure that dst->current is valid. */
1128 dst->current = dst->first;
1129
1130 if (dst_elt)
1131 {
1132 changed = true;
1133 bitmap_elt_clear_from (dst, dst_elt);
1134 }
1135 gcc_checking_assert (!dst->current == !dst->first);
1136 if (dst->current)
1137 dst->indx = dst->current->indx;
1138
1139 return changed;
1140 }
1141
1142 /* A &= ~B. Returns true if A changes */
1143
1144 bool
bitmap_and_compl_into(bitmap a,const_bitmap b)1145 bitmap_and_compl_into (bitmap a, const_bitmap b)
1146 {
1147 bitmap_element *a_elt = a->first;
1148 const bitmap_element *b_elt = b->first;
1149 bitmap_element *next;
1150 BITMAP_WORD changed = 0;
1151
1152 if (a == b)
1153 {
1154 if (bitmap_empty_p (a))
1155 return false;
1156 else
1157 {
1158 bitmap_clear (a);
1159 return true;
1160 }
1161 }
1162
1163 while (a_elt && b_elt)
1164 {
1165 if (a_elt->indx < b_elt->indx)
1166 a_elt = a_elt->next;
1167 else if (b_elt->indx < a_elt->indx)
1168 b_elt = b_elt->next;
1169 else
1170 {
1171 /* Matching elts, generate A &= ~B. */
1172 unsigned ix;
1173 BITMAP_WORD ior = 0;
1174
1175 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1176 {
1177 BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1178 BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
1179
1180 a_elt->bits[ix] = r;
1181 changed |= cleared;
1182 ior |= r;
1183 }
1184 next = a_elt->next;
1185 if (!ior)
1186 bitmap_element_free (a, a_elt);
1187 a_elt = next;
1188 b_elt = b_elt->next;
1189 }
1190 }
1191 gcc_checking_assert (!a->current == !a->first
1192 && (!a->current || a->indx == a->current->indx));
1193 return changed != 0;
1194 }
1195
1196 /* Set COUNT bits from START in HEAD. */
1197 void
bitmap_set_range(bitmap head,unsigned int start,unsigned int count)1198 bitmap_set_range (bitmap head, unsigned int start, unsigned int count)
1199 {
1200 unsigned int first_index, end_bit_plus1, last_index;
1201 bitmap_element *elt, *elt_prev;
1202 unsigned int i;
1203
1204 if (!count)
1205 return;
1206
1207 first_index = start / BITMAP_ELEMENT_ALL_BITS;
1208 end_bit_plus1 = start + count;
1209 last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1210 elt = bitmap_find_bit (head, start);
1211
1212 /* If bitmap_find_bit returns zero, the current is the closest block
1213 to the result. Otherwise, just use bitmap_element_allocate to
1214 ensure ELT is set; in the loop below, ELT == NULL means "insert
1215 at the end of the bitmap". */
1216 if (!elt)
1217 {
1218 elt = bitmap_element_allocate (head);
1219 elt->indx = first_index;
1220 bitmap_element_link (head, elt);
1221 }
1222
1223 gcc_checking_assert (elt->indx == first_index);
1224 elt_prev = elt->prev;
1225 for (i = first_index; i <= last_index; i++)
1226 {
1227 unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS;
1228 unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1229
1230 unsigned int first_word_to_mod;
1231 BITMAP_WORD first_mask;
1232 unsigned int last_word_to_mod;
1233 BITMAP_WORD last_mask;
1234 unsigned int ix;
1235
1236 if (!elt || elt->indx != i)
1237 elt = bitmap_elt_insert_after (head, elt_prev, i);
1238
1239 if (elt_start_bit <= start)
1240 {
1241 /* The first bit to turn on is somewhere inside this
1242 elt. */
1243 first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1244
1245 /* This mask should have 1s in all bits >= start position. */
1246 first_mask =
1247 (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1248 first_mask = ~first_mask;
1249 }
1250 else
1251 {
1252 /* The first bit to turn on is below this start of this elt. */
1253 first_word_to_mod = 0;
1254 first_mask = ~(BITMAP_WORD) 0;
1255 }
1256
1257 if (elt_end_bit_plus1 <= end_bit_plus1)
1258 {
1259 /* The last bit to turn on is beyond this elt. */
1260 last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
1261 last_mask = ~(BITMAP_WORD) 0;
1262 }
1263 else
1264 {
1265 /* The last bit to turn on is inside to this elt. */
1266 last_word_to_mod =
1267 (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1268
1269 /* The last mask should have 1s below the end bit. */
1270 last_mask =
1271 (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1;
1272 }
1273
1274 if (first_word_to_mod == last_word_to_mod)
1275 {
1276 BITMAP_WORD mask = first_mask & last_mask;
1277 elt->bits[first_word_to_mod] |= mask;
1278 }
1279 else
1280 {
1281 elt->bits[first_word_to_mod] |= first_mask;
1282 if (BITMAP_ELEMENT_WORDS > 2)
1283 for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++)
1284 elt->bits[ix] = ~(BITMAP_WORD) 0;
1285 elt->bits[last_word_to_mod] |= last_mask;
1286 }
1287
1288 elt_prev = elt;
1289 elt = elt->next;
1290 }
1291
1292 head->current = elt ? elt : elt_prev;
1293 head->indx = head->current->indx;
1294 }
1295
1296 /* Clear COUNT bits from START in HEAD. */
1297 void
bitmap_clear_range(bitmap head,unsigned int start,unsigned int count)1298 bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
1299 {
1300 unsigned int first_index, end_bit_plus1, last_index;
1301 bitmap_element *elt;
1302
1303 if (!count)
1304 return;
1305
1306 first_index = start / BITMAP_ELEMENT_ALL_BITS;
1307 end_bit_plus1 = start + count;
1308 last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1309 elt = bitmap_find_bit (head, start);
1310
1311 /* If bitmap_find_bit returns zero, the current is the closest block
1312 to the result. If the current is less than first index, find the
1313 next one. Otherwise, just set elt to be current. */
1314 if (!elt)
1315 {
1316 if (head->current)
1317 {
1318 if (head->indx < first_index)
1319 {
1320 elt = head->current->next;
1321 if (!elt)
1322 return;
1323 }
1324 else
1325 elt = head->current;
1326 }
1327 else
1328 return;
1329 }
1330
1331 while (elt && (elt->indx <= last_index))
1332 {
1333 bitmap_element * next_elt = elt->next;
1334 unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
1335 unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1336
1337
1338 if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
1339 /* Get rid of the entire elt and go to the next one. */
1340 bitmap_element_free (head, elt);
1341 else
1342 {
1343 /* Going to have to knock out some bits in this elt. */
1344 unsigned int first_word_to_mod;
1345 BITMAP_WORD first_mask;
1346 unsigned int last_word_to_mod;
1347 BITMAP_WORD last_mask;
1348 unsigned int i;
1349 bool clear = true;
1350
1351 if (elt_start_bit <= start)
1352 {
1353 /* The first bit to turn off is somewhere inside this
1354 elt. */
1355 first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1356
1357 /* This mask should have 1s in all bits >= start position. */
1358 first_mask =
1359 (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1360 first_mask = ~first_mask;
1361 }
1362 else
1363 {
1364 /* The first bit to turn off is below this start of this elt. */
1365 first_word_to_mod = 0;
1366 first_mask = 0;
1367 first_mask = ~first_mask;
1368 }
1369
1370 if (elt_end_bit_plus1 <= end_bit_plus1)
1371 {
1372 /* The last bit to turn off is beyond this elt. */
1373 last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
1374 last_mask = 0;
1375 last_mask = ~last_mask;
1376 }
1377 else
1378 {
1379 /* The last bit to turn off is inside to this elt. */
1380 last_word_to_mod =
1381 (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1382
1383 /* The last mask should have 1s below the end bit. */
1384 last_mask =
1385 (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
1386 }
1387
1388
1389 if (first_word_to_mod == last_word_to_mod)
1390 {
1391 BITMAP_WORD mask = first_mask & last_mask;
1392 elt->bits[first_word_to_mod] &= ~mask;
1393 }
1394 else
1395 {
1396 elt->bits[first_word_to_mod] &= ~first_mask;
1397 if (BITMAP_ELEMENT_WORDS > 2)
1398 for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
1399 elt->bits[i] = 0;
1400 elt->bits[last_word_to_mod] &= ~last_mask;
1401 }
1402 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1403 if (elt->bits[i])
1404 {
1405 clear = false;
1406 break;
1407 }
1408 /* Check to see if there are any bits left. */
1409 if (clear)
1410 bitmap_element_free (head, elt);
1411 }
1412 elt = next_elt;
1413 }
1414
1415 if (elt)
1416 {
1417 head->current = elt;
1418 head->indx = head->current->indx;
1419 }
1420 }
1421
1422 /* A = ~A & B. */
1423
1424 void
bitmap_compl_and_into(bitmap a,const_bitmap b)1425 bitmap_compl_and_into (bitmap a, const_bitmap b)
1426 {
1427 bitmap_element *a_elt = a->first;
1428 const bitmap_element *b_elt = b->first;
1429 bitmap_element *a_prev = NULL;
1430 bitmap_element *next;
1431
1432 gcc_assert (a != b);
1433
1434 if (bitmap_empty_p (a))
1435 {
1436 bitmap_copy (a, b);
1437 return;
1438 }
1439 if (bitmap_empty_p (b))
1440 {
1441 bitmap_clear (a);
1442 return;
1443 }
1444
1445 while (a_elt || b_elt)
1446 {
1447 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1448 {
1449 /* A is before B. Remove A */
1450 next = a_elt->next;
1451 a_prev = a_elt->prev;
1452 bitmap_element_free (a, a_elt);
1453 a_elt = next;
1454 }
1455 else if (!a_elt || b_elt->indx < a_elt->indx)
1456 {
1457 /* B is before A. Copy B. */
1458 next = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1459 memcpy (next->bits, b_elt->bits, sizeof (next->bits));
1460 a_prev = next;
1461 b_elt = b_elt->next;
1462 }
1463 else
1464 {
1465 /* Matching elts, generate A = ~A & B. */
1466 unsigned ix;
1467 BITMAP_WORD ior = 0;
1468
1469 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1470 {
1471 BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1472 BITMAP_WORD r = b_elt->bits[ix] ^ cleared;
1473
1474 a_elt->bits[ix] = r;
1475 ior |= r;
1476 }
1477 next = a_elt->next;
1478 if (!ior)
1479 bitmap_element_free (a, a_elt);
1480 else
1481 a_prev = a_elt;
1482 a_elt = next;
1483 b_elt = b_elt->next;
1484 }
1485 }
1486 gcc_checking_assert (!a->current == !a->first
1487 && (!a->current || a->indx == a->current->indx));
1488 return;
1489 }
1490
1491
1492 /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
1493 overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap
1494 had already been changed; the new value of CHANGED is returned. */
1495
1496 static inline bool
bitmap_elt_ior(bitmap dst,bitmap_element * dst_elt,bitmap_element * dst_prev,const bitmap_element * a_elt,const bitmap_element * b_elt,bool changed)1497 bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
1498 const bitmap_element *a_elt, const bitmap_element *b_elt,
1499 bool changed)
1500 {
1501 gcc_assert (a_elt || b_elt);
1502
1503 if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1504 {
1505 /* Matching elts, generate A | B. */
1506 unsigned ix;
1507
1508 if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1509 {
1510 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1511 {
1512 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1513 if (r != dst_elt->bits[ix])
1514 {
1515 dst_elt->bits[ix] = r;
1516 changed = true;
1517 }
1518 }
1519 }
1520 else
1521 {
1522 changed = true;
1523 if (!dst_elt)
1524 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1525 else
1526 dst_elt->indx = a_elt->indx;
1527 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1528 {
1529 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1530 dst_elt->bits[ix] = r;
1531 }
1532 }
1533 }
1534 else
1535 {
1536 /* Copy a single element. */
1537 const bitmap_element *src;
1538
1539 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1540 src = a_elt;
1541 else
1542 src = b_elt;
1543
1544 gcc_checking_assert (src);
1545 changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed);
1546 }
1547 return changed;
1548 }
1549
1550
1551 /* DST = A | B. Return true if DST changes. */
1552
1553 bool
bitmap_ior(bitmap dst,const_bitmap a,const_bitmap b)1554 bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b)
1555 {
1556 bitmap_element *dst_elt = dst->first;
1557 const bitmap_element *a_elt = a->first;
1558 const bitmap_element *b_elt = b->first;
1559 bitmap_element *dst_prev = NULL;
1560 bitmap_element **dst_prev_pnext = &dst->first;
1561 bool changed = false;
1562
1563 gcc_assert (dst != a && dst != b);
1564
1565 while (a_elt || b_elt)
1566 {
1567 changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed);
1568
1569 if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1570 {
1571 a_elt = a_elt->next;
1572 b_elt = b_elt->next;
1573 }
1574 else
1575 {
1576 if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
1577 a_elt = a_elt->next;
1578 else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
1579 b_elt = b_elt->next;
1580 }
1581
1582 dst_prev = *dst_prev_pnext;
1583 dst_prev_pnext = &dst_prev->next;
1584 dst_elt = *dst_prev_pnext;
1585 }
1586
1587 if (dst_elt)
1588 {
1589 changed = true;
1590 bitmap_elt_clear_from (dst, dst_elt);
1591 }
1592 gcc_checking_assert (!dst->current == !dst->first);
1593 if (dst->current)
1594 dst->indx = dst->current->indx;
1595 return changed;
1596 }
1597
1598 /* A |= B. Return true if A changes. */
1599
1600 bool
bitmap_ior_into(bitmap a,const_bitmap b)1601 bitmap_ior_into (bitmap a, const_bitmap b)
1602 {
1603 bitmap_element *a_elt = a->first;
1604 const bitmap_element *b_elt = b->first;
1605 bitmap_element *a_prev = NULL;
1606 bitmap_element **a_prev_pnext = &a->first;
1607 bool changed = false;
1608
1609 if (a == b)
1610 return false;
1611
1612 while (b_elt)
1613 {
1614 /* If A lags behind B, just advance it. */
1615 if (!a_elt || a_elt->indx == b_elt->indx)
1616 {
1617 changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
1618 b_elt = b_elt->next;
1619 }
1620 else if (a_elt->indx > b_elt->indx)
1621 {
1622 changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed);
1623 b_elt = b_elt->next;
1624 }
1625
1626 a_prev = *a_prev_pnext;
1627 a_prev_pnext = &a_prev->next;
1628 a_elt = *a_prev_pnext;
1629 }
1630
1631 gcc_checking_assert (!a->current == !a->first);
1632 if (a->current)
1633 a->indx = a->current->indx;
1634 return changed;
1635 }
1636
1637 /* DST = A ^ B */
1638
1639 void
bitmap_xor(bitmap dst,const_bitmap a,const_bitmap b)1640 bitmap_xor (bitmap dst, const_bitmap a, const_bitmap b)
1641 {
1642 bitmap_element *dst_elt = dst->first;
1643 const bitmap_element *a_elt = a->first;
1644 const bitmap_element *b_elt = b->first;
1645 bitmap_element *dst_prev = NULL;
1646
1647 gcc_assert (dst != a && dst != b);
1648 if (a == b)
1649 {
1650 bitmap_clear (dst);
1651 return;
1652 }
1653
1654 while (a_elt || b_elt)
1655 {
1656 if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1657 {
1658 /* Matching elts, generate A ^ B. */
1659 unsigned ix;
1660 BITMAP_WORD ior = 0;
1661
1662 if (!dst_elt)
1663 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1664 else
1665 dst_elt->indx = a_elt->indx;
1666 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1667 {
1668 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1669
1670 ior |= r;
1671 dst_elt->bits[ix] = r;
1672 }
1673 a_elt = a_elt->next;
1674 b_elt = b_elt->next;
1675 if (ior)
1676 {
1677 dst_prev = dst_elt;
1678 dst_elt = dst_elt->next;
1679 }
1680 }
1681 else
1682 {
1683 /* Copy a single element. */
1684 const bitmap_element *src;
1685
1686 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1687 {
1688 src = a_elt;
1689 a_elt = a_elt->next;
1690 }
1691 else
1692 {
1693 src = b_elt;
1694 b_elt = b_elt->next;
1695 }
1696
1697 if (!dst_elt)
1698 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
1699 else
1700 dst_elt->indx = src->indx;
1701 memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
1702 dst_prev = dst_elt;
1703 dst_elt = dst_elt->next;
1704 }
1705 }
1706 /* Ensure that dst->current is valid. */
1707 dst->current = dst->first;
1708 bitmap_elt_clear_from (dst, dst_elt);
1709 gcc_checking_assert (!dst->current == !dst->first);
1710 if (dst->current)
1711 dst->indx = dst->current->indx;
1712 }
1713
1714 /* A ^= B */
1715
1716 void
bitmap_xor_into(bitmap a,const_bitmap b)1717 bitmap_xor_into (bitmap a, const_bitmap b)
1718 {
1719 bitmap_element *a_elt = a->first;
1720 const bitmap_element *b_elt = b->first;
1721 bitmap_element *a_prev = NULL;
1722
1723 if (a == b)
1724 {
1725 bitmap_clear (a);
1726 return;
1727 }
1728
1729 while (b_elt)
1730 {
1731 if (!a_elt || b_elt->indx < a_elt->indx)
1732 {
1733 /* Copy b_elt. */
1734 bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1735 memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
1736 a_prev = dst;
1737 b_elt = b_elt->next;
1738 }
1739 else if (a_elt->indx < b_elt->indx)
1740 {
1741 a_prev = a_elt;
1742 a_elt = a_elt->next;
1743 }
1744 else
1745 {
1746 /* Matching elts, generate A ^= B. */
1747 unsigned ix;
1748 BITMAP_WORD ior = 0;
1749 bitmap_element *next = a_elt->next;
1750
1751 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1752 {
1753 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1754
1755 ior |= r;
1756 a_elt->bits[ix] = r;
1757 }
1758 b_elt = b_elt->next;
1759 if (ior)
1760 a_prev = a_elt;
1761 else
1762 bitmap_element_free (a, a_elt);
1763 a_elt = next;
1764 }
1765 }
1766 gcc_checking_assert (!a->current == !a->first);
1767 if (a->current)
1768 a->indx = a->current->indx;
1769 }
1770
1771 /* Return true if two bitmaps are identical.
1772 We do not bother with a check for pointer equality, as that never
1773 occurs in practice. */
1774
1775 bool
bitmap_equal_p(const_bitmap a,const_bitmap b)1776 bitmap_equal_p (const_bitmap a, const_bitmap b)
1777 {
1778 const bitmap_element *a_elt;
1779 const bitmap_element *b_elt;
1780 unsigned ix;
1781
1782 for (a_elt = a->first, b_elt = b->first;
1783 a_elt && b_elt;
1784 a_elt = a_elt->next, b_elt = b_elt->next)
1785 {
1786 if (a_elt->indx != b_elt->indx)
1787 return false;
1788 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1789 if (a_elt->bits[ix] != b_elt->bits[ix])
1790 return false;
1791 }
1792 return !a_elt && !b_elt;
1793 }
1794
1795 /* Return true if A AND B is not empty. */
1796
1797 bool
bitmap_intersect_p(const_bitmap a,const_bitmap b)1798 bitmap_intersect_p (const_bitmap a, const_bitmap b)
1799 {
1800 const bitmap_element *a_elt;
1801 const bitmap_element *b_elt;
1802 unsigned ix;
1803
1804 for (a_elt = a->first, b_elt = b->first;
1805 a_elt && b_elt;)
1806 {
1807 if (a_elt->indx < b_elt->indx)
1808 a_elt = a_elt->next;
1809 else if (b_elt->indx < a_elt->indx)
1810 b_elt = b_elt->next;
1811 else
1812 {
1813 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1814 if (a_elt->bits[ix] & b_elt->bits[ix])
1815 return true;
1816 a_elt = a_elt->next;
1817 b_elt = b_elt->next;
1818 }
1819 }
1820 return false;
1821 }
1822
1823 /* Return true if A AND NOT B is not empty. */
1824
1825 bool
bitmap_intersect_compl_p(const_bitmap a,const_bitmap b)1826 bitmap_intersect_compl_p (const_bitmap a, const_bitmap b)
1827 {
1828 const bitmap_element *a_elt;
1829 const bitmap_element *b_elt;
1830 unsigned ix;
1831 for (a_elt = a->first, b_elt = b->first;
1832 a_elt && b_elt;)
1833 {
1834 if (a_elt->indx < b_elt->indx)
1835 return true;
1836 else if (b_elt->indx < a_elt->indx)
1837 b_elt = b_elt->next;
1838 else
1839 {
1840 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1841 if (a_elt->bits[ix] & ~b_elt->bits[ix])
1842 return true;
1843 a_elt = a_elt->next;
1844 b_elt = b_elt->next;
1845 }
1846 }
1847 return a_elt != NULL;
1848 }
1849
1850
1851 /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */
1852
1853 bool
bitmap_ior_and_compl(bitmap dst,const_bitmap a,const_bitmap b,const_bitmap kill)1854 bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill)
1855 {
1856 bool changed = false;
1857
1858 bitmap_element *dst_elt = dst->first;
1859 const bitmap_element *a_elt = a->first;
1860 const bitmap_element *b_elt = b->first;
1861 const bitmap_element *kill_elt = kill->first;
1862 bitmap_element *dst_prev = NULL;
1863 bitmap_element **dst_prev_pnext = &dst->first;
1864
1865 gcc_assert (dst != a && dst != b && dst != kill);
1866
1867 /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
1868 if (b == kill || bitmap_empty_p (b))
1869 {
1870 changed = !bitmap_equal_p (dst, a);
1871 if (changed)
1872 bitmap_copy (dst, a);
1873 return changed;
1874 }
1875 if (bitmap_empty_p (kill))
1876 return bitmap_ior (dst, a, b);
1877 if (bitmap_empty_p (a))
1878 return bitmap_and_compl (dst, b, kill);
1879
1880 while (a_elt || b_elt)
1881 {
1882 bool new_element = false;
1883
1884 if (b_elt)
1885 while (kill_elt && kill_elt->indx < b_elt->indx)
1886 kill_elt = kill_elt->next;
1887
1888 if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
1889 && (!a_elt || a_elt->indx >= b_elt->indx))
1890 {
1891 bitmap_element tmp_elt;
1892 unsigned ix;
1893
1894 BITMAP_WORD ior = 0;
1895 tmp_elt.indx = b_elt->indx;
1896 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1897 {
1898 BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix];
1899 ior |= r;
1900 tmp_elt.bits[ix] = r;
1901 }
1902
1903 if (ior)
1904 {
1905 changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
1906 a_elt, &tmp_elt, changed);
1907 new_element = true;
1908 if (a_elt && a_elt->indx == b_elt->indx)
1909 a_elt = a_elt->next;
1910 }
1911
1912 b_elt = b_elt->next;
1913 kill_elt = kill_elt->next;
1914 }
1915 else
1916 {
1917 changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
1918 a_elt, b_elt, changed);
1919 new_element = true;
1920
1921 if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1922 {
1923 a_elt = a_elt->next;
1924 b_elt = b_elt->next;
1925 }
1926 else
1927 {
1928 if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
1929 a_elt = a_elt->next;
1930 else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
1931 b_elt = b_elt->next;
1932 }
1933 }
1934
1935 if (new_element)
1936 {
1937 dst_prev = *dst_prev_pnext;
1938 dst_prev_pnext = &dst_prev->next;
1939 dst_elt = *dst_prev_pnext;
1940 }
1941 }
1942
1943 if (dst_elt)
1944 {
1945 changed = true;
1946 bitmap_elt_clear_from (dst, dst_elt);
1947 }
1948 gcc_checking_assert (!dst->current == !dst->first);
1949 if (dst->current)
1950 dst->indx = dst->current->indx;
1951
1952 return changed;
1953 }
1954
1955 /* A |= (FROM1 & ~FROM2). Return true if A changes. */
1956
1957 bool
bitmap_ior_and_compl_into(bitmap a,const_bitmap from1,const_bitmap from2)1958 bitmap_ior_and_compl_into (bitmap a, const_bitmap from1, const_bitmap from2)
1959 {
1960 bitmap_head tmp;
1961 bool changed;
1962
1963 bitmap_initialize (&tmp, &bitmap_default_obstack);
1964 bitmap_and_compl (&tmp, from1, from2);
1965 changed = bitmap_ior_into (a, &tmp);
1966 bitmap_clear (&tmp);
1967
1968 return changed;
1969 }
1970
1971 /* A |= (B & C). Return true if A changes. */
1972
1973 bool
bitmap_ior_and_into(bitmap a,const_bitmap b,const_bitmap c)1974 bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c)
1975 {
1976 bitmap_element *a_elt = a->first;
1977 const bitmap_element *b_elt = b->first;
1978 const bitmap_element *c_elt = c->first;
1979 bitmap_element and_elt;
1980 bitmap_element *a_prev = NULL;
1981 bitmap_element **a_prev_pnext = &a->first;
1982 bool changed = false;
1983 unsigned ix;
1984
1985 if (b == c)
1986 return bitmap_ior_into (a, b);
1987 if (bitmap_empty_p (b) || bitmap_empty_p (c))
1988 return false;
1989
1990 and_elt.indx = -1;
1991 while (b_elt && c_elt)
1992 {
1993 BITMAP_WORD overall;
1994
1995 /* Find a common item of B and C. */
1996 while (b_elt->indx != c_elt->indx)
1997 {
1998 if (b_elt->indx < c_elt->indx)
1999 {
2000 b_elt = b_elt->next;
2001 if (!b_elt)
2002 goto done;
2003 }
2004 else
2005 {
2006 c_elt = c_elt->next;
2007 if (!c_elt)
2008 goto done;
2009 }
2010 }
2011
2012 overall = 0;
2013 and_elt.indx = b_elt->indx;
2014 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2015 {
2016 and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix];
2017 overall |= and_elt.bits[ix];
2018 }
2019
2020 b_elt = b_elt->next;
2021 c_elt = c_elt->next;
2022 if (!overall)
2023 continue;
2024
2025 /* Now find a place to insert AND_ELT. */
2026 do
2027 {
2028 ix = a_elt ? a_elt->indx : and_elt.indx;
2029 if (ix == and_elt.indx)
2030 changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed);
2031 else if (ix > and_elt.indx)
2032 changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed);
2033
2034 a_prev = *a_prev_pnext;
2035 a_prev_pnext = &a_prev->next;
2036 a_elt = *a_prev_pnext;
2037
2038 /* If A lagged behind B/C, we advanced it so loop once more. */
2039 }
2040 while (ix < and_elt.indx);
2041 }
2042
2043 done:
2044 gcc_checking_assert (!a->current == !a->first);
2045 if (a->current)
2046 a->indx = a->current->indx;
2047 return changed;
2048 }
2049
2050 /* Compute hash of bitmap (for purposes of hashing). */
2051 hashval_t
bitmap_hash(const_bitmap head)2052 bitmap_hash (const_bitmap head)
2053 {
2054 const bitmap_element *ptr;
2055 BITMAP_WORD hash = 0;
2056 int ix;
2057
2058 for (ptr = head->first; ptr; ptr = ptr->next)
2059 {
2060 hash ^= ptr->indx;
2061 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
2062 hash ^= ptr->bits[ix];
2063 }
2064 return (hashval_t)hash;
2065 }
2066
2067
2068 /* Debugging function to print out the contents of a bitmap. */
2069
2070 DEBUG_FUNCTION void
debug_bitmap_file(FILE * file,const_bitmap head)2071 debug_bitmap_file (FILE *file, const_bitmap head)
2072 {
2073 const bitmap_element *ptr;
2074
2075 fprintf (file, "\nfirst = " HOST_PTR_PRINTF
2076 " current = " HOST_PTR_PRINTF " indx = %u\n",
2077 (void *) head->first, (void *) head->current, head->indx);
2078
2079 for (ptr = head->first; ptr; ptr = ptr->next)
2080 {
2081 unsigned int i, j, col = 26;
2082
2083 fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
2084 " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
2085 (const void*) ptr, (const void*) ptr->next,
2086 (const void*) ptr->prev, ptr->indx);
2087
2088 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
2089 for (j = 0; j < BITMAP_WORD_BITS; j++)
2090 if ((ptr->bits[i] >> j) & 1)
2091 {
2092 if (col > 70)
2093 {
2094 fprintf (file, "\n\t\t\t");
2095 col = 24;
2096 }
2097
2098 fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
2099 + i * BITMAP_WORD_BITS + j));
2100 col += 4;
2101 }
2102
2103 fprintf (file, " }\n");
2104 }
2105 }
2106
2107 /* Function to be called from the debugger to print the contents
2108 of a bitmap. */
2109
2110 DEBUG_FUNCTION void
debug_bitmap(const_bitmap head)2111 debug_bitmap (const_bitmap head)
2112 {
2113 debug_bitmap_file (stdout, head);
2114 }
2115
2116 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
2117 it does not print anything but the bits. */
2118
2119 DEBUG_FUNCTION void
bitmap_print(FILE * file,const_bitmap head,const char * prefix,const char * suffix)2120 bitmap_print (FILE *file, const_bitmap head, const char *prefix, const char *suffix)
2121 {
2122 const char *comma = "";
2123 unsigned i;
2124 bitmap_iterator bi;
2125
2126 fputs (prefix, file);
2127 EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
2128 {
2129 fprintf (file, "%s%d", comma, i);
2130 comma = ", ";
2131 }
2132 fputs (suffix, file);
2133 }
2134
2135
2136 /* Used to accumulate statistics about bitmap sizes. */
2137 struct output_info
2138 {
2139 unsigned HOST_WIDEST_INT size;
2140 unsigned HOST_WIDEST_INT count;
2141 };
2142
2143 /* Called via htab_traverse. Output bitmap descriptor pointed out by SLOT
2144 and update statistics. */
2145 static int
print_statistics(void ** slot,void * b)2146 print_statistics (void **slot, void *b)
2147 {
2148 bitmap_descriptor d = (bitmap_descriptor) *slot;
2149 struct output_info *i = (struct output_info *) b;
2150 char s[4096];
2151
2152 if (d->allocated)
2153 {
2154 const char *s1 = d->file;
2155 const char *s2;
2156 while ((s2 = strstr (s1, "gcc/")))
2157 s1 = s2 + 4;
2158 sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
2159 s[41] = 0;
2160 fprintf (stderr,
2161 "%-41s %9u"
2162 " %15" HOST_WIDEST_INT_PRINT "d %15" HOST_WIDEST_INT_PRINT "d"
2163 " %15" HOST_WIDEST_INT_PRINT "d"
2164 " %10" HOST_WIDEST_INT_PRINT "d %10" HOST_WIDEST_INT_PRINT "d\n",
2165 s, d->created,
2166 d->allocated, d->peak, d->current,
2167 d->nsearches, d->search_iter);
2168 i->size += d->allocated;
2169 i->count += d->created;
2170 }
2171 return 1;
2172 }
2173
2174 /* Output per-bitmap memory usage statistics. */
2175 void
dump_bitmap_statistics(void)2176 dump_bitmap_statistics (void)
2177 {
2178 struct output_info info;
2179
2180 if (! GATHER_STATISTICS)
2181 return;
2182
2183 if (!bitmap_desc_hash)
2184 return;
2185
2186 fprintf (stderr,
2187 "\n%-41s %9s %15s %15s %15s %10s %10s\n",
2188 "Bitmap", "Overall",
2189 "Allocated", "Peak", "Leak",
2190 "searched", "search_itr");
2191 fprintf (stderr, "---------------------------------------------------------------------------------\n");
2192 info.count = 0;
2193 info.size = 0;
2194 htab_traverse (bitmap_desc_hash, print_statistics, &info);
2195 fprintf (stderr, "---------------------------------------------------------------------------------\n");
2196 fprintf (stderr,
2197 "%-41s %9" HOST_WIDEST_INT_PRINT "d %15" HOST_WIDEST_INT_PRINT "d\n",
2198 "Total", info.count, info.size);
2199 fprintf (stderr, "---------------------------------------------------------------------------------\n");
2200 }
2201
2202 #include "gt-bitmap.h"
2203