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