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