Mercurial > hg > CbC > CbC_gcc

comparison gcc/bitmap.c @ 0:a06113de4d67

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