Line data Source code
1 : /* Functions to support general ended bitmaps.
2 : Copyright (C) 1997-2026 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 "bitmap.h"
24 : #include "selftest.h"
25 : #include "pretty-print.h"
26 : #include "splay-tree-utils.h"
27 :
28 : class bitmap_splay_tree_accessors
29 : {
30 : public:
31 : using node_type = bitmap_element *;
32 :
33 308136307 : static node_type &child (node_type node, unsigned int index)
34 : {
35 306640651 : return index ? node->next : node->prev;
36 : }
37 : };
38 :
39 : using bitmap_splay_tree
40 : = splay_tree_without_parent<bitmap_splay_tree_accessors>;
41 :
42 : /* Memory allocation statistics purpose instance. */
43 : mem_alloc_description<bitmap_usage> bitmap_mem_desc;
44 :
45 : /* Static zero-initialized bitmap obstack used for default initialization
46 : of bitmap_head. */
47 : bitmap_obstack bitmap_head::crashme;
48 :
49 : /* Register new bitmap. */
50 : void
51 0 : bitmap_register (bitmap b MEM_STAT_DECL)
52 : {
53 0 : static unsigned alloc_descriptor_max_uid = 1;
54 0 : gcc_assert (b->alloc_descriptor == 0);
55 0 : b->alloc_descriptor = alloc_descriptor_max_uid++;
56 :
57 0 : bitmap_mem_desc.register_descriptor (b->get_descriptor (), BITMAP_ORIGIN,
58 : false FINAL_PASS_MEM_STAT);
59 0 : }
60 :
61 : /* Account the overhead. */
62 : static void
63 0 : register_overhead (bitmap b, size_t amount)
64 : {
65 0 : unsigned *d = b->get_descriptor ();
66 0 : if (bitmap_mem_desc.contains_descriptor_for_instance (d))
67 0 : bitmap_mem_desc.register_instance_overhead (amount, d);
68 0 : }
69 :
70 : /* Release the overhead. */
71 : static void
72 0 : release_overhead (bitmap b, size_t amount, bool remove_from_map)
73 : {
74 0 : unsigned *d = b->get_descriptor ();
75 0 : if (bitmap_mem_desc.contains_descriptor_for_instance (d))
76 0 : bitmap_mem_desc.release_instance_overhead (d, amount, remove_from_map);
77 0 : }
78 :
79 :
80 : /* Global data */
81 : bitmap_element bitmap_zero_bits; /* An element of all zero bits. */
82 : bitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */
83 : static int bitmap_default_obstack_depth;
84 : static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of
85 : GC'd elements. */
86 :
87 :
88 : /* Bitmap memory management. */
89 :
90 : /* Add ELT to the appropriate freelist. */
91 : static inline void
92 926020620 : bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
93 : {
94 926020620 : bitmap_obstack *bit_obstack = head->obstack;
95 :
96 926020620 : if (GATHER_STATISTICS)
97 : release_overhead (head, sizeof (bitmap_element), false);
98 :
99 926020620 : elt->next = NULL;
100 926020620 : elt->indx = -1;
101 926020620 : if (bit_obstack)
102 : {
103 922707946 : elt->prev = bit_obstack->elements;
104 922707946 : bit_obstack->elements = elt;
105 : }
106 : else
107 : {
108 3312674 : elt->prev = bitmap_ggc_free;
109 3312674 : bitmap_ggc_free = elt;
110 : }
111 : }
112 :
113 : /* Allocate a bitmap element. The bits are cleared, but nothing else is. */
114 :
115 : static inline bitmap_element *
116 13819580118 : bitmap_element_allocate (bitmap head)
117 : {
118 13819580118 : bitmap_element *element;
119 13819580118 : bitmap_obstack *bit_obstack = head->obstack;
120 :
121 13819580118 : if (bit_obstack)
122 : {
123 13684821267 : element = bit_obstack->elements;
124 :
125 13684821267 : if (element)
126 : /* Use up the inner list first before looking at the next
127 : element of the outer list. */
128 10389567172 : if (element->next)
129 : {
130 2931908142 : bit_obstack->elements = element->next;
131 2931908142 : bit_obstack->elements->prev = element->prev;
132 : }
133 : else
134 : /* Inner list was just a singleton. */
135 7457659030 : bit_obstack->elements = element->prev;
136 : else
137 3295254095 : element = XOBNEW (&bit_obstack->obstack, bitmap_element);
138 : }
139 : else
140 : {
141 134758851 : element = bitmap_ggc_free;
142 134758851 : if (element)
143 : /* Use up the inner list first before looking at the next
144 : element of the outer list. */
145 109396084 : if (element->next)
146 : {
147 12911739 : bitmap_ggc_free = element->next;
148 12911739 : bitmap_ggc_free->prev = element->prev;
149 : }
150 : else
151 : /* Inner list was just a singleton. */
152 96484345 : bitmap_ggc_free = element->prev;
153 : else
154 25362767 : element = ggc_alloc<bitmap_element> ();
155 : }
156 :
157 13819580118 : if (GATHER_STATISTICS)
158 : register_overhead (head, sizeof (bitmap_element));
159 :
160 13819580118 : memset (element->bits, 0, sizeof (element->bits));
161 :
162 13819580118 : return element;
163 : }
164 :
165 : /* Remove ELT and all following elements from bitmap HEAD.
166 : Put the released elements in the freelist for HEAD. */
167 :
168 : static void
169 7347844455 : bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
170 : {
171 7347844455 : bitmap_element *prev;
172 7347844455 : bitmap_obstack *bit_obstack = head->obstack;
173 :
174 7347844455 : gcc_checking_assert (!head->tree_form);
175 :
176 7347844455 : if (!elt)
177 : return;
178 :
179 6945256767 : if (GATHER_STATISTICS)
180 : {
181 : int n = 0;
182 : for (prev = elt; prev; prev = prev->next)
183 : n++;
184 : release_overhead (head, sizeof (bitmap_element) * n, false);
185 : }
186 :
187 6945256767 : prev = elt->prev;
188 6945256767 : if (prev)
189 : {
190 121148244 : prev->next = NULL;
191 121148244 : if (head->current->indx > prev->indx)
192 : {
193 324572 : head->current = prev;
194 324572 : head->indx = prev->indx;
195 : }
196 : }
197 : else
198 : {
199 6824108523 : head->first = NULL;
200 6824108523 : head->current = NULL;
201 6824108523 : head->indx = 0;
202 : }
203 :
204 : /* Put the entire list onto the freelist in one operation. */
205 6945256767 : if (bit_obstack)
206 : {
207 6846897086 : elt->prev = bit_obstack->elements;
208 6846897086 : bit_obstack->elements = elt;
209 : }
210 : else
211 : {
212 98359681 : elt->prev = bitmap_ggc_free;
213 98359681 : bitmap_ggc_free = elt;
214 : }
215 : }
216 :
217 : /* Linked-list view of bitmaps.
218 :
219 : In this representation, the bitmap elements form a double-linked list
220 : with elements sorted by increasing index. */
221 :
222 : /* Link the bitmap element into the current bitmap linked list. */
223 :
224 : static inline void
225 7487926696 : bitmap_list_link_element (bitmap head, bitmap_element *element)
226 : {
227 7487926696 : unsigned int indx = element->indx;
228 7487926696 : bitmap_element *ptr;
229 :
230 7487926696 : gcc_checking_assert (!head->tree_form);
231 :
232 : /* If this is the first and only element, set it in. */
233 7487926696 : if (head->first == 0)
234 : {
235 5992394601 : element->next = element->prev = 0;
236 5992394601 : head->first = element;
237 : }
238 :
239 : /* If this index is less than that of the current element, it goes someplace
240 : before the current element. */
241 1495532095 : else if (indx < head->indx)
242 : {
243 514804592 : for (ptr = head->current;
244 514804592 : ptr->prev != 0 && ptr->prev->indx > indx;
245 : ptr = ptr->prev)
246 : ;
247 :
248 514804592 : if (ptr->prev)
249 126885307 : ptr->prev->next = element;
250 : else
251 387919285 : head->first = element;
252 :
253 514804592 : element->prev = ptr->prev;
254 514804592 : element->next = ptr;
255 514804592 : ptr->prev = element;
256 : }
257 :
258 : /* Otherwise, it must go someplace after the current element. */
259 : else
260 : {
261 980727503 : for (ptr = head->current;
262 980727503 : ptr->next != 0 && ptr->next->indx < indx;
263 : ptr = ptr->next)
264 : ;
265 :
266 980727503 : if (ptr->next)
267 54705975 : ptr->next->prev = element;
268 :
269 980727503 : element->next = ptr->next;
270 980727503 : element->prev = ptr;
271 980727503 : ptr->next = element;
272 : }
273 :
274 : /* Set up so this is the first element searched. */
275 7487926696 : head->current = element;
276 7487926696 : head->indx = indx;
277 7487926696 : }
278 :
279 : /* Unlink the bitmap element from the current bitmap linked list,
280 : and return it to the freelist. */
281 :
282 : static inline void
283 785910835 : bitmap_list_unlink_element (bitmap head, bitmap_element *element,
284 : bool to_freelist = true)
285 : {
286 785910835 : bitmap_element *next = element->next;
287 785910835 : bitmap_element *prev = element->prev;
288 :
289 785910835 : gcc_checking_assert (!head->tree_form);
290 :
291 785910835 : if (prev)
292 344261569 : prev->next = next;
293 :
294 785910835 : if (next)
295 251790043 : next->prev = prev;
296 :
297 785910835 : if (head->first == element)
298 441649266 : head->first = next;
299 :
300 : /* Since the first thing we try is to insert before current,
301 : make current the next entry in preference to the previous. */
302 785910835 : if (head->current == element)
303 : {
304 676572609 : head->current = next != 0 ? next : prev;
305 676572609 : if (head->current)
306 345980229 : head->indx = head->current->indx;
307 : else
308 330592380 : head->indx = 0;
309 : }
310 :
311 785910835 : if (to_freelist)
312 781319857 : bitmap_elem_to_freelist (head, element);
313 785910835 : }
314 :
315 : /* Insert a new uninitialized element (or NODE if not NULL) into bitmap
316 : HEAD after element ELT. If ELT is NULL, insert the element at the start.
317 : Return the new element. */
318 :
319 : static bitmap_element *
320 3728666541 : bitmap_list_insert_element_after (bitmap head,
321 : bitmap_element *elt, unsigned int indx,
322 : bitmap_element *node = NULL)
323 : {
324 3728666541 : if (!node)
325 3724075563 : node = bitmap_element_allocate (head);
326 3728666541 : node->indx = indx;
327 :
328 3728666541 : gcc_checking_assert (!head->tree_form);
329 :
330 3728666541 : if (!elt)
331 : {
332 1780746607 : if (!head->current)
333 : {
334 1729646528 : head->current = node;
335 1729646528 : head->indx = indx;
336 : }
337 1780746607 : node->next = head->first;
338 1780746607 : if (node->next)
339 51100079 : node->next->prev = node;
340 1780746607 : head->first = node;
341 1780746607 : node->prev = NULL;
342 : }
343 : else
344 : {
345 1947919934 : gcc_checking_assert (head->current);
346 1947919934 : node->next = elt->next;
347 1947919934 : if (node->next)
348 72830023 : node->next->prev = node;
349 1947919934 : elt->next = node;
350 1947919934 : node->prev = elt;
351 : }
352 3728666541 : return node;
353 : }
354 :
355 : /* Return the element for INDX, or NULL if the element doesn't exist.
356 : Update the `current' field even if we can't find an element that
357 : would hold the bitmap's bit to make eventual allocation
358 : faster. */
359 :
360 : static inline bitmap_element *
361 96495324506 : bitmap_list_find_element (bitmap head, unsigned int indx)
362 : {
363 96495324506 : bitmap_element *element;
364 :
365 96495324506 : if (head->current == NULL
366 80869467632 : || head->indx == indx)
367 : return head->current;
368 :
369 11600316108 : if (head->current == head->first
370 5971457862 : && head->first->next == NULL)
371 : return NULL;
372 :
373 : /* Usage can be NULL due to allocated bitmaps for which we do not
374 : call initialize function. */
375 7936366332 : bitmap_usage *usage = NULL;
376 7936366332 : if (GATHER_STATISTICS)
377 : usage = bitmap_mem_desc.get_descriptor_for_instance (head);
378 :
379 : /* This bitmap has more than one element, and we're going to look
380 : through the elements list. Count that as a search. */
381 7936366332 : if (GATHER_STATISTICS && usage)
382 : usage->m_nsearches++;
383 :
384 7936366332 : if (head->indx < indx)
385 : /* INDX is beyond head->indx. Search from head->current
386 : forward. */
387 : for (element = head->current;
388 9671275222 : element->next != 0 && element->indx < indx;
389 : element = element->next)
390 : {
391 : if (GATHER_STATISTICS && usage)
392 : usage->m_search_iter++;
393 : }
394 :
395 4248723094 : else if (head->indx / 2 < indx)
396 : /* INDX is less than head->indx and closer to head->indx than to
397 : 0. Search from head->current backward. */
398 : for (element = head->current;
399 2814323218 : element->prev != 0 && element->indx > indx;
400 : element = element->prev)
401 : {
402 : if (GATHER_STATISTICS && usage)
403 : usage->m_search_iter++;
404 : }
405 :
406 : else
407 : /* INDX is less than head->indx and closer to 0 than to
408 : head->indx. Search from head->first forward. */
409 : for (element = head->first;
410 4829094169 : element->next != 0 && element->indx < indx;
411 : element = element->next)
412 : {
413 : if (GATHER_STATISTICS && usage)
414 : usage->m_search_iter++;
415 : }
416 :
417 : /* `element' is the nearest to the one we want. If it's not the one we
418 : want, the one we want doesn't exist. */
419 7936366332 : gcc_checking_assert (element != NULL);
420 7936366332 : head->current = element;
421 7936366332 : head->indx = element->indx;
422 7936366332 : if (element->indx != indx)
423 6932111043 : element = 0;
424 : return element;
425 : }
426 :
427 :
428 : /* Splay-tree view of bitmaps.
429 :
430 : This is an almost one-to-one the implementation of the simple top-down
431 : splay tree in Sleator and Tarjan's "Self-adjusting Binary Search Trees".
432 : It is probably not the most efficient form of splay trees, but it should
433 : be good enough to experiment with this idea of bitmaps-as-trees.
434 :
435 : For all functions below, the variable or function argument "t" is a node
436 : in the tree, and "e" is a temporary or new node in the tree. The rest
437 : is sufficiently straight-forward (and very well explained in the paper)
438 : that comment would only clutter things. */
439 :
440 : static inline void
441 269168283 : bitmap_tree_link_left (bitmap_element * &t, bitmap_element * &l)
442 : {
443 269168283 : l->next = t;
444 269168283 : l = t;
445 269168283 : t = t->next;
446 269168283 : }
447 :
448 : static inline void
449 269274963 : bitmap_tree_link_right (bitmap_element * &t, bitmap_element * &r)
450 : {
451 269274963 : r->prev = t;
452 269274963 : r = t;
453 269274963 : t = t->prev;
454 269274963 : }
455 :
456 : static inline void
457 93940769 : bitmap_tree_rotate_left (bitmap_element * &t)
458 : {
459 93940769 : bitmap_element *e = t->next;
460 93940769 : t->next = t->next->prev;
461 93940769 : e->prev = t;
462 93940769 : t = e;
463 93940769 : }
464 :
465 : static inline void
466 95036621 : bitmap_tree_rotate_right (bitmap_element * &t)
467 : {
468 95036621 : bitmap_element *e = t->prev;
469 95036621 : t->prev = t->prev->next;
470 95036621 : e->next = t;
471 95036621 : t = e;
472 95036621 : }
473 :
474 : static bitmap_element *
475 727295847 : bitmap_tree_splay (bitmap head, bitmap_element *t, unsigned int indx)
476 : {
477 727295847 : bitmap_element N, *l, *r;
478 :
479 727295847 : if (t == NULL)
480 : return NULL;
481 :
482 727295847 : bitmap_usage *usage = NULL;
483 727295847 : if (GATHER_STATISTICS)
484 : usage = bitmap_mem_desc.get_descriptor_for_instance (head);
485 :
486 727295847 : N.prev = N.next = NULL;
487 727295847 : l = r = &N;
488 :
489 1265739093 : while (indx != t->indx)
490 : {
491 672160156 : if (GATHER_STATISTICS && usage)
492 : usage->m_search_iter++;
493 :
494 672160156 : if (indx < t->indx)
495 : {
496 339015866 : if (t->prev != NULL && indx < t->prev->indx)
497 95036621 : bitmap_tree_rotate_right (t);
498 339015866 : if (t->prev == NULL)
499 : break;
500 269274963 : bitmap_tree_link_right (t, r);
501 : }
502 333144290 : else if (indx > t->indx)
503 : {
504 333144290 : if (t->next != NULL && indx > t->next->indx)
505 93940769 : bitmap_tree_rotate_left (t);
506 333144290 : if (t->next == NULL)
507 : break;
508 269168283 : bitmap_tree_link_left (t, l);
509 : }
510 : }
511 :
512 727295847 : l->next = t->prev;
513 727295847 : r->prev = t->next;
514 727295847 : t->prev = N.next;
515 727295847 : t->next = N.prev;
516 727295847 : return t;
517 : }
518 :
519 : /* Link bitmap element E into the current bitmap splay tree. The caller
520 : must have called bitmap_tree_find_element first, which guarantees that
521 : the current root should become a neighbor of E. */
522 :
523 : static inline void
524 253466658 : bitmap_tree_link_element (bitmap head, bitmap_element *e)
525 : {
526 253466658 : bitmap_element *t = head->first;
527 253466658 : if (t == NULL)
528 183315143 : e->prev = e->next = NULL;
529 : else
530 : {
531 70151515 : if (e->indx < t->indx)
532 : {
533 35203460 : e->prev = t->prev;
534 35203460 : e->next = t;
535 35203460 : t->prev = NULL;
536 : }
537 34948055 : else if (e->indx > t->indx)
538 : {
539 34948055 : e->next = t->next;
540 34948055 : e->prev = t;
541 34948055 : t->next = NULL;
542 : }
543 : else
544 0 : gcc_unreachable ();
545 : }
546 253466658 : head->first = e;
547 253466658 : head->current = e;
548 253466658 : head->indx = e->indx;
549 253466658 : }
550 :
551 : /* Unlink bitmap element E from the current bitmap splay tree,
552 : and return it to the freelist. */
553 :
554 : static void
555 144700763 : bitmap_tree_unlink_element (bitmap head, bitmap_element *e)
556 : {
557 144700763 : bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx);
558 :
559 144700763 : gcc_checking_assert (t == e);
560 :
561 144700763 : if (e->prev == NULL)
562 138544775 : t = e->next;
563 6155988 : else if (e->next == NULL)
564 : t = e->prev;
565 : else
566 : {
567 894099 : t = bitmap_tree_splay (head, e->prev, e->indx);
568 894099 : t->next = e->next;
569 : }
570 144700763 : head->first = t;
571 144700763 : head->current = t;
572 144700763 : head->indx = (t != NULL) ? t->indx : 0;
573 :
574 144700763 : bitmap_elem_to_freelist (head, e);
575 144700763 : }
576 :
577 : /* Return the element for INDX, or NULL if the element doesn't exist. */
578 :
579 : static inline bitmap_element *
580 3881887670 : bitmap_tree_find_element (bitmap head, unsigned int indx)
581 : {
582 3881887670 : if (head->current == NULL
583 2725647318 : || head->indx == indx)
584 : return head->current;
585 :
586 : /* Usage can be NULL due to allocated bitmaps for which we do not
587 : call initialize function. */
588 581700985 : bitmap_usage *usage = NULL;
589 581700985 : if (GATHER_STATISTICS)
590 : usage = bitmap_mem_desc.get_descriptor_for_instance (head);
591 :
592 : /* This bitmap has more than one element, and we're going to look
593 : through the elements list. Count that as a search. */
594 581700985 : if (GATHER_STATISTICS && usage)
595 : usage->m_nsearches++;
596 :
597 581700985 : bitmap_element *element = bitmap_tree_splay (head, head->first, indx);
598 581700985 : gcc_checking_assert (element != NULL);
599 581700985 : head->first = element;
600 581700985 : head->current = element;
601 581700985 : head->indx = element->indx;
602 581700985 : if (element->indx != indx)
603 132822811 : element = 0;
604 : return element;
605 : }
606 :
607 : /* Converting bitmap views from linked-list to tree and vice versa. */
608 :
609 : /* Convert bitmap HEAD from splay-tree view to linked-list view. */
610 :
611 : void
612 71720097 : bitmap_list_view (bitmap head)
613 : {
614 71720097 : gcc_assert (head->tree_form);
615 :
616 71720097 : if (bitmap_element *node = head->first)
617 : {
618 : bitmap_element *last = nullptr;
619 :
620 : /* STACK is a stack of nodes linked by their left child. Each entry N
621 : represents a set of nodes that contains N itself and all nodes in N's
622 : right subtree. The sets are ordered so that every element of the top
623 : set comes before every element in the next set down, and so on. */
624 : bitmap_element *stack = nullptr;
625 :
626 113411122 : add_subtree:
627 : /* Add NODE and its left and right subtrees to the list. Start by
628 : moving down NODE's left spine, pushing each nonterminal node onto
629 : the stack. */
630 113411122 : while (bitmap_element *left = node->prev)
631 : {
632 23401808 : node->prev = stack;
633 23401808 : stack = node;
634 23401808 : node = left;
635 23401808 : }
636 :
637 90009314 : add_node_and_right_subtree:
638 : /* Add NODE and its right subtree to the list. NODE is therefore the
639 : next entry in the list. */
640 113411122 : if (last)
641 44663635 : last->next = node;
642 : else
643 68747487 : head->first = node;
644 113411122 : node->prev = last;
645 113411122 : last = node;
646 :
647 : /* Move to NODE's right child and repeat the process. */
648 113411122 : node = node->next;
649 113411122 : if (node)
650 21261827 : goto add_subtree;
651 :
652 : /* Pop the top node from the stack and add it to the end of the list. */
653 92149295 : if (stack)
654 : {
655 23401808 : node = stack;
656 23401808 : stack = stack->prev;
657 23401808 : goto add_node_and_right_subtree;
658 : }
659 :
660 68747487 : if (!head->current)
661 : {
662 0 : head->current = head->first;
663 0 : head->indx = head->first->indx;
664 : }
665 : }
666 :
667 71720097 : head->tree_form = false;
668 71720097 : }
669 :
670 : /* Convert bitmap HEAD from linked-list view to splay-tree view.
671 : This is simply a matter of dropping the prev or next pointers
672 : and setting the tree_form flag. The tree will balance itself
673 : if and when it is used. */
674 :
675 : void
676 251972471 : bitmap_tree_view (bitmap head)
677 : {
678 251972471 : bitmap_element *ptr;
679 :
680 251972471 : gcc_assert (! head->tree_form);
681 :
682 251972471 : ptr = head->first;
683 261042407 : while (ptr)
684 : {
685 9069936 : ptr->prev = NULL;
686 9069936 : ptr = ptr->next;
687 : }
688 :
689 251972471 : head->tree_form = true;
690 251972471 : }
691 :
692 : /* Clear a bitmap by freeing all its elements. */
693 :
694 : void
695 13499608030 : bitmap_clear (bitmap head)
696 : {
697 13499608030 : if (head->first == NULL)
698 : return;
699 6553874506 : bool tree_form = head->tree_form;
700 6553874506 : if (tree_form)
701 50759915 : bitmap_list_view (head);
702 6553874506 : bitmap_elt_clear_from (head, head->first);
703 6553874506 : head->tree_form = tree_form;
704 : }
705 :
706 : /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
707 : the default bitmap obstack. */
708 :
709 : void
710 350102013 : bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
711 : {
712 350102013 : if (!bit_obstack)
713 : {
714 47607771 : if (bitmap_default_obstack_depth++)
715 : return;
716 : bit_obstack = &bitmap_default_obstack;
717 : }
718 :
719 : #if !defined(__GNUC__) || (__GNUC__ < 2)
720 : #define __alignof__(type) 0
721 : #endif
722 :
723 338629416 : bit_obstack->elements = NULL;
724 338629416 : bit_obstack->heads = NULL;
725 338629416 : obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE,
726 : __alignof__ (bitmap_element),
727 : obstack_chunk_alloc,
728 : obstack_chunk_free);
729 : }
730 :
731 : /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL,
732 : release the default bitmap obstack. */
733 :
734 : void
735 350062108 : bitmap_obstack_release (bitmap_obstack *bit_obstack)
736 : {
737 350062108 : if (!bit_obstack)
738 : {
739 47585827 : if (--bitmap_default_obstack_depth)
740 : {
741 11472112 : gcc_assert (bitmap_default_obstack_depth > 0);
742 : return;
743 : }
744 : bit_obstack = &bitmap_default_obstack;
745 : }
746 :
747 338589996 : bit_obstack->elements = NULL;
748 338589996 : bit_obstack->heads = NULL;
749 338589996 : obstack_free (&bit_obstack->obstack, NULL);
750 : }
751 :
752 : /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create
753 : it on the default bitmap obstack. */
754 :
755 : bitmap
756 3927430982 : bitmap_alloc (bitmap_obstack *bit_obstack MEM_STAT_DECL)
757 : {
758 3927430982 : bitmap map;
759 :
760 3927430982 : if (!bit_obstack)
761 : {
762 726713635 : gcc_assert (bitmap_default_obstack_depth > 0);
763 : bit_obstack = &bitmap_default_obstack;
764 : }
765 3927430982 : map = bit_obstack->heads;
766 3927430982 : if (map)
767 1285336656 : bit_obstack->heads = (class bitmap_head *) map->first;
768 : else
769 2642094326 : map = XOBNEW (&bit_obstack->obstack, bitmap_head);
770 3927430982 : bitmap_initialize (map, bit_obstack PASS_MEM_STAT);
771 :
772 3927430982 : if (GATHER_STATISTICS)
773 : register_overhead (map, sizeof (bitmap_head));
774 :
775 3927430982 : return map;
776 : }
777 :
778 : /* Create a new GCd bitmap. */
779 :
780 : bitmap
781 47174322 : bitmap_gc_alloc (ALONE_MEM_STAT_DECL)
782 : {
783 47174322 : bitmap map;
784 :
785 47174322 : map = ggc_alloc<bitmap_head> ();
786 47174322 : bitmap_initialize (map, NULL PASS_MEM_STAT);
787 :
788 47174322 : if (GATHER_STATISTICS)
789 : register_overhead (map, sizeof (bitmap_head));
790 :
791 47174322 : return map;
792 : }
793 :
794 : /* Release an obstack allocated bitmap. */
795 :
796 : void
797 2568138873 : bitmap_obstack_free (bitmap map)
798 : {
799 2568138873 : if (map)
800 : {
801 1452068619 : bitmap_clear (map);
802 1452068619 : map->first = (bitmap_element *) map->obstack->heads;
803 :
804 1452068619 : if (GATHER_STATISTICS)
805 : release_overhead (map, sizeof (bitmap_head), true);
806 :
807 1452068619 : map->obstack->heads = map;
808 : }
809 2568138873 : }
810 :
811 :
812 : /* Return nonzero if all bits in an element are zero. */
813 :
814 : static inline int
815 913617321 : bitmap_element_zerop (const bitmap_element *element)
816 : {
817 : #if BITMAP_ELEMENT_WORDS == 2
818 913617321 : return (element->bits[0] | element->bits[1]) == 0;
819 : #else
820 : unsigned i;
821 :
822 : for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
823 : if (element->bits[i] != 0)
824 : return 0;
825 :
826 : return 1;
827 : #endif
828 : }
829 :
830 : /* Copy a bitmap to another bitmap. */
831 :
832 : void
833 1989382574 : bitmap_copy (bitmap to, const_bitmap from)
834 : {
835 1989382574 : const bitmap_element *from_ptr;
836 1989382574 : bitmap_element *to_ptr = 0;
837 :
838 1989382574 : gcc_checking_assert (!to->tree_form && !from->tree_form);
839 :
840 1989382574 : bitmap_clear (to);
841 :
842 : /* Copy elements in forward direction one at a time. */
843 4343493775 : for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
844 : {
845 2354111201 : bitmap_element *to_elt = bitmap_element_allocate (to);
846 :
847 2354111201 : to_elt->indx = from_ptr->indx;
848 2354111201 : memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits));
849 :
850 : /* Here we have a special case of bitmap_list_link_element,
851 : for the case where we know the links are being entered
852 : in sequence. */
853 2354111201 : if (to_ptr == 0)
854 : {
855 1572320705 : to->first = to->current = to_elt;
856 1572320705 : to->indx = from_ptr->indx;
857 1572320705 : to_elt->next = to_elt->prev = 0;
858 : }
859 : else
860 : {
861 781790496 : to_elt->prev = to_ptr;
862 781790496 : to_elt->next = 0;
863 781790496 : to_ptr->next = to_elt;
864 : }
865 :
866 2354111201 : to_ptr = to_elt;
867 : }
868 1989382574 : }
869 :
870 : /* Move a bitmap to another bitmap. */
871 :
872 : void
873 25074659 : bitmap_move (bitmap to, bitmap from)
874 : {
875 25074659 : gcc_assert (to->obstack == from->obstack);
876 :
877 25074659 : bitmap_clear (to);
878 :
879 25074659 : size_t sz = 0;
880 25074659 : if (GATHER_STATISTICS)
881 : {
882 : for (bitmap_element *e = to->first; e; e = e->next)
883 : sz += sizeof (bitmap_element);
884 : register_overhead (to, sz);
885 : }
886 :
887 25074659 : *to = *from;
888 :
889 25074659 : if (GATHER_STATISTICS)
890 : release_overhead (from, sz, false);
891 25074659 : }
892 :
893 : /* Clear a single bit in a bitmap. Return true if the bit changed. */
894 :
895 : bool
896 25758866798 : bitmap_clear_bit (bitmap head, int bit)
897 : {
898 25758866798 : unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
899 25758866798 : bitmap_element *ptr;
900 :
901 25758866798 : if (!head->tree_form)
902 24828870901 : ptr = bitmap_list_find_element (head, indx);
903 : else
904 929995897 : ptr = bitmap_tree_find_element (head, indx);
905 25758866798 : if (ptr != 0)
906 : {
907 20874732579 : unsigned bit_num = bit % BITMAP_WORD_BITS;
908 20874732579 : unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
909 20874732579 : BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
910 20874732579 : bool res = (ptr->bits[word_num] & bit_val) != 0;
911 20874732579 : if (res)
912 : {
913 3741003166 : ptr->bits[word_num] &= ~bit_val;
914 : /* If we cleared the entire word, free up the element. */
915 3741003166 : if (!ptr->bits[word_num]
916 3741003166 : && bitmap_element_zerop (ptr))
917 : {
918 693014974 : if (!head->tree_form)
919 571208050 : bitmap_list_unlink_element (head, ptr);
920 : else
921 121806924 : bitmap_tree_unlink_element (head, ptr);
922 : }
923 : }
924 :
925 20874732579 : return res;
926 : }
927 :
928 : return false;
929 : }
930 :
931 : /* Set a single bit in a bitmap. Return true if the bit changed. */
932 :
933 : bool
934 36900460013 : bitmap_set_bit (bitmap head, int bit)
935 : {
936 36900460013 : unsigned indx = bit / BITMAP_ELEMENT_ALL_BITS;
937 36900460013 : bitmap_element *ptr;
938 36900460013 : if (!head->tree_form)
939 34834116177 : ptr = bitmap_list_find_element (head, indx);
940 : else
941 2066343836 : ptr = bitmap_tree_find_element (head, indx);
942 36900460013 : unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
943 36900460013 : unsigned bit_num = bit % BITMAP_WORD_BITS;
944 36900460013 : BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
945 :
946 36900460013 : if (ptr != 0)
947 : {
948 29267611044 : bool res = (ptr->bits[word_num] & bit_val) == 0;
949 : /* Write back unconditionally to avoid branch mispredicts. */
950 29267611044 : ptr->bits[word_num] |= bit_val;
951 29267611044 : return res;
952 : }
953 :
954 7632848969 : ptr = bitmap_element_allocate (head);
955 7632848969 : ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
956 7632848969 : ptr->bits[word_num] = bit_val;
957 7632848969 : if (!head->tree_form)
958 7379531823 : bitmap_list_link_element (head, ptr);
959 : else
960 253317146 : bitmap_tree_link_element (head, ptr);
961 : return true;
962 : }
963 :
964 : /* Return whether a bit is set within a bitmap. */
965 :
966 : bool
967 35102860952 : bitmap_bit_p (const_bitmap head, int bit)
968 : {
969 35102860952 : unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
970 35102860952 : const bitmap_element *ptr;
971 35102860952 : unsigned bit_num;
972 35102860952 : unsigned word_num;
973 :
974 35102860952 : if (!head->tree_form)
975 34233191225 : ptr = bitmap_list_find_element (const_cast<bitmap> (head), indx);
976 : else
977 869669727 : ptr = bitmap_tree_find_element (const_cast<bitmap> (head), indx);
978 35102860952 : if (ptr == 0)
979 : return 0;
980 :
981 25235197065 : bit_num = bit % BITMAP_WORD_BITS;
982 25235197065 : word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
983 :
984 25235197065 : return (ptr->bits[word_num] >> bit_num) & 1;
985 : }
986 :
987 : /* Set CHUNK_SIZE bits at a time in bitmap HEAD.
988 : Store CHUNK_VALUE starting at bits CHUNK * chunk_size.
989 : This is the set routine for viewing bitmap as a multi-bit sparse array. */
990 :
991 : void
992 485287 : bitmap_set_aligned_chunk (bitmap head, unsigned int chunk,
993 : unsigned int chunk_size, BITMAP_WORD chunk_value)
994 : {
995 : // Ensure chunk size is a power of 2 and fits in BITMAP_WORD.
996 485287 : gcc_checking_assert (pow2p_hwi (chunk_size));
997 485287 : gcc_checking_assert (chunk_size < (sizeof (BITMAP_WORD) * CHAR_BIT));
998 :
999 : // Ensure chunk_value is within range of chunk_size bits.
1000 485287 : BITMAP_WORD max_value = (1 << chunk_size) - 1;
1001 485287 : gcc_checking_assert (chunk_value <= max_value);
1002 :
1003 485287 : unsigned bit = chunk * chunk_size;
1004 485287 : unsigned indx = bit / BITMAP_ELEMENT_ALL_BITS;
1005 485287 : bitmap_element *ptr;
1006 485287 : if (!head->tree_form)
1007 64 : ptr = bitmap_list_find_element (head, indx);
1008 : else
1009 485223 : ptr = bitmap_tree_find_element (head, indx);
1010 485287 : unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
1011 485287 : unsigned bit_num = bit % BITMAP_WORD_BITS;
1012 485287 : BITMAP_WORD bit_val = chunk_value << bit_num;
1013 485287 : BITMAP_WORD mask = ~(max_value << bit_num);
1014 :
1015 485287 : if (ptr != 0)
1016 : {
1017 335763 : ptr->bits[word_num] &= mask;
1018 335763 : ptr->bits[word_num] |= bit_val;
1019 335763 : return;
1020 : }
1021 :
1022 149524 : ptr = bitmap_element_allocate (head);
1023 149524 : ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
1024 149524 : ptr->bits[word_num] = bit_val;
1025 149524 : if (!head->tree_form)
1026 12 : bitmap_list_link_element (head, ptr);
1027 : else
1028 149512 : bitmap_tree_link_element (head, ptr);
1029 : }
1030 :
1031 : /* This is the get routine for viewing bitmap as a multi-bit sparse array.
1032 : Return a set of CHUNK_SIZE consecutive bits from HEAD, starting at bit
1033 : CHUNK * chunk_size. */
1034 :
1035 : BITMAP_WORD
1036 15393243 : bitmap_get_aligned_chunk (const_bitmap head, unsigned int chunk,
1037 : unsigned int chunk_size)
1038 : {
1039 : // Ensure chunk size is a power of 2, fits in BITMAP_WORD and is in range.
1040 15393243 : gcc_checking_assert (pow2p_hwi (chunk_size));
1041 15393243 : gcc_checking_assert (chunk_size < (sizeof (BITMAP_WORD) * CHAR_BIT));
1042 :
1043 15393243 : BITMAP_WORD max_value = (1 << chunk_size) - 1;
1044 15393243 : unsigned bit = chunk * chunk_size;
1045 15393243 : unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
1046 15393243 : const bitmap_element *ptr;
1047 15393243 : unsigned bit_num;
1048 15393243 : unsigned word_num;
1049 :
1050 15393243 : if (!head->tree_form)
1051 256 : ptr = bitmap_list_find_element (const_cast<bitmap> (head), indx);
1052 : else
1053 15392987 : ptr = bitmap_tree_find_element (const_cast<bitmap> (head), indx);
1054 15393243 : if (ptr == 0)
1055 : return 0;
1056 :
1057 5533154 : bit_num = bit % BITMAP_WORD_BITS;
1058 5533154 : word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
1059 :
1060 : // Return 4 bits.
1061 5533154 : return (ptr->bits[word_num] >> bit_num) & max_value;
1062 : }
1063 :
1064 : #if GCC_VERSION < 3400
1065 : /* Table of number of set bits in a character, indexed by value of char. */
1066 : static const unsigned char popcount_table[] =
1067 : {
1068 : 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,
1069 : 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,
1070 : 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,
1071 : 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,
1072 : 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,
1073 : 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,
1074 : 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,
1075 : 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,
1076 : };
1077 :
1078 : static unsigned long
1079 : bitmap_popcount (BITMAP_WORD a)
1080 : {
1081 : unsigned long ret = 0;
1082 : unsigned i;
1083 :
1084 : /* Just do this the table way for now */
1085 : for (i = 0; i < BITMAP_WORD_BITS; i+= 8)
1086 : ret += popcount_table[(a >> i) & 0xff];
1087 : return ret;
1088 : }
1089 : #endif
1090 :
1091 : /* Count and return the number of bits set in the bitmap word BITS. */
1092 : static unsigned long
1093 68874638 : bitmap_count_bits_in_word (const BITMAP_WORD *bits)
1094 : {
1095 68874638 : unsigned long count = 0;
1096 :
1097 209465052 : for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1098 : {
1099 : #if GCC_VERSION >= 3400
1100 : /* Note that popcountl matches BITMAP_WORD in type, so the actual size
1101 : of BITMAP_WORD is not material. */
1102 139643368 : count += __builtin_popcountl (bits[ix]);
1103 : #else
1104 : count += bitmap_popcount (bits[ix]);
1105 : #endif
1106 : }
1107 69821684 : return count;
1108 : }
1109 :
1110 : /* Count the number of bits set in the bitmap, and return it. */
1111 :
1112 : unsigned long
1113 139266380 : bitmap_count_bits (const_bitmap a)
1114 : {
1115 139266380 : unsigned long count = 0;
1116 139266380 : const bitmap_element *elt;
1117 :
1118 139266380 : gcc_checking_assert (!a->tree_form);
1119 207947448 : for (elt = a->first; elt; elt = elt->next)
1120 137362136 : count += bitmap_count_bits_in_word (elt->bits);
1121 :
1122 139266380 : return count;
1123 : }
1124 :
1125 : /* Count the number of unique bits set in A and B and return it. */
1126 :
1127 : unsigned long
1128 797388 : bitmap_count_unique_bits (const_bitmap a, const_bitmap b)
1129 : {
1130 797388 : unsigned long count = 0;
1131 797388 : const bitmap_element *elt_a, *elt_b;
1132 :
1133 1938004 : for (elt_a = a->first, elt_b = b->first; elt_a && elt_b; )
1134 : {
1135 : /* If we're at different indices, then count all the bits
1136 : in the lower element. If we're at the same index, then
1137 : count the bits in the IOR of the two elements. */
1138 1140616 : if (elt_a->indx < elt_b->indx)
1139 : {
1140 83392 : count += bitmap_count_bits_in_word (elt_a->bits);
1141 83392 : elt_a = elt_a->next;
1142 : }
1143 1057224 : else if (elt_b->indx < elt_a->indx)
1144 : {
1145 110178 : count += bitmap_count_bits_in_word (elt_b->bits);
1146 110178 : elt_b = elt_b->next;
1147 : }
1148 : else
1149 : {
1150 : BITMAP_WORD bits[BITMAP_ELEMENT_WORDS];
1151 2841138 : for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1152 1894092 : bits[ix] = elt_a->bits[ix] | elt_b->bits[ix];
1153 947046 : count += bitmap_count_bits_in_word (bits);
1154 947046 : elt_a = elt_a->next;
1155 947046 : elt_b = elt_b->next;
1156 : }
1157 : }
1158 797388 : return count;
1159 : }
1160 :
1161 : /* Return true if the bitmap has a single bit set. Otherwise return
1162 : false. */
1163 :
1164 : bool
1165 2693238 : bitmap_single_bit_set_p (const_bitmap a)
1166 : {
1167 2693238 : unsigned long count = 0;
1168 2693238 : const bitmap_element *elt;
1169 2693238 : unsigned ix;
1170 :
1171 2693238 : if (bitmap_empty_p (a))
1172 : return false;
1173 :
1174 2691892 : elt = a->first;
1175 :
1176 : /* As there are no completely empty bitmap elements, a second one
1177 : means we have more than one bit set. */
1178 2691892 : if (elt->next != NULL
1179 278452 : && (!a->tree_form || elt->prev != NULL))
1180 : return false;
1181 :
1182 5494649 : for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1183 : {
1184 : #if GCC_VERSION >= 3400
1185 : /* Note that popcountl matches BITMAP_WORD in type, so the actual size
1186 : of BITMAP_WORD is not material. */
1187 4095999 : count += __builtin_popcountl (elt->bits[ix]);
1188 : #else
1189 : count += bitmap_popcount (elt->bits[ix]);
1190 : #endif
1191 4095999 : if (count > 1)
1192 : return false;
1193 : }
1194 :
1195 1398650 : return count == 1;
1196 : }
1197 :
1198 :
1199 : /* Return the bit number of the first set bit in the bitmap. The
1200 : bitmap must be non-empty. When CLEAR is true it clears the bit. */
1201 :
1202 : static unsigned
1203 730547510 : bitmap_first_set_bit_worker (bitmap a, bool clear)
1204 : {
1205 730547510 : bitmap_element *elt = a->first;
1206 730547510 : unsigned bit_no;
1207 730547510 : BITMAP_WORD word;
1208 730547510 : unsigned ix;
1209 :
1210 730547510 : gcc_checking_assert (elt);
1211 :
1212 730547510 : if (a->tree_form)
1213 300189972 : elt = a->first = bitmap_splay_tree (elt).min_node ();
1214 :
1215 730547510 : bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
1216 923480582 : for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1217 : {
1218 923480582 : word = elt->bits[ix];
1219 923480582 : if (word)
1220 730547510 : goto found_bit;
1221 : }
1222 0 : gcc_unreachable ();
1223 730547510 : found_bit:
1224 730547510 : bit_no += ix * BITMAP_WORD_BITS;
1225 :
1226 : #if GCC_VERSION >= 3004
1227 730547510 : gcc_assert (sizeof (long) == sizeof (word));
1228 730547510 : bit_no += __builtin_ctzl (word);
1229 : #else
1230 : /* Binary search for the first set bit. */
1231 : #if BITMAP_WORD_BITS > 64
1232 : #error "Fill out the table."
1233 : #endif
1234 : #if BITMAP_WORD_BITS > 32
1235 : if (!(word & 0xffffffff))
1236 : word >>= 32, bit_no += 32;
1237 : #endif
1238 : if (!(word & 0xffff))
1239 : word >>= 16, bit_no += 16;
1240 : if (!(word & 0xff))
1241 : word >>= 8, bit_no += 8;
1242 : if (!(word & 0xf))
1243 : word >>= 4, bit_no += 4;
1244 : if (!(word & 0x3))
1245 : word >>= 2, bit_no += 2;
1246 : if (!(word & 0x1))
1247 : word >>= 1, bit_no += 1;
1248 :
1249 : gcc_checking_assert (word & 1);
1250 : #endif
1251 :
1252 730547510 : if (clear)
1253 : {
1254 226339017 : elt->bits[ix] &= ~((BITMAP_WORD) 1 << (bit_no % BITMAP_WORD_BITS));
1255 : /* If we cleared the entire word, free up the element. */
1256 226339017 : if (!elt->bits[ix]
1257 226339017 : && bitmap_element_zerop (elt))
1258 : {
1259 46824995 : if (!a->tree_form)
1260 23931176 : bitmap_list_unlink_element (a, elt);
1261 : else
1262 22893819 : bitmap_tree_unlink_element (a, elt);
1263 : }
1264 : }
1265 :
1266 730547510 : return bit_no;
1267 : }
1268 :
1269 : /* Return the bit number of the first set bit in the bitmap. The
1270 : bitmap must be non-empty. */
1271 :
1272 : unsigned
1273 504208493 : bitmap_first_set_bit (const_bitmap a)
1274 : {
1275 504208493 : return bitmap_first_set_bit_worker (const_cast<bitmap> (a), false);
1276 : }
1277 :
1278 : /* Return and clear the bit number of the first set bit in the bitmap. The
1279 : bitmap must be non-empty. */
1280 :
1281 : unsigned
1282 226339017 : bitmap_clear_first_set_bit (bitmap a)
1283 : {
1284 226339017 : return bitmap_first_set_bit_worker (a, true);
1285 : }
1286 :
1287 : /* Return the bit number of the last set bit in the bitmap. The bitmap
1288 : must be non-empty. When CLEAR is true, also clear the bit. */
1289 :
1290 : static unsigned
1291 20 : bitmap_last_set_bit_worker (bitmap a, bool clear)
1292 : {
1293 20 : bitmap_element *elt;
1294 20 : unsigned bit_no;
1295 20 : BITMAP_WORD word;
1296 20 : int ix;
1297 :
1298 20 : if (a->tree_form)
1299 20 : elt = a->first = bitmap_splay_tree (a->first).max_node ();
1300 : else
1301 : {
1302 0 : elt = a->current ? a->current : a->first;
1303 0 : while (elt->next)
1304 : elt = elt->next;
1305 : }
1306 :
1307 20 : bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
1308 40 : for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--)
1309 : {
1310 40 : word = elt->bits[ix];
1311 40 : if (word)
1312 20 : goto found_bit;
1313 : }
1314 0 : gcc_unreachable ();
1315 20 : found_bit:
1316 20 : bit_no += ix * BITMAP_WORD_BITS;
1317 : #if GCC_VERSION >= 3004
1318 20 : gcc_assert (sizeof (long) == sizeof (word));
1319 20 : bit_no += BITMAP_WORD_BITS - __builtin_clzl (word) - 1;
1320 : #else
1321 : /* Hopefully this is a twos-complement host... */
1322 : BITMAP_WORD x = word;
1323 : x |= (x >> 1);
1324 : x |= (x >> 2);
1325 : x |= (x >> 4);
1326 : x |= (x >> 8);
1327 : x |= (x >> 16);
1328 : #if BITMAP_WORD_BITS > 32
1329 : x |= (x >> 32);
1330 : #endif
1331 : bit_no += bitmap_popcount (x) - 1;
1332 : #endif
1333 :
1334 20 : if (clear)
1335 : {
1336 20 : elt->bits[ix] &= ~((BITMAP_WORD) 1 << (bit_no % BITMAP_WORD_BITS));
1337 : /* If we cleared the entire word, free up the element. */
1338 20 : if (!elt->bits[ix]
1339 20 : && bitmap_element_zerop (elt))
1340 : {
1341 20 : if (!a->tree_form)
1342 0 : bitmap_list_unlink_element (a, elt);
1343 : else
1344 20 : bitmap_tree_unlink_element (a, elt);
1345 : }
1346 : }
1347 :
1348 20 : return bit_no;
1349 : }
1350 :
1351 : /* Return the bit number of the last set bit in the bitmap.
1352 : The bitmap must be non-empty. */
1353 :
1354 : unsigned
1355 0 : bitmap_last_set_bit (const_bitmap a)
1356 : {
1357 0 : return bitmap_last_set_bit_worker (const_cast<bitmap> (a), false);
1358 : }
1359 :
1360 : /* Return and clear the bit number of the last set bit in the bitmap.
1361 : The bitmap must be non-empty. */
1362 :
1363 : unsigned
1364 20 : bitmap_clear_last_set_bit (bitmap a)
1365 : {
1366 20 : return bitmap_last_set_bit_worker (a, true);
1367 : }
1368 :
1369 :
1370 :
1371 : /* DST = A & B. */
1372 :
1373 : void
1374 738131408 : bitmap_and (bitmap dst, const_bitmap a, const_bitmap b)
1375 : {
1376 738131408 : bitmap_element *dst_elt = dst->first;
1377 738131408 : const bitmap_element *a_elt = a->first;
1378 738131408 : const bitmap_element *b_elt = b->first;
1379 738131408 : bitmap_element *dst_prev = NULL;
1380 :
1381 738131408 : gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
1382 738131408 : gcc_assert (dst != a && dst != b);
1383 :
1384 738131408 : if (a == b)
1385 : {
1386 0 : bitmap_copy (dst, a);
1387 0 : return;
1388 : }
1389 :
1390 1727841982 : while (a_elt && b_elt)
1391 : {
1392 989710574 : if (a_elt->indx < b_elt->indx)
1393 25404428 : a_elt = a_elt->next;
1394 964306146 : else if (b_elt->indx < a_elt->indx)
1395 180636932 : b_elt = b_elt->next;
1396 : else
1397 : {
1398 : /* Matching elts, generate A & B. */
1399 783669214 : unsigned ix;
1400 783669214 : BITMAP_WORD ior = 0;
1401 :
1402 783669214 : if (!dst_elt)
1403 259740072 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
1404 : a_elt->indx);
1405 : else
1406 523929142 : dst_elt->indx = a_elt->indx;
1407 2351007642 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1408 : {
1409 1567338428 : BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
1410 :
1411 1567338428 : dst_elt->bits[ix] = r;
1412 1567338428 : ior |= r;
1413 : }
1414 783669214 : if (ior)
1415 : {
1416 468970848 : dst_prev = dst_elt;
1417 468970848 : dst_elt = dst_elt->next;
1418 : }
1419 783669214 : a_elt = a_elt->next;
1420 783669214 : b_elt = b_elt->next;
1421 : }
1422 : }
1423 : /* Ensure that dst->current is valid. */
1424 738131408 : dst->current = dst->first;
1425 738131408 : bitmap_elt_clear_from (dst, dst_elt);
1426 738131408 : gcc_checking_assert (!dst->current == !dst->first);
1427 738131408 : if (dst->current)
1428 403938498 : dst->indx = dst->current->indx;
1429 : }
1430 :
1431 : /* A &= B. Return true if A changed. */
1432 :
1433 : bool
1434 1026554164 : bitmap_and_into (bitmap a, const_bitmap b)
1435 : {
1436 1026554164 : bitmap_element *a_elt = a->first;
1437 1026554164 : const bitmap_element *b_elt = b->first;
1438 1026554164 : bitmap_element *next;
1439 1026554164 : bool changed = false;
1440 :
1441 1026554164 : gcc_checking_assert (!a->tree_form && !b->tree_form);
1442 :
1443 1026554164 : if (a == b)
1444 : return false;
1445 :
1446 2977040926 : while (a_elt && b_elt)
1447 : {
1448 1950486762 : if (a_elt->indx < b_elt->indx)
1449 : {
1450 38139589 : next = a_elt->next;
1451 38139589 : bitmap_list_unlink_element (a, a_elt);
1452 38139589 : a_elt = next;
1453 38139589 : changed = true;
1454 : }
1455 1912347173 : else if (b_elt->indx < a_elt->indx)
1456 43124782 : b_elt = b_elt->next;
1457 : else
1458 : {
1459 : /* Matching elts, generate A &= B. */
1460 : unsigned ix;
1461 : BITMAP_WORD ior = 0;
1462 :
1463 5607667173 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1464 : {
1465 3738444782 : BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
1466 3738444782 : if (a_elt->bits[ix] != r)
1467 372772438 : changed = true;
1468 3738444782 : a_elt->bits[ix] = r;
1469 3738444782 : ior |= r;
1470 : }
1471 1869222391 : next = a_elt->next;
1472 1869222391 : if (!ior)
1473 6504464 : bitmap_list_unlink_element (a, a_elt);
1474 1869222391 : a_elt = next;
1475 1869222391 : b_elt = b_elt->next;
1476 : }
1477 : }
1478 :
1479 1026554164 : if (a_elt)
1480 : {
1481 54043494 : changed = true;
1482 54043494 : bitmap_elt_clear_from (a, a_elt);
1483 : }
1484 :
1485 1026554164 : gcc_checking_assert (!a->current == !a->first
1486 : && (!a->current || a->indx == a->current->indx));
1487 :
1488 : return changed;
1489 : }
1490 :
1491 :
1492 : /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
1493 : if non-NULL. CHANGED is true if the destination bitmap had already been
1494 : changed; the new value of CHANGED is returned. */
1495 :
1496 : static inline bool
1497 3428677978 : bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
1498 : const bitmap_element *src_elt, bool changed)
1499 : {
1500 3428677978 : if (!changed && dst_elt && dst_elt->indx == src_elt->indx)
1501 : {
1502 : unsigned ix;
1503 :
1504 285552435 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1505 190368290 : if (src_elt->bits[ix] != dst_elt->bits[ix])
1506 : {
1507 26733522 : dst_elt->bits[ix] = src_elt->bits[ix];
1508 26733522 : changed = true;
1509 : }
1510 : }
1511 : else
1512 : {
1513 3431962069 : changed = true;
1514 3266411389 : if (!dst_elt)
1515 3167943153 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
1516 3167943153 : src_elt->indx);
1517 : else
1518 165550680 : dst_elt->indx = src_elt->indx;
1519 3333493833 : memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits));
1520 : }
1521 3428677978 : return changed;
1522 : }
1523 :
1524 :
1525 :
1526 : /* DST = A & ~B */
1527 :
1528 : bool
1529 186307984 : bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b)
1530 : {
1531 186307984 : bitmap_element *dst_elt = dst->first;
1532 186307984 : const bitmap_element *a_elt = a->first;
1533 186307984 : const bitmap_element *b_elt = b->first;
1534 186307984 : bitmap_element *dst_prev = NULL;
1535 186307984 : bitmap_element **dst_prev_pnext = &dst->first;
1536 186307984 : bool changed = false;
1537 :
1538 186307984 : gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
1539 186307984 : gcc_assert (dst != a && dst != b);
1540 :
1541 186307984 : if (a == b)
1542 : {
1543 0 : changed = !bitmap_empty_p (dst);
1544 0 : bitmap_clear (dst);
1545 0 : return changed;
1546 : }
1547 :
1548 526148514 : while (a_elt)
1549 : {
1550 354581122 : while (b_elt && b_elt->indx < a_elt->indx)
1551 14740592 : b_elt = b_elt->next;
1552 :
1553 339840530 : if (!b_elt || b_elt->indx > a_elt->indx)
1554 : {
1555 171856183 : changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed);
1556 171856183 : dst_prev = *dst_prev_pnext;
1557 171856183 : dst_prev_pnext = &dst_prev->next;
1558 171856183 : dst_elt = *dst_prev_pnext;
1559 171856183 : a_elt = a_elt->next;
1560 : }
1561 :
1562 : else
1563 : {
1564 : /* Matching elts, generate A & ~B. */
1565 167984347 : unsigned ix;
1566 167984347 : BITMAP_WORD ior = 0;
1567 :
1568 167984347 : if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1569 : {
1570 134339127 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1571 : {
1572 89559418 : BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1573 :
1574 89559418 : if (dst_elt->bits[ix] != r)
1575 : {
1576 30375538 : changed = true;
1577 30375538 : dst_elt->bits[ix] = r;
1578 : }
1579 89559418 : ior |= r;
1580 : }
1581 : }
1582 : else
1583 : {
1584 106505202 : bool new_element;
1585 123204638 : if (!dst_elt || dst_elt->indx > a_elt->indx)
1586 : {
1587 121990476 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
1588 : a_elt->indx);
1589 121990476 : new_element = true;
1590 : }
1591 : else
1592 : {
1593 1214162 : dst_elt->indx = a_elt->indx;
1594 1214162 : new_element = false;
1595 : }
1596 :
1597 369613914 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1598 : {
1599 246409276 : BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1600 :
1601 246409276 : dst_elt->bits[ix] = r;
1602 246409276 : ior |= r;
1603 : }
1604 :
1605 123204638 : if (ior)
1606 : changed = true;
1607 : else
1608 : {
1609 43406678 : changed |= !new_element;
1610 43406678 : bitmap_list_unlink_element (dst, dst_elt);
1611 43406678 : dst_elt = *dst_prev_pnext;
1612 : }
1613 : }
1614 :
1615 88186387 : if (ior)
1616 : {
1617 123650989 : dst_prev = *dst_prev_pnext;
1618 123650989 : dst_prev_pnext = &dst_prev->next;
1619 123650989 : dst_elt = *dst_prev_pnext;
1620 : }
1621 167984347 : a_elt = a_elt->next;
1622 167984347 : b_elt = b_elt->next;
1623 : }
1624 : }
1625 :
1626 : /* Ensure that dst->current is valid. */
1627 186307984 : dst->current = dst->first;
1628 :
1629 186307984 : if (dst_elt)
1630 : {
1631 1783691 : changed = true;
1632 1783691 : bitmap_elt_clear_from (dst, dst_elt);
1633 : }
1634 186307984 : gcc_checking_assert (!dst->current == !dst->first);
1635 186307984 : if (dst->current)
1636 138830539 : dst->indx = dst->current->indx;
1637 :
1638 : return changed;
1639 : }
1640 :
1641 : /* A &= ~B. Returns true if A changes */
1642 :
1643 : bool
1644 432488838 : bitmap_and_compl_into (bitmap a, const_bitmap b)
1645 : {
1646 432488838 : bitmap_element *a_elt = a->first;
1647 432488838 : const bitmap_element *b_elt = b->first;
1648 432488838 : bitmap_element *next;
1649 432488838 : BITMAP_WORD changed = 0;
1650 :
1651 432488838 : gcc_checking_assert (!a->tree_form && !b->tree_form);
1652 :
1653 432488838 : if (a == b)
1654 : {
1655 0 : if (bitmap_empty_p (a))
1656 : return false;
1657 : else
1658 : {
1659 0 : bitmap_clear (a);
1660 0 : return true;
1661 : }
1662 : }
1663 :
1664 1262391164 : while (a_elt && b_elt)
1665 : {
1666 829902326 : if (a_elt->indx < b_elt->indx)
1667 174857876 : a_elt = a_elt->next;
1668 655044450 : else if (b_elt->indx < a_elt->indx)
1669 344466951 : b_elt = b_elt->next;
1670 : else
1671 : {
1672 : /* Matching elts, generate A &= ~B. */
1673 : unsigned ix;
1674 : BITMAP_WORD ior = 0;
1675 :
1676 931732497 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1677 : {
1678 621154998 : BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1679 621154998 : BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
1680 :
1681 621154998 : a_elt->bits[ix] = r;
1682 621154998 : changed |= cleared;
1683 621154998 : ior |= r;
1684 : }
1685 310577499 : next = a_elt->next;
1686 310577499 : if (!ior)
1687 13505150 : bitmap_list_unlink_element (a, a_elt);
1688 310577499 : a_elt = next;
1689 310577499 : b_elt = b_elt->next;
1690 : }
1691 : }
1692 432488838 : gcc_checking_assert (!a->current == !a->first
1693 : && (!a->current || a->indx == a->current->indx));
1694 432488838 : return changed != 0;
1695 : }
1696 :
1697 : /* Set COUNT bits from START in HEAD. */
1698 : void
1699 1483188102 : bitmap_set_range (bitmap head, unsigned int start, unsigned int count)
1700 : {
1701 1483188102 : unsigned int first_index, end_bit_plus1, last_index;
1702 1483188102 : bitmap_element *elt, *elt_prev;
1703 1483188102 : unsigned int i;
1704 :
1705 1483188102 : gcc_checking_assert (!head->tree_form);
1706 :
1707 1483188102 : if (!count)
1708 : return;
1709 :
1710 1190284096 : if (count == 1)
1711 : {
1712 577344550 : bitmap_set_bit (head, start);
1713 577344550 : return;
1714 : }
1715 :
1716 612939546 : first_index = start / BITMAP_ELEMENT_ALL_BITS;
1717 612939546 : end_bit_plus1 = start + count;
1718 612939546 : last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1719 612939546 : elt = bitmap_list_find_element (head, first_index);
1720 :
1721 : /* If bitmap_list_find_element returns zero, the current is the closest block
1722 : to the result. Otherwise, just use bitmap_element_allocate to
1723 : ensure ELT is set; in the loop below, ELT == NULL means "insert
1724 : at the end of the bitmap". */
1725 612939546 : if (!elt)
1726 : {
1727 108394861 : elt = bitmap_element_allocate (head);
1728 108394861 : elt->indx = first_index;
1729 108394861 : bitmap_list_link_element (head, elt);
1730 : }
1731 :
1732 612939546 : gcc_checking_assert (elt->indx == first_index);
1733 612939546 : elt_prev = elt->prev;
1734 1264488130 : for (i = first_index; i <= last_index; i++)
1735 : {
1736 651548584 : unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS;
1737 651548584 : unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1738 :
1739 651548584 : unsigned int first_word_to_mod;
1740 651548584 : BITMAP_WORD first_mask;
1741 651548584 : unsigned int last_word_to_mod;
1742 651548584 : BITMAP_WORD last_mask;
1743 651548584 : unsigned int ix;
1744 :
1745 651548584 : if (!elt || elt->indx != i)
1746 38446409 : elt = bitmap_list_insert_element_after (head, elt_prev, i);
1747 :
1748 651548584 : if (elt_start_bit <= start)
1749 : {
1750 : /* The first bit to turn on is somewhere inside this
1751 : elt. */
1752 612939546 : first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1753 :
1754 : /* This mask should have 1s in all bits >= start position. */
1755 612939546 : first_mask =
1756 612939546 : (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1757 612939546 : first_mask = ~first_mask;
1758 : }
1759 : else
1760 : {
1761 : /* The first bit to turn on is below this start of this elt. */
1762 : first_word_to_mod = 0;
1763 : first_mask = ~(BITMAP_WORD) 0;
1764 : }
1765 :
1766 651548584 : if (elt_end_bit_plus1 <= end_bit_plus1)
1767 : {
1768 : /* The last bit to turn on is beyond this elt. */
1769 : last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
1770 : last_mask = ~(BITMAP_WORD) 0;
1771 : }
1772 : else
1773 : {
1774 : /* The last bit to turn on is inside to this elt. */
1775 608897440 : last_word_to_mod =
1776 608897440 : (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1777 :
1778 : /* The last mask should have 1s below the end bit. */
1779 608897440 : last_mask =
1780 608897440 : (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1;
1781 : }
1782 :
1783 651548584 : if (first_word_to_mod == last_word_to_mod)
1784 : {
1785 602516192 : BITMAP_WORD mask = first_mask & last_mask;
1786 602516192 : elt->bits[first_word_to_mod] |= mask;
1787 : }
1788 : else
1789 : {
1790 49032392 : elt->bits[first_word_to_mod] |= first_mask;
1791 49032392 : if (BITMAP_ELEMENT_WORDS > 2)
1792 : for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++)
1793 : elt->bits[ix] = ~(BITMAP_WORD) 0;
1794 49032392 : elt->bits[last_word_to_mod] |= last_mask;
1795 : }
1796 :
1797 651548584 : elt_prev = elt;
1798 651548584 : elt = elt->next;
1799 : }
1800 :
1801 612939546 : head->current = elt ? elt : elt_prev;
1802 612939546 : head->indx = head->current->indx;
1803 : }
1804 :
1805 : /* Clear COUNT bits from START in HEAD. */
1806 : void
1807 2383393358 : bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
1808 : {
1809 2383393358 : unsigned int first_index, end_bit_plus1, last_index;
1810 2383393358 : bitmap_element *elt;
1811 :
1812 2383393358 : gcc_checking_assert (!head->tree_form);
1813 :
1814 2383393358 : if (!count)
1815 : return;
1816 :
1817 2383392951 : if (count == 1)
1818 : {
1819 397186614 : bitmap_clear_bit (head, start);
1820 397186614 : return;
1821 : }
1822 :
1823 1986206337 : first_index = start / BITMAP_ELEMENT_ALL_BITS;
1824 1986206337 : end_bit_plus1 = start + count;
1825 1986206337 : last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1826 1986206337 : elt = bitmap_list_find_element (head, first_index);
1827 :
1828 : /* If bitmap_list_find_element returns zero, the current is the closest block
1829 : to the result. If the current is less than first index, find the
1830 : next one. Otherwise, just set elt to be current. */
1831 1986206337 : if (!elt)
1832 : {
1833 1343979531 : if (head->current)
1834 : {
1835 1297977024 : if (head->indx < first_index)
1836 : {
1837 860313328 : elt = head->current->next;
1838 860313328 : if (!elt)
1839 : return;
1840 : }
1841 : else
1842 : elt = head->current;
1843 : }
1844 : else
1845 : return;
1846 : }
1847 :
1848 2393060804 : while (elt && (elt->indx <= last_index))
1849 : {
1850 783990183 : bitmap_element * next_elt = elt->next;
1851 783990183 : unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
1852 783990183 : unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1853 :
1854 :
1855 783990183 : if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
1856 : /* Get rid of the entire elt and go to the next one. */
1857 48750856 : bitmap_list_unlink_element (head, elt);
1858 : else
1859 : {
1860 : /* Going to have to knock out some bits in this elt. */
1861 735239327 : unsigned int first_word_to_mod;
1862 735239327 : BITMAP_WORD first_mask;
1863 735239327 : unsigned int last_word_to_mod;
1864 735239327 : BITMAP_WORD last_mask;
1865 735239327 : unsigned int i;
1866 735239327 : bool clear = true;
1867 :
1868 735239327 : if (elt_start_bit <= start)
1869 : {
1870 : /* The first bit to turn off is somewhere inside this
1871 : elt. */
1872 640894621 : first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1873 :
1874 : /* This mask should have 1s in all bits >= start position. */
1875 640894621 : first_mask =
1876 640894621 : (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1877 640894621 : first_mask = ~first_mask;
1878 : }
1879 : else
1880 : {
1881 : /* The first bit to turn off is below this start of this elt. */
1882 : first_word_to_mod = 0;
1883 : first_mask = 0;
1884 : first_mask = ~first_mask;
1885 : }
1886 :
1887 735239327 : if (elt_end_bit_plus1 <= end_bit_plus1)
1888 : {
1889 : /* The last bit to turn off is beyond this elt. */
1890 : last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
1891 : last_mask = 0;
1892 : last_mask = ~last_mask;
1893 : }
1894 : else
1895 : {
1896 : /* The last bit to turn off is inside to this elt. */
1897 604807105 : last_word_to_mod =
1898 604807105 : (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1899 :
1900 : /* The last mask should have 1s below the end bit. */
1901 604807105 : last_mask =
1902 604807105 : (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
1903 : }
1904 :
1905 :
1906 735239327 : if (first_word_to_mod == last_word_to_mod)
1907 : {
1908 607716232 : BITMAP_WORD mask = first_mask & last_mask;
1909 607716232 : elt->bits[first_word_to_mod] &= ~mask;
1910 : }
1911 : else
1912 : {
1913 127523095 : elt->bits[first_word_to_mod] &= ~first_mask;
1914 127523095 : if (BITMAP_ELEMENT_WORDS > 2)
1915 : for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
1916 : elt->bits[i] = 0;
1917 127523095 : elt->bits[last_word_to_mod] &= ~last_mask;
1918 : }
1919 997547778 : for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1920 961673884 : if (elt->bits[i])
1921 : {
1922 : clear = false;
1923 : break;
1924 : }
1925 : /* Check to see if there are any bits left. */
1926 735239327 : if (clear)
1927 35873894 : bitmap_list_unlink_element (head, elt);
1928 : }
1929 : elt = next_elt;
1930 : }
1931 :
1932 1609070621 : if (elt)
1933 : {
1934 1326124264 : head->current = elt;
1935 1326124264 : head->indx = head->current->indx;
1936 : }
1937 : }
1938 :
1939 : /* A = ~A & B. */
1940 :
1941 : void
1942 0 : bitmap_compl_and_into (bitmap a, const_bitmap b)
1943 : {
1944 0 : bitmap_element *a_elt = a->first;
1945 0 : const bitmap_element *b_elt = b->first;
1946 0 : bitmap_element *a_prev = NULL;
1947 0 : bitmap_element *next;
1948 :
1949 0 : gcc_checking_assert (!a->tree_form && !b->tree_form);
1950 0 : gcc_assert (a != b);
1951 :
1952 0 : if (bitmap_empty_p (a))
1953 : {
1954 0 : bitmap_copy (a, b);
1955 0 : return;
1956 : }
1957 0 : if (bitmap_empty_p (b))
1958 : {
1959 0 : bitmap_clear (a);
1960 0 : return;
1961 : }
1962 :
1963 0 : while (a_elt || b_elt)
1964 : {
1965 0 : if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1966 : {
1967 : /* A is before B. Remove A */
1968 0 : next = a_elt->next;
1969 0 : a_prev = a_elt->prev;
1970 0 : bitmap_list_unlink_element (a, a_elt);
1971 0 : a_elt = next;
1972 : }
1973 0 : else if (!a_elt || b_elt->indx < a_elt->indx)
1974 : {
1975 : /* B is before A. Copy B. */
1976 0 : next = bitmap_list_insert_element_after (a, a_prev, b_elt->indx);
1977 0 : memcpy (next->bits, b_elt->bits, sizeof (next->bits));
1978 0 : a_prev = next;
1979 0 : b_elt = b_elt->next;
1980 : }
1981 : else
1982 : {
1983 : /* Matching elts, generate A = ~A & B. */
1984 : unsigned ix;
1985 : BITMAP_WORD ior = 0;
1986 :
1987 0 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1988 : {
1989 0 : BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1990 0 : BITMAP_WORD r = b_elt->bits[ix] ^ cleared;
1991 :
1992 0 : a_elt->bits[ix] = r;
1993 0 : ior |= r;
1994 : }
1995 0 : next = a_elt->next;
1996 0 : if (!ior)
1997 0 : bitmap_list_unlink_element (a, a_elt);
1998 : else
1999 : a_prev = a_elt;
2000 0 : a_elt = next;
2001 0 : b_elt = b_elt->next;
2002 : }
2003 : }
2004 0 : gcc_checking_assert (!a->current == !a->first
2005 : && (!a->current || a->indx == a->current->indx));
2006 : return;
2007 : }
2008 :
2009 :
2010 : /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
2011 : overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap
2012 : had already been changed; the new value of CHANGED is returned. */
2013 :
2014 : static inline bool
2015 7376957208 : bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
2016 : const bitmap_element *a_elt, const bitmap_element *b_elt,
2017 : bool changed)
2018 : {
2019 7376957208 : gcc_assert (a_elt || b_elt);
2020 :
2021 7376957208 : if (a_elt && b_elt && a_elt->indx == b_elt->indx)
2022 : {
2023 : /* Matching elts, generate A | B. */
2024 4222970457 : unsigned ix;
2025 :
2026 4222970457 : if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
2027 : {
2028 11063743062 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2029 : {
2030 7375828708 : BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
2031 7375828708 : if (r != dst_elt->bits[ix])
2032 : {
2033 1225884610 : dst_elt->bits[ix] = r;
2034 1225884610 : changed = true;
2035 : }
2036 : }
2037 : }
2038 : else
2039 : {
2040 933360896 : changed = true;
2041 534260246 : if (!dst_elt)
2042 135955453 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
2043 : a_elt->indx);
2044 : else
2045 399100650 : dst_elt->indx = a_elt->indx;
2046 1605168309 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2047 : {
2048 1070112206 : BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
2049 1070112206 : dst_elt->bits[ix] = r;
2050 : }
2051 : }
2052 : }
2053 : else
2054 : {
2055 : /* Copy a single element. */
2056 2918645273 : const bitmap_element *src;
2057 :
2058 3153986751 : if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
2059 : src = a_elt;
2060 : else
2061 191016228 : src = b_elt;
2062 :
2063 3109661501 : gcc_checking_assert (src);
2064 3153986751 : changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed);
2065 : }
2066 7376957208 : return changed;
2067 : }
2068 :
2069 :
2070 : /* DST = A | B. Return true if DST changes. */
2071 :
2072 : bool
2073 338159522 : bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b)
2074 : {
2075 338159522 : bitmap_element *dst_elt = dst->first;
2076 338159522 : const bitmap_element *a_elt = a->first;
2077 338159522 : const bitmap_element *b_elt = b->first;
2078 338159522 : bitmap_element *dst_prev = NULL;
2079 338159522 : bitmap_element **dst_prev_pnext = &dst->first;
2080 338159522 : bool changed = false;
2081 :
2082 338159522 : gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
2083 338159522 : gcc_assert (dst != a && dst != b);
2084 :
2085 943370305 : while (a_elt || b_elt)
2086 : {
2087 605210783 : changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed);
2088 :
2089 605210783 : if (a_elt && b_elt && a_elt->indx == b_elt->indx)
2090 : {
2091 210486071 : a_elt = a_elt->next;
2092 210486071 : b_elt = b_elt->next;
2093 : }
2094 : else
2095 : {
2096 394724712 : if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
2097 33426002 : a_elt = a_elt->next;
2098 361298710 : else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
2099 361298710 : b_elt = b_elt->next;
2100 : }
2101 :
2102 605210783 : dst_prev = *dst_prev_pnext;
2103 605210783 : dst_prev_pnext = &dst_prev->next;
2104 605210783 : dst_elt = *dst_prev_pnext;
2105 : }
2106 :
2107 338159522 : if (dst_elt)
2108 : {
2109 8122 : changed = true;
2110 : /* Ensure that dst->current is valid. */
2111 8122 : dst->current = dst->first;
2112 8122 : bitmap_elt_clear_from (dst, dst_elt);
2113 : }
2114 338159522 : gcc_checking_assert (!dst->current == !dst->first);
2115 338159522 : if (dst->current)
2116 336850921 : dst->indx = dst->current->indx;
2117 338159522 : return changed;
2118 : }
2119 :
2120 : /* A |= B. Return true if A changes. */
2121 :
2122 : bool
2123 4622287644 : bitmap_ior_into (bitmap a, const_bitmap b)
2124 : {
2125 4622287644 : bitmap_element *a_elt = a->first;
2126 4622287644 : const bitmap_element *b_elt = b->first;
2127 4622287644 : bitmap_element *a_prev = NULL;
2128 4622287644 : bitmap_element **a_prev_pnext = &a->first;
2129 4622287644 : bool changed = false;
2130 :
2131 4622287644 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2132 4622287644 : if (a == b)
2133 : return false;
2134 :
2135 11149506530 : while (b_elt)
2136 : {
2137 : /* If A lags behind B, just advance it. */
2138 6527223408 : if (!a_elt || a_elt->indx == b_elt->indx)
2139 : {
2140 5650570213 : changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
2141 5650570213 : b_elt = b_elt->next;
2142 : }
2143 876653195 : else if (a_elt->indx > b_elt->indx)
2144 : {
2145 101480662 : changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed);
2146 101480662 : b_elt = b_elt->next;
2147 : }
2148 :
2149 6527223408 : a_prev = *a_prev_pnext;
2150 6527223408 : a_prev_pnext = &a_prev->next;
2151 6527223408 : a_elt = *a_prev_pnext;
2152 : }
2153 :
2154 4622283122 : gcc_checking_assert (!a->current == !a->first);
2155 4622283122 : if (a->current)
2156 4307748631 : a->indx = a->current->indx;
2157 : return changed;
2158 : }
2159 :
2160 : /* A |= B. Return true if A changes. Free B (re-using its storage
2161 : for the result). */
2162 :
2163 : bool
2164 11724348 : bitmap_ior_into_and_free (bitmap a, bitmap *b_)
2165 : {
2166 11724348 : bitmap b = *b_;
2167 11724348 : bitmap_element *a_elt = a->first;
2168 11724348 : bitmap_element *b_elt = b->first;
2169 11724348 : bitmap_element *a_prev = NULL;
2170 11724348 : bitmap_element **a_prev_pnext = &a->first;
2171 11724348 : bool changed = false;
2172 :
2173 11724348 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2174 11724348 : gcc_assert (a->obstack == b->obstack);
2175 11724348 : if (a == b)
2176 : return false;
2177 :
2178 39078745 : while (b_elt)
2179 : {
2180 : /* If A lags behind B, just advance it. */
2181 27354397 : if (!a_elt || a_elt->indx == b_elt->indx)
2182 : {
2183 17086268 : changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
2184 17086268 : b_elt = b_elt->next;
2185 : }
2186 10268129 : else if (a_elt->indx > b_elt->indx)
2187 : {
2188 4590978 : bitmap_element *b_elt_next = b_elt->next;
2189 4590978 : bitmap_list_unlink_element (b, b_elt, false);
2190 4590978 : bitmap_list_insert_element_after (a, a_prev, b_elt->indx, b_elt);
2191 4590978 : b_elt = b_elt_next;
2192 : }
2193 :
2194 27354397 : a_prev = *a_prev_pnext;
2195 27354397 : a_prev_pnext = &a_prev->next;
2196 27354397 : a_elt = *a_prev_pnext;
2197 : }
2198 :
2199 11724348 : gcc_checking_assert (!a->current == !a->first);
2200 11724348 : if (a->current)
2201 11724348 : a->indx = a->current->indx;
2202 :
2203 11724348 : if (b->obstack)
2204 11724348 : BITMAP_FREE (*b_);
2205 : else
2206 0 : bitmap_clear (b);
2207 : return changed;
2208 : }
2209 :
2210 : /* DST = A ^ B */
2211 :
2212 : void
2213 0 : bitmap_xor (bitmap dst, const_bitmap a, const_bitmap b)
2214 : {
2215 0 : bitmap_element *dst_elt = dst->first;
2216 0 : const bitmap_element *a_elt = a->first;
2217 0 : const bitmap_element *b_elt = b->first;
2218 0 : bitmap_element *dst_prev = NULL;
2219 :
2220 0 : gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
2221 0 : gcc_assert (dst != a && dst != b);
2222 :
2223 0 : if (a == b)
2224 : {
2225 0 : bitmap_clear (dst);
2226 0 : return;
2227 : }
2228 :
2229 0 : while (a_elt || b_elt)
2230 : {
2231 0 : if (a_elt && b_elt && a_elt->indx == b_elt->indx)
2232 : {
2233 : /* Matching elts, generate A ^ B. */
2234 0 : unsigned ix;
2235 0 : BITMAP_WORD ior = 0;
2236 :
2237 0 : if (!dst_elt)
2238 0 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
2239 : a_elt->indx);
2240 : else
2241 0 : dst_elt->indx = a_elt->indx;
2242 0 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2243 : {
2244 0 : BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
2245 :
2246 0 : ior |= r;
2247 0 : dst_elt->bits[ix] = r;
2248 : }
2249 0 : a_elt = a_elt->next;
2250 0 : b_elt = b_elt->next;
2251 0 : if (ior)
2252 : {
2253 0 : dst_prev = dst_elt;
2254 0 : dst_elt = dst_elt->next;
2255 : }
2256 : }
2257 : else
2258 : {
2259 : /* Copy a single element. */
2260 0 : const bitmap_element *src;
2261 :
2262 0 : if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
2263 : {
2264 0 : src = a_elt;
2265 0 : a_elt = a_elt->next;
2266 : }
2267 : else
2268 : {
2269 0 : src = b_elt;
2270 0 : b_elt = b_elt->next;
2271 : }
2272 :
2273 0 : if (!dst_elt)
2274 0 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
2275 0 : src->indx);
2276 : else
2277 0 : dst_elt->indx = src->indx;
2278 0 : memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
2279 0 : dst_prev = dst_elt;
2280 0 : dst_elt = dst_elt->next;
2281 : }
2282 : }
2283 : /* Ensure that dst->current is valid. */
2284 0 : dst->current = dst->first;
2285 0 : bitmap_elt_clear_from (dst, dst_elt);
2286 0 : gcc_checking_assert (!dst->current == !dst->first);
2287 0 : if (dst->current)
2288 0 : dst->indx = dst->current->indx;
2289 : }
2290 :
2291 : /* A ^= B */
2292 :
2293 : void
2294 0 : bitmap_xor_into (bitmap a, const_bitmap b)
2295 : {
2296 0 : bitmap_element *a_elt = a->first;
2297 0 : const bitmap_element *b_elt = b->first;
2298 0 : bitmap_element *a_prev = NULL;
2299 :
2300 0 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2301 :
2302 0 : if (a == b)
2303 : {
2304 0 : bitmap_clear (a);
2305 0 : return;
2306 : }
2307 :
2308 0 : while (b_elt)
2309 : {
2310 0 : if (!a_elt || b_elt->indx < a_elt->indx)
2311 : {
2312 : /* Copy b_elt. */
2313 0 : bitmap_element *dst = bitmap_list_insert_element_after (a, a_prev,
2314 0 : b_elt->indx);
2315 0 : memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
2316 0 : a_prev = dst;
2317 0 : b_elt = b_elt->next;
2318 0 : }
2319 0 : else if (a_elt->indx < b_elt->indx)
2320 : {
2321 0 : a_prev = a_elt;
2322 0 : a_elt = a_elt->next;
2323 : }
2324 : else
2325 : {
2326 : /* Matching elts, generate A ^= B. */
2327 0 : unsigned ix;
2328 0 : BITMAP_WORD ior = 0;
2329 0 : bitmap_element *next = a_elt->next;
2330 :
2331 0 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2332 : {
2333 0 : BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
2334 :
2335 0 : ior |= r;
2336 0 : a_elt->bits[ix] = r;
2337 : }
2338 0 : b_elt = b_elt->next;
2339 0 : if (ior)
2340 : a_prev = a_elt;
2341 : else
2342 0 : bitmap_list_unlink_element (a, a_elt);
2343 : a_elt = next;
2344 : }
2345 : }
2346 0 : gcc_checking_assert (!a->current == !a->first);
2347 0 : if (a->current)
2348 0 : a->indx = a->current->indx;
2349 : }
2350 :
2351 : /* Return true if two bitmaps are identical.
2352 : We do not bother with a check for pointer equality, as that never
2353 : occurs in practice. */
2354 :
2355 : bool
2356 495606782 : bitmap_equal_p (const_bitmap a, const_bitmap b)
2357 : {
2358 495606782 : const bitmap_element *a_elt;
2359 495606782 : const bitmap_element *b_elt;
2360 495606782 : unsigned ix;
2361 :
2362 495606782 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2363 :
2364 495606782 : for (a_elt = a->first, b_elt = b->first;
2365 1021506673 : a_elt && b_elt;
2366 525899891 : a_elt = a_elt->next, b_elt = b_elt->next)
2367 : {
2368 641177677 : if (a_elt->indx != b_elt->indx)
2369 : return false;
2370 1666604012 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2371 1140704121 : if (a_elt->bits[ix] != b_elt->bits[ix])
2372 : return false;
2373 : }
2374 380328996 : return !a_elt && !b_elt;
2375 : }
2376 :
2377 : /* Return true if A AND B is not empty. */
2378 :
2379 : bool
2380 409379148 : bitmap_intersect_p (const_bitmap a, const_bitmap b)
2381 : {
2382 409379148 : const bitmap_element *a_elt;
2383 409379148 : const bitmap_element *b_elt;
2384 409379148 : unsigned ix;
2385 :
2386 409379148 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2387 :
2388 409379148 : for (a_elt = a->first, b_elt = b->first;
2389 850474799 : a_elt && b_elt;)
2390 : {
2391 542802057 : if (a_elt->indx < b_elt->indx)
2392 214082247 : a_elt = a_elt->next;
2393 328719810 : else if (b_elt->indx < a_elt->indx)
2394 84917919 : b_elt = b_elt->next;
2395 : else
2396 : {
2397 563724996 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2398 421629511 : if (a_elt->bits[ix] & b_elt->bits[ix])
2399 : return true;
2400 142095485 : a_elt = a_elt->next;
2401 142095485 : b_elt = b_elt->next;
2402 : }
2403 : }
2404 : return false;
2405 : }
2406 :
2407 : /* Return true if A AND NOT B is not empty. */
2408 :
2409 : bool
2410 172 : bitmap_intersect_compl_p (const_bitmap a, const_bitmap b)
2411 : {
2412 172 : const bitmap_element *a_elt;
2413 172 : const bitmap_element *b_elt;
2414 172 : unsigned ix;
2415 :
2416 172 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2417 :
2418 172 : for (a_elt = a->first, b_elt = b->first;
2419 311 : a_elt && b_elt;)
2420 : {
2421 172 : if (a_elt->indx < b_elt->indx)
2422 : return true;
2423 172 : else if (b_elt->indx < a_elt->indx)
2424 0 : b_elt = b_elt->next;
2425 : else
2426 : {
2427 450 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2428 311 : if (a_elt->bits[ix] & ~b_elt->bits[ix])
2429 : return true;
2430 139 : a_elt = a_elt->next;
2431 139 : b_elt = b_elt->next;
2432 : }
2433 : }
2434 : return a_elt != NULL;
2435 : }
2436 :
2437 :
2438 : /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */
2439 :
2440 : bool
2441 858607570 : bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill)
2442 : {
2443 858607570 : bool changed = false;
2444 :
2445 858607570 : bitmap_element *dst_elt = dst->first;
2446 858607570 : const bitmap_element *a_elt = a->first;
2447 858607570 : const bitmap_element *b_elt = b->first;
2448 858607570 : const bitmap_element *kill_elt = kill->first;
2449 858607570 : bitmap_element *dst_prev = NULL;
2450 858607570 : bitmap_element **dst_prev_pnext = &dst->first;
2451 :
2452 858607570 : gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form
2453 : && !kill->tree_form);
2454 858607570 : gcc_assert (dst != a && dst != b && dst != kill);
2455 :
2456 : /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
2457 858607570 : if (b == kill || bitmap_empty_p (b))
2458 : {
2459 65307555 : changed = !bitmap_equal_p (dst, a);
2460 65307555 : if (changed)
2461 4050765 : bitmap_copy (dst, a);
2462 65307555 : return changed;
2463 : }
2464 793300015 : if (bitmap_empty_p (kill))
2465 287857196 : return bitmap_ior (dst, a, b);
2466 505442819 : if (bitmap_empty_p (a))
2467 36412340 : return bitmap_and_compl (dst, b, kill);
2468 :
2469 1558957803 : while (a_elt || b_elt)
2470 : {
2471 1089927324 : bool new_element = false;
2472 :
2473 1089927324 : if (b_elt)
2474 1086592413 : while (kill_elt && kill_elt->indx < b_elt->indx)
2475 25786833 : kill_elt = kill_elt->next;
2476 :
2477 1089927324 : if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
2478 600805200 : && (!a_elt || a_elt->indx >= b_elt->indx))
2479 : {
2480 594694626 : bitmap_element tmp_elt;
2481 594694626 : unsigned ix;
2482 :
2483 594694626 : BITMAP_WORD ior = 0;
2484 594694626 : tmp_elt.indx = b_elt->indx;
2485 1784083878 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2486 : {
2487 1189389252 : BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix];
2488 1189389252 : ior |= r;
2489 1189389252 : tmp_elt.bits[ix] = r;
2490 : }
2491 :
2492 594694626 : if (ior)
2493 : {
2494 552080006 : changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
2495 : a_elt, &tmp_elt, changed);
2496 552080006 : new_element = true;
2497 552080006 : if (a_elt && a_elt->indx == b_elt->indx)
2498 481961845 : a_elt = a_elt->next;
2499 : }
2500 :
2501 594694626 : b_elt = b_elt->next;
2502 594694626 : kill_elt = kill_elt->next;
2503 : }
2504 : else
2505 : {
2506 495232698 : changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
2507 : a_elt, b_elt, changed);
2508 495232698 : new_element = true;
2509 :
2510 495232698 : if (a_elt && b_elt && a_elt->indx == b_elt->indx)
2511 : {
2512 137579035 : a_elt = a_elt->next;
2513 137579035 : b_elt = b_elt->next;
2514 : }
2515 : else
2516 : {
2517 357653663 : if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
2518 50070842 : a_elt = a_elt->next;
2519 307582821 : else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
2520 307582821 : b_elt = b_elt->next;
2521 : }
2522 : }
2523 :
2524 1089927324 : if (new_element)
2525 : {
2526 1047312704 : dst_prev = *dst_prev_pnext;
2527 1047312704 : dst_prev_pnext = &dst_prev->next;
2528 1047312704 : dst_elt = *dst_prev_pnext;
2529 : }
2530 : }
2531 :
2532 469030479 : if (dst_elt)
2533 : {
2534 3234 : changed = true;
2535 : /* Ensure that dst->current is valid. */
2536 3234 : dst->current = dst->first;
2537 3234 : bitmap_elt_clear_from (dst, dst_elt);
2538 : }
2539 469030479 : gcc_checking_assert (!dst->current == !dst->first);
2540 469030479 : if (dst->current)
2541 469030479 : dst->indx = dst->current->indx;
2542 :
2543 : return changed;
2544 : }
2545 :
2546 : /* A |= (B & ~C). Return true if A changes. */
2547 :
2548 : bool
2549 53750524 : bitmap_ior_and_compl_into (bitmap a, const_bitmap b, const_bitmap c)
2550 : {
2551 53750524 : bitmap_element *a_elt = a->first;
2552 53750524 : const bitmap_element *b_elt = b->first;
2553 53750524 : const bitmap_element *c_elt = c->first;
2554 53750524 : bitmap_element and_elt;
2555 53750524 : bitmap_element *a_prev = NULL;
2556 53750524 : bitmap_element **a_prev_pnext = &a->first;
2557 53750524 : bool changed = false;
2558 53750524 : unsigned ix;
2559 :
2560 53750524 : gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form);
2561 :
2562 53750524 : if (a == b)
2563 : return false;
2564 53442114 : if (bitmap_empty_p (c))
2565 11583014 : return bitmap_ior_into (a, b);
2566 41859100 : else if (bitmap_empty_p (a))
2567 21403038 : return bitmap_and_compl (a, b, c);
2568 :
2569 20456062 : and_elt.indx = -1;
2570 67873596 : while (b_elt)
2571 : {
2572 : /* Advance C. */
2573 59695027 : while (c_elt && c_elt->indx < b_elt->indx)
2574 12277493 : c_elt = c_elt->next;
2575 :
2576 47417534 : const bitmap_element *and_elt_ptr;
2577 47417534 : if (c_elt && c_elt->indx == b_elt->indx)
2578 : {
2579 13395605 : BITMAP_WORD overall = 0;
2580 13395605 : and_elt_ptr = &and_elt;
2581 13395605 : and_elt.indx = b_elt->indx;
2582 40186815 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2583 : {
2584 26791210 : and_elt.bits[ix] = b_elt->bits[ix] & ~c_elt->bits[ix];
2585 26791210 : overall |= and_elt.bits[ix];
2586 : }
2587 13395605 : if (!overall)
2588 : {
2589 1261490 : b_elt = b_elt->next;
2590 1261490 : continue;
2591 : }
2592 : }
2593 : else
2594 : and_elt_ptr = b_elt;
2595 :
2596 46156044 : b_elt = b_elt->next;
2597 :
2598 : /* Now find a place to insert AND_ELT. */
2599 53326730 : do
2600 : {
2601 53326730 : ix = a_elt ? a_elt->indx : and_elt_ptr->indx;
2602 53326730 : if (ix == and_elt_ptr->indx)
2603 44853863 : changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt,
2604 : and_elt_ptr, changed);
2605 8472867 : else if (ix > and_elt_ptr->indx)
2606 1302181 : changed = bitmap_elt_copy (a, NULL, a_prev, and_elt_ptr, changed);
2607 :
2608 53326730 : a_prev = *a_prev_pnext;
2609 53326730 : a_prev_pnext = &a_prev->next;
2610 53326730 : a_elt = *a_prev_pnext;
2611 :
2612 : /* If A lagged behind B/C, we advanced it so loop once more. */
2613 : }
2614 53326730 : while (ix < and_elt_ptr->indx);
2615 : }
2616 :
2617 20456062 : gcc_checking_assert (!a->current == !a->first);
2618 20456062 : if (a->current)
2619 20456062 : a->indx = a->current->indx;
2620 : return changed;
2621 : }
2622 :
2623 : /* A |= (B & C). Return true if A changes. */
2624 :
2625 : bool
2626 13294847 : bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c)
2627 : {
2628 13294847 : bitmap_element *a_elt = a->first;
2629 13294847 : const bitmap_element *b_elt = b->first;
2630 13294847 : const bitmap_element *c_elt = c->first;
2631 13294847 : bitmap_element and_elt;
2632 13294847 : bitmap_element *a_prev = NULL;
2633 13294847 : bitmap_element **a_prev_pnext = &a->first;
2634 13294847 : bool changed = false;
2635 13294847 : unsigned ix;
2636 :
2637 13294847 : gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form);
2638 :
2639 13294847 : if (b == c)
2640 0 : return bitmap_ior_into (a, b);
2641 13294847 : if (bitmap_empty_p (b) || bitmap_empty_p (c))
2642 : return false;
2643 :
2644 : and_elt.indx = -1;
2645 30046079 : while (b_elt && c_elt)
2646 : {
2647 : BITMAP_WORD overall;
2648 :
2649 : /* Find a common item of B and C. */
2650 23159627 : while (b_elt->indx != c_elt->indx)
2651 : {
2652 6408393 : if (b_elt->indx < c_elt->indx)
2653 : {
2654 690761 : b_elt = b_elt->next;
2655 690761 : if (!b_elt)
2656 210511 : goto done;
2657 : }
2658 : else
2659 : {
2660 5717632 : c_elt = c_elt->next;
2661 5717632 : if (!c_elt)
2662 189432 : goto done;
2663 : }
2664 : }
2665 :
2666 16751234 : overall = 0;
2667 16751234 : and_elt.indx = b_elt->indx;
2668 50253702 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2669 : {
2670 33502468 : and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix];
2671 33502468 : overall |= and_elt.bits[ix];
2672 : }
2673 :
2674 16751234 : b_elt = b_elt->next;
2675 16751234 : c_elt = c_elt->next;
2676 16751234 : if (!overall)
2677 4775656 : continue;
2678 :
2679 : /* Now find a place to insert AND_ELT. */
2680 11975695 : do
2681 : {
2682 11975695 : ix = a_elt ? a_elt->indx : and_elt.indx;
2683 11975695 : if (ix == and_elt.indx)
2684 11923377 : changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed);
2685 52318 : else if (ix > and_elt.indx)
2686 52201 : changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed);
2687 :
2688 11975695 : a_prev = *a_prev_pnext;
2689 11975695 : a_prev_pnext = &a_prev->next;
2690 11975695 : a_elt = *a_prev_pnext;
2691 :
2692 : /* If A lagged behind B/C, we advanced it so loop once more. */
2693 : }
2694 11975695 : while (ix < and_elt.indx);
2695 : }
2696 :
2697 12894902 : done:
2698 13294845 : gcc_checking_assert (!a->current == !a->first);
2699 13294845 : if (a->current)
2700 10355083 : a->indx = a->current->indx;
2701 : return changed;
2702 : }
2703 :
2704 : /* Compute hash of bitmap (for purposes of hashing). */
2705 :
2706 : hashval_t
2707 266904804 : bitmap_hash (const_bitmap head)
2708 : {
2709 266904804 : const bitmap_element *ptr;
2710 266904804 : BITMAP_WORD hash = 0;
2711 266904804 : int ix;
2712 :
2713 266904804 : gcc_checking_assert (!head->tree_form);
2714 :
2715 609466479 : for (ptr = head->first; ptr; ptr = ptr->next)
2716 : {
2717 342561675 : hash ^= ptr->indx;
2718 1027685025 : for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
2719 685123350 : hash ^= ptr->bits[ix];
2720 : }
2721 266904804 : return iterative_hash (&hash, sizeof (hash), 0);
2722 : }
2723 :
2724 :
2725 : /* Function to obtain a vector of bitmap elements in bit order from
2726 : HEAD in tree view. */
2727 :
2728 : static void
2729 169 : bitmap_tree_to_vec (vec<bitmap_element *> &elts, const_bitmap head)
2730 : {
2731 169 : gcc_checking_assert (head->tree_form);
2732 169 : auto_vec<bitmap_element *, 32> stack;
2733 169 : bitmap_element *e = head->first;
2734 169 : while (true)
2735 : {
2736 507 : while (e != NULL)
2737 : {
2738 169 : stack.safe_push (e);
2739 169 : e = e->prev;
2740 : }
2741 507 : if (stack.is_empty ())
2742 : break;
2743 :
2744 169 : e = stack.pop ();
2745 169 : elts.safe_push (e);
2746 169 : e = e->next;
2747 : }
2748 169 : }
2749 :
2750 : /* Debugging function to print out the contents of a bitmap element. */
2751 :
2752 : DEBUG_FUNCTION void
2753 66 : debug_bitmap_elt_file (FILE *file, const bitmap_element *ptr)
2754 : {
2755 66 : unsigned int i, j, col = 26;
2756 :
2757 66 : fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
2758 : " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
2759 66 : (const void*) ptr, (const void*) ptr->next,
2760 66 : (const void*) ptr->prev, ptr->indx);
2761 :
2762 264 : for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
2763 8580 : for (j = 0; j < BITMAP_WORD_BITS; j++)
2764 8448 : if ((ptr->bits[i] >> j) & 1)
2765 : {
2766 572 : if (col > 70)
2767 : {
2768 5 : fprintf (file, "\n\t\t\t");
2769 5 : col = 24;
2770 : }
2771 :
2772 572 : fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
2773 572 : + i * BITMAP_WORD_BITS + j));
2774 572 : col += 4;
2775 : }
2776 :
2777 66 : fprintf (file, " }\n");
2778 66 : }
2779 :
2780 : /* Debugging function to print out the contents of a bitmap. */
2781 :
2782 : DEBUG_FUNCTION void
2783 66 : debug_bitmap_file (FILE *file, const_bitmap head)
2784 : {
2785 66 : const bitmap_element *ptr;
2786 :
2787 66 : fprintf (file, "\nfirst = " HOST_PTR_PRINTF
2788 : " current = " HOST_PTR_PRINTF " indx = %u\n",
2789 66 : (void *) head->first, (void *) head->current, head->indx);
2790 :
2791 66 : if (head->tree_form)
2792 : {
2793 0 : auto_vec<bitmap_element *, 32> elts;
2794 0 : bitmap_tree_to_vec (elts, head);
2795 0 : for (unsigned i = 0; i < elts.length (); ++i)
2796 0 : debug_bitmap_elt_file (file, elts[i]);
2797 0 : }
2798 : else
2799 132 : for (ptr = head->first; ptr; ptr = ptr->next)
2800 66 : debug_bitmap_elt_file (file, ptr);
2801 66 : }
2802 :
2803 : /* Function to be called from the debugger to print the contents
2804 : of a bitmap. */
2805 :
2806 : DEBUG_FUNCTION void
2807 0 : debug_bitmap (const_bitmap head)
2808 : {
2809 0 : debug_bitmap_file (stderr, head);
2810 0 : }
2811 :
2812 : /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
2813 : it does not print anything but the bits. */
2814 :
2815 : DEBUG_FUNCTION void
2816 2582 : bitmap_print (FILE *file, const_bitmap head, const char *prefix,
2817 : const char *suffix)
2818 : {
2819 2582 : const char *comma = "";
2820 2582 : unsigned i;
2821 :
2822 2582 : fputs (prefix, file);
2823 2582 : if (head->tree_form)
2824 : {
2825 169 : auto_vec<bitmap_element *, 32> elts;
2826 169 : bitmap_tree_to_vec (elts, head);
2827 338 : for (i = 0; i < elts.length (); ++i)
2828 507 : for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ++ix)
2829 : {
2830 338 : BITMAP_WORD word = elts[i]->bits[ix];
2831 21970 : for (unsigned bit = 0; bit != BITMAP_WORD_BITS; ++bit)
2832 21632 : if (word & ((BITMAP_WORD)1 << bit))
2833 : {
2834 588 : fprintf (file, "%s%d", comma,
2835 : (bit + BITMAP_WORD_BITS * ix
2836 294 : + elts[i]->indx * BITMAP_ELEMENT_ALL_BITS));
2837 294 : comma = ", ";
2838 : }
2839 : }
2840 169 : }
2841 : else
2842 : {
2843 2413 : bitmap_iterator bi;
2844 23027 : EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
2845 : {
2846 20614 : fprintf (file, "%s%d", comma, i);
2847 20614 : comma = ", ";
2848 : }
2849 : }
2850 2582 : fputs (suffix, file);
2851 2582 : }
2852 :
2853 : /* Output per-bitmap memory usage statistics. */
2854 : void
2855 0 : dump_bitmap_statistics (void)
2856 : {
2857 0 : if (!GATHER_STATISTICS)
2858 0 : return;
2859 :
2860 : bitmap_mem_desc.dump (BITMAP_ORIGIN);
2861 : }
2862 :
2863 : DEBUG_FUNCTION void
2864 0 : debug (const bitmap_head &ref)
2865 : {
2866 0 : dump_bitmap (stderr, &ref);
2867 0 : }
2868 :
2869 : DEBUG_FUNCTION void
2870 0 : debug (const bitmap_head *ptr)
2871 : {
2872 0 : if (ptr)
2873 0 : debug (*ptr);
2874 : else
2875 0 : fprintf (stderr, "<nil>\n");
2876 0 : }
2877 :
2878 : DEBUG_FUNCTION void
2879 0 : debug (const auto_bitmap &ref)
2880 : {
2881 0 : debug ((const bitmap_head &) ref);
2882 0 : }
2883 :
2884 : DEBUG_FUNCTION void
2885 0 : debug (const auto_bitmap *ptr)
2886 : {
2887 0 : debug ((const bitmap_head *) ptr);
2888 0 : }
2889 :
2890 : void
2891 0 : bitmap_head::dump ()
2892 : {
2893 0 : debug (this);
2894 0 : }
2895 :
2896 : #if CHECKING_P
2897 :
2898 : namespace selftest {
2899 :
2900 : /* Selftests for bitmaps. */
2901 :
2902 : /* Freshly-created bitmaps ought to be empty. */
2903 :
2904 : static void
2905 4 : test_gc_alloc ()
2906 : {
2907 4 : bitmap b = bitmap_gc_alloc ();
2908 4 : ASSERT_TRUE (bitmap_empty_p (b));
2909 4 : }
2910 :
2911 : /* Verify bitmap_set_range. */
2912 :
2913 : static void
2914 4 : test_set_range ()
2915 : {
2916 4 : bitmap b = bitmap_gc_alloc ();
2917 4 : ASSERT_TRUE (bitmap_empty_p (b));
2918 :
2919 4 : bitmap_set_range (b, 7, 5);
2920 4 : ASSERT_FALSE (bitmap_empty_p (b));
2921 4 : ASSERT_EQ (5, bitmap_count_bits (b));
2922 :
2923 : /* Verify bitmap_bit_p at the boundaries. */
2924 4 : ASSERT_FALSE (bitmap_bit_p (b, 6));
2925 4 : ASSERT_TRUE (bitmap_bit_p (b, 7));
2926 4 : ASSERT_TRUE (bitmap_bit_p (b, 11));
2927 4 : ASSERT_FALSE (bitmap_bit_p (b, 12));
2928 4 : }
2929 :
2930 : /* Verify splitting a range into two pieces using bitmap_clear_bit. */
2931 :
2932 : static void
2933 4 : test_clear_bit_in_middle ()
2934 : {
2935 4 : bitmap b = bitmap_gc_alloc ();
2936 :
2937 : /* Set b to [100..200]. */
2938 4 : bitmap_set_range (b, 100, 100);
2939 4 : ASSERT_EQ (100, bitmap_count_bits (b));
2940 :
2941 : /* Clear a bit in the middle. */
2942 4 : bool changed = bitmap_clear_bit (b, 150);
2943 4 : ASSERT_TRUE (changed);
2944 4 : ASSERT_EQ (99, bitmap_count_bits (b));
2945 4 : ASSERT_TRUE (bitmap_bit_p (b, 149));
2946 4 : ASSERT_FALSE (bitmap_bit_p (b, 150));
2947 4 : ASSERT_TRUE (bitmap_bit_p (b, 151));
2948 4 : }
2949 :
2950 : /* Verify bitmap_copy. */
2951 :
2952 : static void
2953 4 : test_copying ()
2954 : {
2955 4 : bitmap src = bitmap_gc_alloc ();
2956 4 : bitmap_set_range (src, 40, 10);
2957 :
2958 4 : bitmap dst = bitmap_gc_alloc ();
2959 4 : ASSERT_FALSE (bitmap_equal_p (src, dst));
2960 4 : bitmap_copy (dst, src);
2961 4 : ASSERT_TRUE (bitmap_equal_p (src, dst));
2962 :
2963 : /* Verify that we can make them unequal again... */
2964 4 : bitmap_set_range (src, 70, 5);
2965 4 : ASSERT_FALSE (bitmap_equal_p (src, dst));
2966 :
2967 : /* ...and that changing src after the copy didn't affect
2968 : the other: */
2969 4 : ASSERT_FALSE (bitmap_bit_p (dst, 70));
2970 4 : }
2971 :
2972 : /* Verify bitmap_single_bit_set_p. */
2973 :
2974 : static void
2975 4 : test_bitmap_single_bit_set_p ()
2976 : {
2977 4 : bitmap b = bitmap_gc_alloc ();
2978 :
2979 4 : ASSERT_FALSE (bitmap_single_bit_set_p (b));
2980 :
2981 4 : bitmap_set_range (b, 42, 1);
2982 4 : ASSERT_TRUE (bitmap_single_bit_set_p (b));
2983 4 : ASSERT_EQ (42, bitmap_first_set_bit (b));
2984 :
2985 4 : bitmap_set_range (b, 1066, 1);
2986 4 : ASSERT_FALSE (bitmap_single_bit_set_p (b));
2987 4 : ASSERT_EQ (42, bitmap_first_set_bit (b));
2988 :
2989 4 : bitmap_clear_range (b, 0, 100);
2990 4 : ASSERT_TRUE (bitmap_single_bit_set_p (b));
2991 4 : ASSERT_EQ (1066, bitmap_first_set_bit (b));
2992 4 : }
2993 :
2994 : /* Verify accessing aligned bit chunks works as expected. */
2995 :
2996 : static void
2997 12 : test_aligned_chunk (unsigned num_bits)
2998 : {
2999 12 : bitmap b = bitmap_gc_alloc ();
3000 12 : int limit = 2 ^ num_bits;
3001 :
3002 12 : int index = 3;
3003 76 : for (int x = 0; x < limit; x++)
3004 : {
3005 64 : bitmap_set_aligned_chunk (b, index, num_bits, (BITMAP_WORD) x);
3006 64 : ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index, num_bits) == x);
3007 64 : ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index + 1,
3008 : num_bits) == 0);
3009 64 : ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index - 1,
3010 : num_bits) == 0);
3011 64 : index += 3;
3012 : }
3013 : index = 3;
3014 76 : for (int x = 0; x < limit ; x++)
3015 : {
3016 64 : ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index, num_bits) == x);
3017 64 : index += 3;
3018 : }
3019 12 : }
3020 :
3021 : /* Run all of the selftests within this file. */
3022 :
3023 : void
3024 4 : bitmap_cc_tests ()
3025 : {
3026 4 : test_gc_alloc ();
3027 4 : test_set_range ();
3028 4 : test_clear_bit_in_middle ();
3029 4 : test_copying ();
3030 4 : test_bitmap_single_bit_set_p ();
3031 : /* Test 2, 4 and 8 bit aligned chunks. */
3032 4 : test_aligned_chunk (2);
3033 4 : test_aligned_chunk (4);
3034 4 : test_aligned_chunk (8);
3035 4 : }
3036 :
3037 : } // namespace selftest
3038 : #endif /* CHECKING_P */
3039 :
3040 : #include "gt-bitmap.h"
|
