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 837012613 : bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
79 : {
80 837012613 : bitmap_obstack *bit_obstack = head->obstack;
81 :
82 837012613 : if (GATHER_STATISTICS)
83 : release_overhead (head, sizeof (bitmap_element), false);
84 :
85 837012613 : elt->next = NULL;
86 837012613 : elt->indx = -1;
87 837012613 : if (bit_obstack)
88 : {
89 833773324 : elt->prev = bit_obstack->elements;
90 833773324 : bit_obstack->elements = elt;
91 : }
92 : else
93 : {
94 3239289 : elt->prev = bitmap_ggc_free;
95 3239289 : 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 13785378216 : bitmap_element_allocate (bitmap head)
103 : {
104 13785378216 : bitmap_element *element;
105 13785378216 : bitmap_obstack *bit_obstack = head->obstack;
106 :
107 13785378216 : if (bit_obstack)
108 : {
109 13646879220 : element = bit_obstack->elements;
110 :
111 13646879220 : if (element)
112 : /* Use up the inner list first before looking at the next
113 : element of the outer list. */
114 10308507556 : if (element->next)
115 : {
116 2963895549 : bit_obstack->elements = element->next;
117 2963895549 : bit_obstack->elements->prev = element->prev;
118 : }
119 : else
120 : /* Inner list was just a singleton. */
121 7344612007 : bit_obstack->elements = element->prev;
122 : else
123 3338371664 : element = XOBNEW (&bit_obstack->obstack, bitmap_element);
124 : }
125 : else
126 : {
127 138498996 : element = bitmap_ggc_free;
128 138498996 : if (element)
129 : /* Use up the inner list first before looking at the next
130 : element of the outer list. */
131 113436113 : if (element->next)
132 : {
133 14070155 : bitmap_ggc_free = element->next;
134 14070155 : bitmap_ggc_free->prev = element->prev;
135 : }
136 : else
137 : /* Inner list was just a singleton. */
138 99365958 : bitmap_ggc_free = element->prev;
139 : else
140 25062883 : element = ggc_alloc<bitmap_element> ();
141 : }
142 :
143 13785378216 : if (GATHER_STATISTICS)
144 : register_overhead (head, sizeof (bitmap_element));
145 :
146 13785378216 : memset (element->bits, 0, sizeof (element->bits));
147 :
148 13785378216 : 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 7314230314 : bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
156 : {
157 7314230314 : bitmap_element *prev;
158 7314230314 : bitmap_obstack *bit_obstack = head->obstack;
159 :
160 7314230314 : if (!elt)
161 : return;
162 :
163 6921635657 : if (head->tree_form)
164 53884301 : elt = bitmap_tree_listify_from (head, elt);
165 :
166 6921635657 : 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 6921635657 : prev = elt->prev;
175 6921635657 : if (prev)
176 : {
177 122797968 : prev->next = NULL;
178 122797968 : if (head->current->indx > prev->indx)
179 : {
180 492605 : head->current = prev;
181 492605 : head->indx = prev->indx;
182 : }
183 : }
184 : else
185 : {
186 6798837689 : head->first = NULL;
187 6798837689 : head->current = NULL;
188 6798837689 : head->indx = 0;
189 : }
190 :
191 : /* Put the entire list onto the freelist in one operation. */
192 6921635657 : if (bit_obstack)
193 : {
194 6820449919 : elt->prev = bit_obstack->elements;
195 6820449919 : bit_obstack->elements = elt;
196 : }
197 : else
198 : {
199 101185738 : elt->prev = bitmap_ggc_free;
200 101185738 : 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 7432864491 : bitmap_list_link_element (bitmap head, bitmap_element *element)
213 : {
214 7432864491 : unsigned int indx = element->indx;
215 7432864491 : bitmap_element *ptr;
216 :
217 7432864491 : gcc_checking_assert (!head->tree_form);
218 :
219 : /* If this is the first and only element, set it in. */
220 7432864491 : if (head->first == 0)
221 : {
222 5926529261 : element->next = element->prev = 0;
223 5926529261 : 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 1506335230 : else if (indx < head->indx)
229 : {
230 518388533 : for (ptr = head->current;
231 518388533 : ptr->prev != 0 && ptr->prev->indx > indx;
232 : ptr = ptr->prev)
233 : ;
234 :
235 518388533 : if (ptr->prev)
236 128335132 : ptr->prev->next = element;
237 : else
238 390053401 : head->first = element;
239 :
240 518388533 : element->prev = ptr->prev;
241 518388533 : element->next = ptr;
242 518388533 : ptr->prev = element;
243 : }
244 :
245 : /* Otherwise, it must go someplace after the current element. */
246 : else
247 : {
248 987946697 : for (ptr = head->current;
249 987946697 : ptr->next != 0 && ptr->next->indx < indx;
250 : ptr = ptr->next)
251 : ;
252 :
253 987946697 : if (ptr->next)
254 56624880 : ptr->next->prev = element;
255 :
256 987946697 : element->next = ptr->next;
257 987946697 : element->prev = ptr;
258 987946697 : ptr->next = element;
259 : }
260 :
261 : /* Set up so this is the first element searched. */
262 7432864491 : head->current = element;
263 7432864491 : head->indx = indx;
264 7432864491 : }
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 735245585 : bitmap_list_unlink_element (bitmap head, bitmap_element *element,
271 : bool to_freelist = true)
272 : {
273 735245585 : bitmap_element *next = element->next;
274 735245585 : bitmap_element *prev = element->prev;
275 :
276 735245585 : gcc_checking_assert (!head->tree_form);
277 :
278 735245585 : if (prev)
279 346580232 : prev->next = next;
280 :
281 735245585 : if (next)
282 260027430 : next->prev = prev;
283 :
284 735245585 : if (head->first == element)
285 388665353 : 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 735245585 : if (head->current == element)
290 : {
291 617851088 : head->current = next != 0 ? next : prev;
292 617851088 : if (head->current)
293 342690949 : head->indx = head->current->indx;
294 : else
295 275160139 : head->indx = 0;
296 : }
297 :
298 735245585 : if (to_freelist)
299 730692388 : bitmap_elem_to_freelist (head, element);
300 735245585 : }
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 3768844531 : bitmap_list_insert_element_after (bitmap head,
308 : bitmap_element *elt, unsigned int indx,
309 : bitmap_element *node = NULL)
310 : {
311 3768844531 : if (!node)
312 3764291334 : node = bitmap_element_allocate (head);
313 3768844531 : node->indx = indx;
314 :
315 3768844531 : gcc_checking_assert (!head->tree_form);
316 :
317 3768844531 : if (!elt)
318 : {
319 1775285209 : if (!head->current)
320 : {
321 1722631217 : head->current = node;
322 1722631217 : head->indx = indx;
323 : }
324 1775285209 : node->next = head->first;
325 1775285209 : if (node->next)
326 52653992 : node->next->prev = node;
327 1775285209 : head->first = node;
328 1775285209 : node->prev = NULL;
329 : }
330 : else
331 : {
332 1993559322 : gcc_checking_assert (head->current);
333 1993559322 : node->next = elt->next;
334 1993559322 : if (node->next)
335 75785715 : node->next->prev = node;
336 1993559322 : elt->next = node;
337 1993559322 : node->prev = elt;
338 : }
339 3768844531 : 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 95259711083 : bitmap_list_find_element (bitmap head, unsigned int indx)
349 : {
350 95259711083 : bitmap_element *element;
351 :
352 95259711083 : if (head->current == NULL
353 79811757089 : || head->indx == indx)
354 : return head->current;
355 :
356 11314773732 : if (head->current == head->first
357 5699276731 : && 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 7814440690 : bitmap_usage *usage = NULL;
363 7814440690 : 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 7814440690 : if (GATHER_STATISTICS && usage)
369 : usage->m_nsearches++;
370 :
371 7814440690 : if (head->indx < indx)
372 : /* INDX is beyond head->indx. Search from head->current
373 : forward. */
374 : for (element = head->current;
375 9421094858 : element->next != 0 && element->indx < indx;
376 : element = element->next)
377 : {
378 : if (GATHER_STATISTICS && usage)
379 : usage->m_search_iter++;
380 : }
381 :
382 4123081403 : 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 2728784310 : 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 4684614513 : 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 7814440690 : gcc_checking_assert (element != NULL);
407 7814440690 : head->current = element;
408 7814440690 : head->indx = element->indx;
409 7814440690 : if (element->indx != indx)
410 6749673339 : 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 240006453 : bitmap_tree_link_left (bitmap_element * &t, bitmap_element * &l)
429 : {
430 240006453 : l->next = t;
431 240006453 : l = t;
432 240006453 : t = t->next;
433 240006453 : }
434 :
435 : static inline void
436 263346731 : bitmap_tree_link_right (bitmap_element * &t, bitmap_element * &r)
437 : {
438 263346731 : r->prev = t;
439 263346731 : r = t;
440 263346731 : t = t->prev;
441 263346731 : }
442 :
443 : static inline void
444 83889429 : bitmap_tree_rotate_left (bitmap_element * &t)
445 : {
446 83889429 : bitmap_element *e = t->next;
447 83889429 : t->next = t->next->prev;
448 83889429 : e->prev = t;
449 83889429 : t = e;
450 83889429 : }
451 :
452 : static inline void
453 89197268 : bitmap_tree_rotate_right (bitmap_element * &t)
454 : {
455 89197268 : bitmap_element *e = t->prev;
456 89197268 : t->prev = t->prev->next;
457 89197268 : e->next = t;
458 89197268 : t = e;
459 89197268 : }
460 :
461 : static bitmap_element *
462 779577842 : bitmap_tree_splay (bitmap head, bitmap_element *t, unsigned int indx)
463 : {
464 779577842 : bitmap_element N, *l, *r;
465 :
466 779577842 : if (t == NULL)
467 : return NULL;
468 :
469 779577842 : bitmap_usage *usage = NULL;
470 779577842 : if (GATHER_STATISTICS)
471 : usage = bitmap_mem_desc.get_descriptor_for_instance (head);
472 :
473 779577842 : N.prev = N.next = NULL;
474 779577842 : l = r = &N;
475 :
476 1282931026 : while (indx != t->indx)
477 : {
478 665107161 : if (GATHER_STATISTICS && usage)
479 : usage->m_search_iter++;
480 :
481 665107161 : if (indx < t->indx)
482 : {
483 343603630 : if (t->prev != NULL && indx < t->prev->indx)
484 88920834 : bitmap_tree_rotate_right (t);
485 343603630 : if (t->prev == NULL)
486 : break;
487 263346731 : bitmap_tree_link_right (t, r);
488 : }
489 321503531 : else if (indx > t->indx)
490 : {
491 321503531 : if (t->next != NULL && indx > t->next->indx)
492 83889429 : bitmap_tree_rotate_left (t);
493 321503531 : if (t->next == NULL)
494 : break;
495 240006453 : bitmap_tree_link_left (t, l);
496 : }
497 : }
498 :
499 779577842 : l->next = t->prev;
500 779577842 : r->prev = t->next;
501 779577842 : t->prev = N.next;
502 779577842 : t->next = N.prev;
503 779577842 : return t;
504 : }
505 :
506 : /* Link bitmap element E into the current bitmap splay tree. */
507 :
508 : static inline void
509 201529507 : bitmap_tree_link_element (bitmap head, bitmap_element *e)
510 : {
511 201529507 : if (head->first == NULL)
512 145758830 : e->prev = e->next = NULL;
513 : else
514 : {
515 55770677 : bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx);
516 55770677 : if (e->indx < t->indx)
517 : {
518 25103233 : e->prev = t->prev;
519 25103233 : e->next = t;
520 25103233 : t->prev = NULL;
521 : }
522 30667444 : else if (e->indx > t->indx)
523 : {
524 30667444 : e->next = t->next;
525 30667444 : e->prev = t;
526 30667444 : t->next = NULL;
527 : }
528 : else
529 0 : gcc_unreachable ();
530 : }
531 201529507 : head->first = e;
532 201529507 : head->current = e;
533 201529507 : head->indx = e->indx;
534 201529507 : }
535 :
536 : /* Unlink bitmap element E from the current bitmap splay tree,
537 : and return it to the freelist. */
538 :
539 : static void
540 106320225 : bitmap_tree_unlink_element (bitmap head, bitmap_element *e)
541 : {
542 106320225 : bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx);
543 :
544 106320225 : gcc_checking_assert (t == e);
545 :
546 106320225 : if (e->prev == NULL)
547 105580769 : t = e->next;
548 : else
549 : {
550 739456 : t = bitmap_tree_splay (head, e->prev, e->indx);
551 739456 : t->next = e->next;
552 : }
553 106320225 : head->first = t;
554 106320225 : head->current = t;
555 106320225 : head->indx = (t != NULL) ? t->indx : 0;
556 :
557 106320225 : bitmap_elem_to_freelist (head, e);
558 106320225 : }
559 :
560 : /* Return the element for INDX, or NULL if the element doesn't exist. */
561 :
562 : static inline bitmap_element *
563 3367432663 : bitmap_tree_find_element (bitmap head, unsigned int indx)
564 : {
565 3367432663 : if (head->current == NULL
566 2428069594 : || 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 500781911 : bitmap_usage *usage = NULL;
572 500781911 : 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 500781911 : if (GATHER_STATISTICS && usage)
578 : usage->m_nsearches++;
579 :
580 500781911 : bitmap_element *element = bitmap_tree_splay (head, head->first, indx);
581 500781911 : gcc_checking_assert (element != NULL);
582 500781911 : head->first = element;
583 500781911 : head->current = element;
584 500781911 : head->indx = element->indx;
585 500781911 : if (element->indx != indx)
586 105243844 : 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 62081272 : bitmap_tree_listify_from (bitmap head, bitmap_element *e)
598 : {
599 62081272 : 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 62081272 : erb = e->next;
604 62081272 : e->next = NULL;
605 62081272 : t = bitmap_tree_splay (head, head->first, e->indx);
606 62081272 : 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 62081272 : t = e->prev;
611 62081272 : head->first = t;
612 62081272 : head->current = t;
613 62081272 : head->indx = (t != NULL) ? t->indx : 0;
614 :
615 : /* Detach the tree from E, and re-attach the right branch of E. */
616 62081272 : e->prev = NULL;
617 62081272 : 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 62081272 : auto_vec<bitmap_element *, 32> stack;
627 62081272 : auto_vec<bitmap_element *, 32> sorted_elements;
628 62081272 : bitmap_element *n = e;
629 :
630 101932405 : while (true)
631 : {
632 265946082 : while (n != NULL)
633 : {
634 101932405 : stack.safe_push (n);
635 101932405 : n = n->prev;
636 : }
637 :
638 164013677 : if (stack.is_empty ())
639 : break;
640 :
641 101932405 : n = stack.pop ();
642 101932405 : sorted_elements.safe_push (n);
643 101932405 : n = n->next;
644 : }
645 :
646 62081272 : gcc_assert (sorted_elements[0] == e);
647 :
648 : bitmap_element *prev = NULL;
649 : unsigned ix;
650 164013677 : FOR_EACH_VEC_ELT (sorted_elements, ix, n)
651 : {
652 101932405 : if (prev != NULL)
653 39851133 : prev->next = n;
654 101932405 : n->prev = prev;
655 101932405 : n->next = NULL;
656 101932405 : prev = n;
657 : }
658 :
659 62081272 : return e;
660 62081272 : }
661 :
662 : /* Convert bitmap HEAD from splay-tree view to linked-list view. */
663 :
664 : void
665 10477967 : bitmap_list_view (bitmap head)
666 : {
667 10477967 : bitmap_element *ptr;
668 :
669 10477967 : gcc_assert (head->tree_form);
670 :
671 10477967 : ptr = head->first;
672 10477967 : if (ptr)
673 : {
674 8473405 : while (ptr->prev)
675 276434 : bitmap_tree_rotate_right (ptr);
676 8196971 : head->first = ptr;
677 8196971 : head->first = bitmap_tree_listify_from (head, ptr);
678 : }
679 :
680 10477967 : head->tree_form = false;
681 10477967 : if (!head->current)
682 : {
683 10477967 : head->current = head->first;
684 10477967 : head->indx = head->current ? head->current->indx : 0;
685 : }
686 10477967 : }
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 210823206 : bitmap_tree_view (bitmap head)
695 : {
696 210823206 : bitmap_element *ptr;
697 :
698 210823206 : gcc_assert (! head->tree_form);
699 :
700 210823206 : ptr = head->first;
701 219062705 : while (ptr)
702 : {
703 8239499 : ptr->prev = NULL;
704 8239499 : ptr = ptr->next;
705 : }
706 :
707 210823206 : head->tree_form = true;
708 210823206 : }
709 :
710 : /* Clear a bitmap by freeing all its elements. */
711 :
712 : void
713 13414955594 : bitmap_clear (bitmap head)
714 : {
715 13414955594 : if (head->first == NULL)
716 : return;
717 6534556965 : if (head->tree_form)
718 : {
719 : bitmap_element *e, *t;
720 71115590 : for (e = head->first; e->prev; e = e->prev)
721 : /* Loop to find the element with the smallest index. */ ;
722 53884301 : t = bitmap_tree_splay (head, head->first, e->indx);
723 53884301 : gcc_checking_assert (t == e);
724 53884301 : head->first = t;
725 : }
726 6534556965 : 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 354101476 : bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
734 : {
735 354101476 : if (!bit_obstack)
736 : {
737 56609204 : 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 342865282 : bit_obstack->elements = NULL;
747 342865282 : bit_obstack->heads = NULL;
748 342865282 : 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 354062847 : bitmap_obstack_release (bitmap_obstack *bit_obstack)
759 : {
760 354062847 : if (!bit_obstack)
761 : {
762 56588035 : if (--bitmap_default_obstack_depth)
763 : {
764 11235709 : gcc_assert (bitmap_default_obstack_depth > 0);
765 : return;
766 : }
767 : bit_obstack = &bitmap_default_obstack;
768 : }
769 :
770 342827138 : bit_obstack->elements = NULL;
771 342827138 : bit_obstack->heads = NULL;
772 342827138 : 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 3776173366 : bitmap_alloc (bitmap_obstack *bit_obstack MEM_STAT_DECL)
780 : {
781 3776173366 : bitmap map;
782 :
783 3776173366 : if (!bit_obstack)
784 : {
785 656706802 : gcc_assert (bitmap_default_obstack_depth > 0);
786 : bit_obstack = &bitmap_default_obstack;
787 : }
788 3776173366 : map = bit_obstack->heads;
789 3776173366 : if (map)
790 1226225061 : bit_obstack->heads = (class bitmap_head *) map->first;
791 : else
792 2549948305 : map = XOBNEW (&bit_obstack->obstack, bitmap_head);
793 3776173366 : bitmap_initialize (map, bit_obstack PASS_MEM_STAT);
794 :
795 3776173366 : if (GATHER_STATISTICS)
796 : register_overhead (map, sizeof (bitmap_head));
797 :
798 3776173366 : return map;
799 : }
800 :
801 : /* Create a new GCd bitmap. */
802 :
803 : bitmap
804 45956116 : bitmap_gc_alloc (ALONE_MEM_STAT_DECL)
805 : {
806 45956116 : bitmap map;
807 :
808 45956116 : map = ggc_alloc<bitmap_head> ();
809 45956116 : bitmap_initialize (map, NULL PASS_MEM_STAT);
810 :
811 45956116 : if (GATHER_STATISTICS)
812 : register_overhead (map, sizeof (bitmap_head));
813 :
814 45956116 : return map;
815 : }
816 :
817 : /* Release an obstack allocated bitmap. */
818 :
819 : void
820 2482438824 : bitmap_obstack_free (bitmap map)
821 : {
822 2482438824 : if (map)
823 : {
824 1391061484 : bitmap_clear (map);
825 1391061484 : map->first = (bitmap_element *) map->obstack->heads;
826 :
827 1391061484 : if (GATHER_STATISTICS)
828 : release_overhead (map, sizeof (bitmap_head), true);
829 :
830 1391061484 : map->obstack->heads = map;
831 : }
832 2482438824 : }
833 :
834 :
835 : /* Return nonzero if all bits in an element are zero. */
836 :
837 : static inline int
838 802482125 : bitmap_element_zerop (const bitmap_element *element)
839 : {
840 : #if BITMAP_ELEMENT_WORDS == 2
841 802482125 : 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 1994346884 : bitmap_copy (bitmap to, const_bitmap from)
857 : {
858 1994346884 : const bitmap_element *from_ptr;
859 1994346884 : bitmap_element *to_ptr = 0;
860 :
861 1994346884 : gcc_checking_assert (!to->tree_form && !from->tree_form);
862 :
863 1994346884 : bitmap_clear (to);
864 :
865 : /* Copy elements in forward direction one at a time. */
866 4381039768 : for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
867 : {
868 2386692884 : bitmap_element *to_elt = bitmap_element_allocate (to);
869 :
870 2386692884 : to_elt->indx = from_ptr->indx;
871 2386692884 : 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 2386692884 : if (to_ptr == 0)
877 : {
878 1581857258 : to->first = to->current = to_elt;
879 1581857258 : to->indx = from_ptr->indx;
880 1581857258 : to_elt->next = to_elt->prev = 0;
881 : }
882 : else
883 : {
884 804835626 : to_elt->prev = to_ptr;
885 804835626 : to_elt->next = 0;
886 804835626 : to_ptr->next = to_elt;
887 : }
888 :
889 2386692884 : to_ptr = to_elt;
890 : }
891 1994346884 : }
892 :
893 : /* Move a bitmap to another bitmap. */
894 :
895 : void
896 31145146 : bitmap_move (bitmap to, bitmap from)
897 : {
898 31145146 : gcc_assert (to->obstack == from->obstack);
899 :
900 31145146 : bitmap_clear (to);
901 :
902 31145146 : size_t sz = 0;
903 31145146 : 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 31145146 : *to = *from;
911 :
912 31145146 : if (GATHER_STATISTICS)
913 : release_overhead (from, sz, false);
914 31145146 : }
915 :
916 : /* Clear a single bit in a bitmap. Return true if the bit changed. */
917 :
918 : bool
919 25217957693 : bitmap_clear_bit (bitmap head, int bit)
920 : {
921 25217957693 : unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
922 25217957693 : bitmap_element *ptr;
923 :
924 25217957693 : if (!head->tree_form)
925 24391377640 : ptr = bitmap_list_find_element (head, indx);
926 : else
927 826580053 : ptr = bitmap_tree_find_element (head, indx);
928 25217957693 : if (ptr != 0)
929 : {
930 20421572020 : unsigned bit_num = bit % BITMAP_WORD_BITS;
931 20421572020 : unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
932 20421572020 : BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
933 20421572020 : bool res = (ptr->bits[word_num] & bit_val) != 0;
934 20421572020 : if (res)
935 : {
936 3547131555 : ptr->bits[word_num] &= ~bit_val;
937 : /* If we cleared the entire word, free up the element. */
938 3547131555 : if (!ptr->bits[word_num]
939 3547131555 : && bitmap_element_zerop (ptr))
940 : {
941 588661243 : if (!head->tree_form)
942 505365292 : bitmap_list_unlink_element (head, ptr);
943 : else
944 83295951 : bitmap_tree_unlink_element (head, ptr);
945 : }
946 : }
947 :
948 20421572020 : 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 36571987931 : bitmap_set_bit (bitmap head, int bit)
958 : {
959 36571987931 : unsigned indx = bit / BITMAP_ELEMENT_ALL_BITS;
960 36571987931 : bitmap_element *ptr;
961 36571987931 : if (!head->tree_form)
962 34671056877 : ptr = bitmap_list_find_element (head, indx);
963 : else
964 1900931054 : ptr = bitmap_tree_find_element (head, indx);
965 36571987931 : unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
966 36571987931 : unsigned bit_num = bit % BITMAP_WORD_BITS;
967 36571987931 : BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
968 :
969 36571987931 : if (ptr != 0)
970 : {
971 29078963056 : bool res = (ptr->bits[word_num] & bit_val) == 0;
972 : /* Write back unconditionally to avoid branch mispredicts. */
973 29078963056 : ptr->bits[word_num] |= bit_val;
974 29078963056 : return res;
975 : }
976 :
977 7493024875 : ptr = bitmap_element_allocate (head);
978 7493024875 : ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
979 7493024875 : ptr->bits[word_num] = bit_val;
980 7493024875 : if (!head->tree_form)
981 7291629922 : bitmap_list_link_element (head, ptr);
982 : else
983 201394953 : 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 33656587188 : bitmap_bit_p (const_bitmap head, int bit)
991 : {
992 33656587188 : unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
993 33656587188 : const bitmap_element *ptr;
994 33656587188 : unsigned bit_num;
995 33656587188 : unsigned word_num;
996 :
997 33656587188 : if (!head->tree_form)
998 33031367916 : ptr = bitmap_list_find_element (const_cast<bitmap> (head), indx);
999 : else
1000 625219272 : ptr = bitmap_tree_find_element (const_cast<bitmap> (head), indx);
1001 33656587188 : if (ptr == 0)
1002 : return 0;
1003 :
1004 24517626194 : bit_num = bit % BITMAP_WORD_BITS;
1005 24517626194 : word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
1006 :
1007 24517626194 : 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 66674004 : bitmap_count_bits_in_word (const BITMAP_WORD *bits)
1117 : {
1118 66674004 : unsigned long count = 0;
1119 :
1120 202736640 : 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 135157760 : count += __builtin_popcountl (bits[ix]);
1126 : #else
1127 : count += bitmap_popcount (bits[ix]);
1128 : #endif
1129 : }
1130 67578880 : return count;
1131 : }
1132 :
1133 : /* Count the number of bits set in the bitmap, and return it. */
1134 :
1135 : unsigned long
1136 125821327 : bitmap_count_bits (const_bitmap a)
1137 : {
1138 125821327 : unsigned long count = 0;
1139 125821327 : const bitmap_element *elt;
1140 :
1141 125821327 : gcc_checking_assert (!a->tree_form);
1142 192349088 : for (elt = a->first; elt; elt = elt->next)
1143 133055522 : count += bitmap_count_bits_in_word (elt->bits);
1144 :
1145 125821327 : return count;
1146 : }
1147 :
1148 : /* Count the number of unique bits set in A and B and return it. */
1149 :
1150 : unsigned long
1151 779343 : bitmap_count_unique_bits (const_bitmap a, const_bitmap b)
1152 : {
1153 779343 : unsigned long count = 0;
1154 779343 : const bitmap_element *elt_a, *elt_b;
1155 :
1156 1830462 : 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 1051119 : if (elt_a->indx < elt_b->indx)
1162 : {
1163 59831 : count += bitmap_count_bits_in_word (elt_a->bits);
1164 59831 : elt_a = elt_a->next;
1165 : }
1166 991288 : else if (elt_b->indx < elt_a->indx)
1167 : {
1168 86412 : count += bitmap_count_bits_in_word (elt_b->bits);
1169 86412 : elt_b = elt_b->next;
1170 : }
1171 : else
1172 : {
1173 : BITMAP_WORD bits[BITMAP_ELEMENT_WORDS];
1174 2714628 : for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1175 1809752 : bits[ix] = elt_a->bits[ix] | elt_b->bits[ix];
1176 904876 : count += bitmap_count_bits_in_word (bits);
1177 904876 : elt_a = elt_a->next;
1178 904876 : elt_b = elt_b->next;
1179 : }
1180 : }
1181 779343 : return count;
1182 : }
1183 :
1184 : /* Return true if the bitmap has a single bit set. Otherwise return
1185 : false. */
1186 :
1187 : bool
1188 2639690 : bitmap_single_bit_set_p (const_bitmap a)
1189 : {
1190 2639690 : unsigned long count = 0;
1191 2639690 : const bitmap_element *elt;
1192 2639690 : unsigned ix;
1193 :
1194 2639690 : if (bitmap_empty_p (a))
1195 : return false;
1196 :
1197 2638316 : 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 2638316 : if (elt->next != NULL
1202 270725 : && (!a->tree_form || elt->prev != NULL))
1203 : return false;
1204 :
1205 5372870 : 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 4010739 : count += __builtin_popcountl (elt->bits[ix]);
1211 : #else
1212 : count += bitmap_popcount (elt->bits[ix]);
1213 : #endif
1214 4010739 : if (count > 1)
1215 : return false;
1216 : }
1217 :
1218 1362131 : 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 721922949 : bitmap_first_set_bit_worker (bitmap a, bool clear)
1227 : {
1228 721922949 : bitmap_element *elt = a->first;
1229 721922949 : unsigned bit_no;
1230 721922949 : BITMAP_WORD word;
1231 721922949 : unsigned ix;
1232 :
1233 721922949 : gcc_checking_assert (elt);
1234 :
1235 721922949 : if (a->tree_form)
1236 311838364 : while (elt->prev)
1237 : elt = elt->prev;
1238 :
1239 721922949 : bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
1240 911575316 : for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1241 : {
1242 911575316 : word = elt->bits[ix];
1243 911575316 : if (word)
1244 721922949 : goto found_bit;
1245 : }
1246 0 : gcc_unreachable ();
1247 721922949 : found_bit:
1248 721922949 : bit_no += ix * BITMAP_WORD_BITS;
1249 :
1250 : #if GCC_VERSION >= 3004
1251 721922949 : gcc_assert (sizeof (long) == sizeof (word));
1252 721922949 : 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 721922949 : if (clear)
1277 : {
1278 224733831 : elt->bits[ix] &= ~((BITMAP_WORD) 1 << (bit_no % BITMAP_WORD_BITS));
1279 : /* If we cleared the entire word, free up the element. */
1280 224733831 : if (!elt->bits[ix]
1281 224733831 : && bitmap_element_zerop (elt))
1282 : {
1283 46350648 : if (!a->tree_form)
1284 23326374 : bitmap_list_unlink_element (a, elt);
1285 : else
1286 23024274 : bitmap_tree_unlink_element (a, elt);
1287 : }
1288 : }
1289 :
1290 721922949 : 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 497189118 : bitmap_first_set_bit (const_bitmap a)
1298 : {
1299 497189118 : 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 224733831 : bitmap_clear_first_set_bit (bitmap a)
1307 : {
1308 224733831 : 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 721641110 : bitmap_and (bitmap dst, const_bitmap a, const_bitmap b)
1366 : {
1367 721641110 : bitmap_element *dst_elt = dst->first;
1368 721641110 : const bitmap_element *a_elt = a->first;
1369 721641110 : const bitmap_element *b_elt = b->first;
1370 721641110 : bitmap_element *dst_prev = NULL;
1371 :
1372 721641110 : gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
1373 721641110 : gcc_assert (dst != a && dst != b);
1374 :
1375 721641110 : if (a == b)
1376 : {
1377 0 : bitmap_copy (dst, a);
1378 0 : return;
1379 : }
1380 :
1381 1698392456 : while (a_elt && b_elt)
1382 : {
1383 976751346 : if (a_elt->indx < b_elt->indx)
1384 24576556 : a_elt = a_elt->next;
1385 952174790 : else if (b_elt->indx < a_elt->indx)
1386 179777334 : b_elt = b_elt->next;
1387 : else
1388 : {
1389 : /* Matching elts, generate A & B. */
1390 772397456 : unsigned ix;
1391 772397456 : BITMAP_WORD ior = 0;
1392 :
1393 772397456 : if (!dst_elt)
1394 248428802 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
1395 : a_elt->indx);
1396 : else
1397 523968654 : dst_elt->indx = a_elt->indx;
1398 2317192368 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1399 : {
1400 1544794912 : BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
1401 :
1402 1544794912 : dst_elt->bits[ix] = r;
1403 1544794912 : ior |= r;
1404 : }
1405 772397456 : if (ior)
1406 : {
1407 464442096 : dst_prev = dst_elt;
1408 464442096 : dst_elt = dst_elt->next;
1409 : }
1410 772397456 : a_elt = a_elt->next;
1411 772397456 : b_elt = b_elt->next;
1412 : }
1413 : }
1414 : /* Ensure that dst->current is valid. */
1415 721641110 : dst->current = dst->first;
1416 721641110 : bitmap_elt_clear_from (dst, dst_elt);
1417 721641110 : gcc_checking_assert (!dst->current == !dst->first);
1418 721641110 : if (dst->current)
1419 400262353 : dst->indx = dst->current->indx;
1420 : }
1421 :
1422 : /* A &= B. Return true if A changed. */
1423 :
1424 : bool
1425 1036106680 : bitmap_and_into (bitmap a, const_bitmap b)
1426 : {
1427 1036106680 : bitmap_element *a_elt = a->first;
1428 1036106680 : const bitmap_element *b_elt = b->first;
1429 1036106680 : bitmap_element *next;
1430 1036106680 : bool changed = false;
1431 :
1432 1036106680 : gcc_checking_assert (!a->tree_form && !b->tree_form);
1433 :
1434 1036106680 : if (a == b)
1435 : return false;
1436 :
1437 3021238330 : while (a_elt && b_elt)
1438 : {
1439 1985131650 : if (a_elt->indx < b_elt->indx)
1440 : {
1441 43468662 : next = a_elt->next;
1442 43468662 : bitmap_list_unlink_element (a, a_elt);
1443 43468662 : a_elt = next;
1444 43468662 : changed = true;
1445 : }
1446 1941662988 : else if (b_elt->indx < a_elt->indx)
1447 53712770 : b_elt = b_elt->next;
1448 : else
1449 : {
1450 : /* Matching elts, generate A &= B. */
1451 : unsigned ix;
1452 : BITMAP_WORD ior = 0;
1453 :
1454 5663850654 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1455 : {
1456 3775900436 : BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
1457 3775900436 : if (a_elt->bits[ix] != r)
1458 382912654 : changed = true;
1459 3775900436 : a_elt->bits[ix] = r;
1460 3775900436 : ior |= r;
1461 : }
1462 1887950218 : next = a_elt->next;
1463 1887950218 : if (!ior)
1464 6987865 : bitmap_list_unlink_element (a, a_elt);
1465 1887950218 : a_elt = next;
1466 1887950218 : b_elt = b_elt->next;
1467 : }
1468 : }
1469 :
1470 1036106680 : if (a_elt)
1471 : {
1472 56265027 : changed = true;
1473 56265027 : bitmap_elt_clear_from (a, a_elt);
1474 : }
1475 :
1476 1036106680 : 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 3455880643 : bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
1489 : const bitmap_element *src_elt, bool changed)
1490 : {
1491 3455880643 : if (!changed && dst_elt && dst_elt->indx == src_elt->indx)
1492 : {
1493 : unsigned ix;
1494 :
1495 282327645 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1496 188218430 : if (src_elt->bits[ix] != dst_elt->bits[ix])
1497 : {
1498 26533065 : dst_elt->bits[ix] = src_elt->bits[ix];
1499 26533065 : changed = true;
1500 : }
1501 : }
1502 : else
1503 : {
1504 3456625204 : changed = true;
1505 3294115947 : if (!dst_elt)
1506 3199262171 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
1507 3199262171 : src_elt->indx);
1508 : else
1509 162509257 : dst_elt->indx = src_elt->indx;
1510 3361771428 : memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits));
1511 : }
1512 3455880643 : return changed;
1513 : }
1514 :
1515 :
1516 :
1517 : /* DST = A & ~B */
1518 :
1519 : bool
1520 190874251 : bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b)
1521 : {
1522 190874251 : bitmap_element *dst_elt = dst->first;
1523 190874251 : const bitmap_element *a_elt = a->first;
1524 190874251 : const bitmap_element *b_elt = b->first;
1525 190874251 : bitmap_element *dst_prev = NULL;
1526 190874251 : bitmap_element **dst_prev_pnext = &dst->first;
1527 190874251 : bool changed = false;
1528 :
1529 190874251 : gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
1530 190874251 : gcc_assert (dst != a && dst != b);
1531 :
1532 190874251 : if (a == b)
1533 : {
1534 0 : changed = !bitmap_empty_p (dst);
1535 0 : bitmap_clear (dst);
1536 0 : return changed;
1537 : }
1538 :
1539 550975049 : while (a_elt)
1540 : {
1541 375457127 : while (b_elt && b_elt->indx < a_elt->indx)
1542 15356329 : b_elt = b_elt->next;
1543 :
1544 360100798 : if (!b_elt || b_elt->indx > a_elt->indx)
1545 : {
1546 190714267 : changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed);
1547 190714267 : dst_prev = *dst_prev_pnext;
1548 190714267 : dst_prev_pnext = &dst_prev->next;
1549 190714267 : dst_elt = *dst_prev_pnext;
1550 190714267 : a_elt = a_elt->next;
1551 : }
1552 :
1553 : else
1554 : {
1555 : /* Matching elts, generate A & ~B. */
1556 169386531 : unsigned ix;
1557 169386531 : BITMAP_WORD ior = 0;
1558 :
1559 169386531 : if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1560 : {
1561 131976177 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1562 : {
1563 87984118 : BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1564 :
1565 87984118 : if (dst_elt->bits[ix] != r)
1566 : {
1567 29935017 : changed = true;
1568 29935017 : dst_elt->bits[ix] = r;
1569 : }
1570 87984118 : ior |= r;
1571 : }
1572 : }
1573 : else
1574 : {
1575 108814591 : bool new_element;
1576 125394472 : if (!dst_elt || dst_elt->indx > a_elt->indx)
1577 : {
1578 124188865 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
1579 : a_elt->indx);
1580 124188865 : new_element = true;
1581 : }
1582 : else
1583 : {
1584 1205607 : dst_elt->indx = a_elt->indx;
1585 1205607 : new_element = false;
1586 : }
1587 :
1588 376183416 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1589 : {
1590 250788944 : BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1591 :
1592 250788944 : dst_elt->bits[ix] = r;
1593 250788944 : ior |= r;
1594 : }
1595 :
1596 125394472 : if (ior)
1597 : changed = true;
1598 : else
1599 : {
1600 43281592 : changed |= !new_element;
1601 43281592 : bitmap_list_unlink_element (dst, dst_elt);
1602 43281592 : dst_elt = *dst_prev_pnext;
1603 : }
1604 : }
1605 :
1606 87273651 : if (ior)
1607 : {
1608 125179341 : dst_prev = *dst_prev_pnext;
1609 125179341 : dst_prev_pnext = &dst_prev->next;
1610 125179341 : dst_elt = *dst_prev_pnext;
1611 : }
1612 169386531 : a_elt = a_elt->next;
1613 169386531 : b_elt = b_elt->next;
1614 : }
1615 : }
1616 :
1617 : /* Ensure that dst->current is valid. */
1618 190874251 : dst->current = dst->first;
1619 :
1620 190874251 : if (dst_elt)
1621 : {
1622 1756201 : changed = true;
1623 1756201 : bitmap_elt_clear_from (dst, dst_elt);
1624 : }
1625 190874251 : gcc_checking_assert (!dst->current == !dst->first);
1626 190874251 : if (dst->current)
1627 143901970 : dst->indx = dst->current->indx;
1628 :
1629 : return changed;
1630 : }
1631 :
1632 : /* A &= ~B. Returns true if A changes */
1633 :
1634 : bool
1635 418468546 : bitmap_and_compl_into (bitmap a, const_bitmap b)
1636 : {
1637 418468546 : bitmap_element *a_elt = a->first;
1638 418468546 : const bitmap_element *b_elt = b->first;
1639 418468546 : bitmap_element *next;
1640 418468546 : BITMAP_WORD changed = 0;
1641 :
1642 418468546 : gcc_checking_assert (!a->tree_form && !b->tree_form);
1643 :
1644 418468546 : 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 1236478134 : while (a_elt && b_elt)
1656 : {
1657 818009588 : if (a_elt->indx < b_elt->indx)
1658 173852157 : a_elt = a_elt->next;
1659 644157431 : else if (b_elt->indx < a_elt->indx)
1660 343969873 : b_elt = b_elt->next;
1661 : else
1662 : {
1663 : /* Matching elts, generate A &= ~B. */
1664 : unsigned ix;
1665 : BITMAP_WORD ior = 0;
1666 :
1667 900562674 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1668 : {
1669 600375116 : BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1670 600375116 : BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
1671 :
1672 600375116 : a_elt->bits[ix] = r;
1673 600375116 : changed |= cleared;
1674 600375116 : ior |= r;
1675 : }
1676 300187558 : next = a_elt->next;
1677 300187558 : if (!ior)
1678 13483981 : bitmap_list_unlink_element (a, a_elt);
1679 300187558 : a_elt = next;
1680 300187558 : b_elt = b_elt->next;
1681 : }
1682 : }
1683 418468546 : gcc_checking_assert (!a->current == !a->first
1684 : && (!a->current || a->indx == a->current->indx));
1685 418468546 : return changed != 0;
1686 : }
1687 :
1688 : /* Set COUNT bits from START in HEAD. */
1689 : void
1690 1647892677 : bitmap_set_range (bitmap head, unsigned int start, unsigned int count)
1691 : {
1692 1647892677 : unsigned int first_index, end_bit_plus1, last_index;
1693 1647892677 : bitmap_element *elt, *elt_prev;
1694 1647892677 : unsigned int i;
1695 :
1696 1647892677 : gcc_checking_assert (!head->tree_form);
1697 :
1698 1647892677 : if (!count)
1699 : return;
1700 :
1701 1333518196 : if (count == 1)
1702 : {
1703 595522171 : bitmap_set_bit (head, start);
1704 595522171 : return;
1705 : }
1706 :
1707 737996025 : first_index = start / BITMAP_ELEMENT_ALL_BITS;
1708 737996025 : end_bit_plus1 = start + count;
1709 737996025 : last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1710 737996025 : 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 737996025 : if (!elt)
1717 : {
1718 141234557 : elt = bitmap_element_allocate (head);
1719 141234557 : elt->indx = first_index;
1720 141234557 : bitmap_list_link_element (head, elt);
1721 : }
1722 :
1723 737996025 : gcc_checking_assert (elt->indx == first_index);
1724 737996025 : elt_prev = elt->prev;
1725 1534090072 : for (i = first_index; i <= last_index; i++)
1726 : {
1727 796094047 : unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS;
1728 796094047 : unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1729 :
1730 796094047 : unsigned int first_word_to_mod;
1731 796094047 : BITMAP_WORD first_mask;
1732 796094047 : unsigned int last_word_to_mod;
1733 796094047 : BITMAP_WORD last_mask;
1734 796094047 : unsigned int ix;
1735 :
1736 796094047 : if (!elt || elt->indx != i)
1737 57830420 : elt = bitmap_list_insert_element_after (head, elt_prev, i);
1738 :
1739 796094047 : if (elt_start_bit <= start)
1740 : {
1741 : /* The first bit to turn on is somewhere inside this
1742 : elt. */
1743 737996025 : first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1744 :
1745 : /* This mask should have 1s in all bits >= start position. */
1746 737996025 : first_mask =
1747 737996025 : (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1748 737996025 : 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 796094047 : 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 733185497 : last_word_to_mod =
1767 733185497 : (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1768 :
1769 : /* The last mask should have 1s below the end bit. */
1770 733185497 : last_mask =
1771 733185497 : (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1;
1772 : }
1773 :
1774 796094047 : if (first_word_to_mod == last_word_to_mod)
1775 : {
1776 723915824 : BITMAP_WORD mask = first_mask & last_mask;
1777 723915824 : elt->bits[first_word_to_mod] |= mask;
1778 : }
1779 : else
1780 : {
1781 72178223 : elt->bits[first_word_to_mod] |= first_mask;
1782 72178223 : 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 72178223 : elt->bits[last_word_to_mod] |= last_mask;
1786 : }
1787 :
1788 796094047 : elt_prev = elt;
1789 796094047 : elt = elt->next;
1790 : }
1791 :
1792 737996025 : head->current = elt ? elt : elt_prev;
1793 737996025 : head->indx = head->current->indx;
1794 : }
1795 :
1796 : /* Clear COUNT bits from START in HEAD. */
1797 : void
1798 2838587104 : bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
1799 : {
1800 2838587104 : unsigned int first_index, end_bit_plus1, last_index;
1801 2838587104 : bitmap_element *elt;
1802 :
1803 2838587104 : gcc_checking_assert (!head->tree_form);
1804 :
1805 2838587104 : if (!count)
1806 : return;
1807 :
1808 2838586701 : if (count == 1)
1809 : {
1810 410674396 : bitmap_clear_bit (head, start);
1811 410674396 : return;
1812 : }
1813 :
1814 2427912305 : first_index = start / BITMAP_ELEMENT_ALL_BITS;
1815 2427912305 : end_bit_plus1 = start + count;
1816 2427912305 : last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1817 2427912305 : 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 2427912305 : if (!elt)
1823 : {
1824 1663574513 : if (head->current)
1825 : {
1826 1607381771 : if (head->indx < first_index)
1827 : {
1828 1139028156 : elt = head->current->next;
1829 1139028156 : if (!elt)
1830 : return;
1831 : }
1832 : else
1833 : elt = head->current;
1834 : }
1835 : else
1836 : return;
1837 : }
1838 :
1839 2709114303 : while (elt && (elt->indx <= last_index))
1840 : {
1841 925110566 : bitmap_element * next_elt = elt->next;
1842 925110566 : unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
1843 925110566 : unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1844 :
1845 :
1846 925110566 : 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 51759118 : bitmap_list_unlink_element (head, elt);
1849 : else
1850 : {
1851 : /* Going to have to knock out some bits in this elt. */
1852 873351448 : unsigned int first_word_to_mod;
1853 873351448 : BITMAP_WORD first_mask;
1854 873351448 : unsigned int last_word_to_mod;
1855 873351448 : BITMAP_WORD last_mask;
1856 873351448 : unsigned int i;
1857 873351448 : bool clear = true;
1858 :
1859 873351448 : if (elt_start_bit <= start)
1860 : {
1861 : /* The first bit to turn off is somewhere inside this
1862 : elt. */
1863 762256358 : first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1864 :
1865 : /* This mask should have 1s in all bits >= start position. */
1866 762256358 : first_mask =
1867 762256358 : (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1868 762256358 : 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 873351448 : 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 724539775 : last_word_to_mod =
1889 724539775 : (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1890 :
1891 : /* The last mask should have 1s below the end bit. */
1892 724539775 : last_mask =
1893 724539775 : (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
1894 : }
1895 :
1896 :
1897 873351448 : if (first_word_to_mod == last_word_to_mod)
1898 : {
1899 724741272 : BITMAP_WORD mask = first_mask & last_mask;
1900 724741272 : elt->bits[first_word_to_mod] &= ~mask;
1901 : }
1902 : else
1903 : {
1904 148610176 : elt->bits[first_word_to_mod] &= ~first_mask;
1905 148610176 : 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 148610176 : elt->bits[last_word_to_mod] &= ~last_mask;
1909 : }
1910 1177870904 : for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1911 1134851400 : if (elt->bits[i])
1912 : {
1913 : clear = false;
1914 : break;
1915 : }
1916 : /* Check to see if there are any bits left. */
1917 873351448 : if (clear)
1918 43019504 : bitmap_list_unlink_element (head, elt);
1919 : }
1920 : elt = next_elt;
1921 : }
1922 :
1923 1784003737 : if (elt)
1924 : {
1925 1417497258 : head->current = elt;
1926 1417497258 : 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 7365215199 : 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 7365215199 : gcc_assert (a_elt || b_elt);
2011 :
2012 7365215199 : if (a_elt && b_elt && a_elt->indx == b_elt->indx)
2013 : {
2014 : /* Matching elts, generate A | B. */
2015 4207508884 : unsigned ix;
2016 :
2017 4207508884 : if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
2018 : {
2019 11013519492 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2020 : {
2021 7342346328 : BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
2022 7342346328 : if (r != dst_elt->bits[ix])
2023 : {
2024 1233285660 : dst_elt->bits[ix] = r;
2025 1233285660 : changed = true;
2026 : }
2027 : }
2028 : }
2029 : else
2030 : {
2031 937301155 : changed = true;
2032 535546511 : if (!dst_elt)
2033 134581076 : dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
2034 : a_elt->indx);
2035 : else
2036 401754644 : dst_elt->indx = a_elt->indx;
2037 1609007160 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2038 : {
2039 1072671440 : BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
2040 1072671440 : dst_elt->bits[ix] = r;
2041 : }
2042 : }
2043 : }
2044 : else
2045 : {
2046 : /* Copy a single element. */
2047 2924742114 : const bitmap_element *src;
2048 :
2049 3157706315 : if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
2050 : src = a_elt;
2051 : else
2052 189639193 : src = b_elt;
2053 :
2054 3114381307 : gcc_checking_assert (src);
2055 3157706315 : changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed);
2056 : }
2057 7365215199 : return changed;
2058 : }
2059 :
2060 :
2061 : /* DST = A | B. Return true if DST changes. */
2062 :
2063 : bool
2064 338918149 : bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b)
2065 : {
2066 338918149 : bitmap_element *dst_elt = dst->first;
2067 338918149 : const bitmap_element *a_elt = a->first;
2068 338918149 : const bitmap_element *b_elt = b->first;
2069 338918149 : bitmap_element *dst_prev = NULL;
2070 338918149 : bitmap_element **dst_prev_pnext = &dst->first;
2071 338918149 : bool changed = false;
2072 :
2073 338918149 : gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
2074 338918149 : gcc_assert (dst != a && dst != b);
2075 :
2076 944177414 : while (a_elt || b_elt)
2077 : {
2078 605259265 : changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed);
2079 :
2080 605259265 : if (a_elt && b_elt && a_elt->indx == b_elt->indx)
2081 : {
2082 210307223 : a_elt = a_elt->next;
2083 210307223 : b_elt = b_elt->next;
2084 : }
2085 : else
2086 : {
2087 394952042 : if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
2088 32944189 : a_elt = a_elt->next;
2089 362007853 : else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
2090 362007853 : b_elt = b_elt->next;
2091 : }
2092 :
2093 605259265 : dst_prev = *dst_prev_pnext;
2094 605259265 : dst_prev_pnext = &dst_prev->next;
2095 605259265 : dst_elt = *dst_prev_pnext;
2096 : }
2097 :
2098 338918149 : if (dst_elt)
2099 : {
2100 7852 : changed = true;
2101 : /* Ensure that dst->current is valid. */
2102 7852 : dst->current = dst->first;
2103 7852 : bitmap_elt_clear_from (dst, dst_elt);
2104 : }
2105 338918149 : gcc_checking_assert (!dst->current == !dst->first);
2106 338918149 : if (dst->current)
2107 337622187 : dst->indx = dst->current->indx;
2108 338918149 : return changed;
2109 : }
2110 :
2111 : /* A |= B. Return true if A changes. */
2112 :
2113 : bool
2114 4667920074 : bitmap_ior_into (bitmap a, const_bitmap b)
2115 : {
2116 4667920074 : bitmap_element *a_elt = a->first;
2117 4667920074 : const bitmap_element *b_elt = b->first;
2118 4667920074 : bitmap_element *a_prev = NULL;
2119 4667920074 : bitmap_element **a_prev_pnext = &a->first;
2120 4667920074 : bool changed = false;
2121 :
2122 4667920074 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2123 4667920074 : if (a == b)
2124 : return false;
2125 :
2126 11194601451 : while (b_elt)
2127 : {
2128 : /* If A lags behind B, just advance it. */
2129 6526685510 : if (!a_elt || a_elt->indx == b_elt->indx)
2130 : {
2131 5644934190 : changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
2132 5644934190 : b_elt = b_elt->next;
2133 : }
2134 881751320 : else if (a_elt->indx > b_elt->indx)
2135 : {
2136 106172787 : changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed);
2137 106172787 : b_elt = b_elt->next;
2138 : }
2139 :
2140 6526685510 : a_prev = *a_prev_pnext;
2141 6526685510 : a_prev_pnext = &a_prev->next;
2142 6526685510 : a_elt = *a_prev_pnext;
2143 : }
2144 :
2145 4667915941 : gcc_checking_assert (!a->current == !a->first);
2146 4667915941 : if (a->current)
2147 4338485846 : 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 11595340 : bitmap_ior_into_and_free (bitmap a, bitmap *b_)
2156 : {
2157 11595340 : bitmap b = *b_;
2158 11595340 : bitmap_element *a_elt = a->first;
2159 11595340 : bitmap_element *b_elt = b->first;
2160 11595340 : bitmap_element *a_prev = NULL;
2161 11595340 : bitmap_element **a_prev_pnext = &a->first;
2162 11595340 : bool changed = false;
2163 :
2164 11595340 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2165 11595340 : gcc_assert (a->obstack == b->obstack);
2166 11595340 : if (a == b)
2167 : return false;
2168 :
2169 38690757 : while (b_elt)
2170 : {
2171 : /* If A lags behind B, just advance it. */
2172 27095417 : if (!a_elt || a_elt->indx == b_elt->indx)
2173 : {
2174 16905564 : changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
2175 16905564 : b_elt = b_elt->next;
2176 : }
2177 10189853 : else if (a_elt->indx > b_elt->indx)
2178 : {
2179 4553197 : bitmap_element *b_elt_next = b_elt->next;
2180 4553197 : bitmap_list_unlink_element (b, b_elt, false);
2181 4553197 : bitmap_list_insert_element_after (a, a_prev, b_elt->indx, b_elt);
2182 4553197 : b_elt = b_elt_next;
2183 : }
2184 :
2185 27095417 : a_prev = *a_prev_pnext;
2186 27095417 : a_prev_pnext = &a_prev->next;
2187 27095417 : a_elt = *a_prev_pnext;
2188 : }
2189 :
2190 11595340 : gcc_checking_assert (!a->current == !a->first);
2191 11595340 : if (a->current)
2192 11595340 : a->indx = a->current->indx;
2193 :
2194 11595340 : if (b->obstack)
2195 11595340 : 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 487771967 : bitmap_equal_p (const_bitmap a, const_bitmap b)
2348 : {
2349 487771967 : const bitmap_element *a_elt;
2350 487771967 : const bitmap_element *b_elt;
2351 487771967 : unsigned ix;
2352 :
2353 487771967 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2354 :
2355 487771967 : for (a_elt = a->first, b_elt = b->first;
2356 998899932 : a_elt && b_elt;
2357 511127965 : a_elt = a_elt->next, b_elt = b_elt->next)
2358 : {
2359 629245126 : if (a_elt->indx != b_elt->indx)
2360 : return false;
2361 1623341323 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2362 1112213358 : if (a_elt->bits[ix] != b_elt->bits[ix])
2363 : return false;
2364 : }
2365 369654806 : return !a_elt && !b_elt;
2366 : }
2367 :
2368 : /* Return true if A AND B is not empty. */
2369 :
2370 : bool
2371 385958282 : bitmap_intersect_p (const_bitmap a, const_bitmap b)
2372 : {
2373 385958282 : const bitmap_element *a_elt;
2374 385958282 : const bitmap_element *b_elt;
2375 385958282 : unsigned ix;
2376 :
2377 385958282 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2378 :
2379 385958282 : for (a_elt = a->first, b_elt = b->first;
2380 757891328 : a_elt && b_elt;)
2381 : {
2382 464398552 : if (a_elt->indx < b_elt->indx)
2383 167933046 : a_elt = a_elt->next;
2384 296465506 : else if (b_elt->indx < a_elt->indx)
2385 71417927 : b_elt = b_elt->next;
2386 : else
2387 : {
2388 522549165 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2389 389967092 : if (a_elt->bits[ix] & b_elt->bits[ix])
2390 : return true;
2391 132582073 : a_elt = a_elt->next;
2392 132582073 : 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 170 : bitmap_intersect_compl_p (const_bitmap a, const_bitmap b)
2402 : {
2403 170 : const bitmap_element *a_elt;
2404 170 : const bitmap_element *b_elt;
2405 170 : unsigned ix;
2406 :
2407 170 : gcc_checking_assert (!a->tree_form && !b->tree_form);
2408 :
2409 170 : for (a_elt = a->first, b_elt = b->first;
2410 308 : a_elt && b_elt;)
2411 : {
2412 170 : if (a_elt->indx < b_elt->indx)
2413 : return true;
2414 170 : else if (b_elt->indx < a_elt->indx)
2415 0 : b_elt = b_elt->next;
2416 : else
2417 : {
2418 446 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2419 308 : if (a_elt->bits[ix] & ~b_elt->bits[ix])
2420 : return true;
2421 138 : a_elt = a_elt->next;
2422 138 : 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 862118408 : bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill)
2433 : {
2434 862118408 : bool changed = false;
2435 :
2436 862118408 : bitmap_element *dst_elt = dst->first;
2437 862118408 : const bitmap_element *a_elt = a->first;
2438 862118408 : const bitmap_element *b_elt = b->first;
2439 862118408 : const bitmap_element *kill_elt = kill->first;
2440 862118408 : bitmap_element *dst_prev = NULL;
2441 862118408 : bitmap_element **dst_prev_pnext = &dst->first;
2442 :
2443 862118408 : gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form
2444 : && !kill->tree_form);
2445 862118408 : gcc_assert (dst != a && dst != b && dst != kill);
2446 :
2447 : /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
2448 862118408 : if (b == kill || bitmap_empty_p (b))
2449 : {
2450 65823331 : changed = !bitmap_equal_p (dst, a);
2451 65823331 : if (changed)
2452 4024494 : bitmap_copy (dst, a);
2453 65823331 : return changed;
2454 : }
2455 796295077 : if (bitmap_empty_p (kill))
2456 289442753 : return bitmap_ior (dst, a, b);
2457 506852324 : if (bitmap_empty_p (a))
2458 36039149 : return bitmap_and_compl (dst, b, kill);
2459 :
2460 1557673389 : while (a_elt || b_elt)
2461 : {
2462 1086860214 : bool new_element = false;
2463 :
2464 1086860214 : if (b_elt)
2465 1082702523 : while (kill_elt && kill_elt->indx < b_elt->indx)
2466 25491616 : kill_elt = kill_elt->next;
2467 :
2468 1086860214 : if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
2469 601566525 : && (!a_elt || a_elt->indx >= b_elt->indx))
2470 : {
2471 595448899 : bitmap_element tmp_elt;
2472 595448899 : unsigned ix;
2473 :
2474 595448899 : BITMAP_WORD ior = 0;
2475 595448899 : tmp_elt.indx = b_elt->indx;
2476 1786346697 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2477 : {
2478 1190897798 : BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix];
2479 1190897798 : ior |= r;
2480 1190897798 : tmp_elt.bits[ix] = r;
2481 : }
2482 :
2483 595448899 : if (ior)
2484 : {
2485 553036932 : changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
2486 : a_elt, &tmp_elt, changed);
2487 553036932 : new_element = true;
2488 553036932 : if (a_elt && a_elt->indx == b_elt->indx)
2489 482742546 : a_elt = a_elt->next;
2490 : }
2491 :
2492 595448899 : b_elt = b_elt->next;
2493 595448899 : kill_elt = kill_elt->next;
2494 : }
2495 : else
2496 : {
2497 491411315 : changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
2498 : a_elt, b_elt, changed);
2499 491411315 : new_element = true;
2500 :
2501 491411315 : if (a_elt && b_elt && a_elt->indx == b_elt->indx)
2502 : {
2503 136019857 : a_elt = a_elt->next;
2504 136019857 : b_elt = b_elt->next;
2505 : }
2506 : else
2507 : {
2508 355391458 : if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
2509 50055123 : a_elt = a_elt->next;
2510 305336335 : else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
2511 305336335 : b_elt = b_elt->next;
2512 : }
2513 : }
2514 :
2515 1086860214 : if (new_element)
2516 : {
2517 1044448247 : dst_prev = *dst_prev_pnext;
2518 1044448247 : dst_prev_pnext = &dst_prev->next;
2519 1044448247 : dst_elt = *dst_prev_pnext;
2520 : }
2521 : }
2522 :
2523 470813175 : if (dst_elt)
2524 : {
2525 3159 : changed = true;
2526 : /* Ensure that dst->current is valid. */
2527 3159 : dst->current = dst->first;
2528 3159 : bitmap_elt_clear_from (dst, dst_elt);
2529 : }
2530 470813175 : gcc_checking_assert (!dst->current == !dst->first);
2531 470813175 : if (dst->current)
2532 470813175 : dst->indx = dst->current->indx;
2533 :
2534 : return changed;
2535 : }
2536 :
2537 : /* A |= (B & ~C). Return true if A changes. */
2538 :
2539 : bool
2540 52902681 : bitmap_ior_and_compl_into (bitmap a, const_bitmap b, const_bitmap c)
2541 : {
2542 52902681 : bitmap_element *a_elt = a->first;
2543 52902681 : const bitmap_element *b_elt = b->first;
2544 52902681 : const bitmap_element *c_elt = c->first;
2545 52902681 : bitmap_element and_elt;
2546 52902681 : bitmap_element *a_prev = NULL;
2547 52902681 : bitmap_element **a_prev_pnext = &a->first;
2548 52902681 : bool changed = false;
2549 52902681 : unsigned ix;
2550 :
2551 52902681 : gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form);
2552 :
2553 52902681 : if (a == b)
2554 : return false;
2555 52592682 : if (bitmap_empty_p (c))
2556 11492334 : return bitmap_ior_into (a, b);
2557 41100348 : else if (bitmap_empty_p (a))
2558 20975053 : return bitmap_and_compl (a, b, c);
2559 :
2560 20125295 : and_elt.indx = -1;
2561 65704868 : while (b_elt)
2562 : {
2563 : /* Advance C. */
2564 57615685 : while (c_elt && c_elt->indx < b_elt->indx)
2565 12036112 : c_elt = c_elt->next;
2566 :
2567 45579573 : const bitmap_element *and_elt_ptr;
2568 45579573 : if (c_elt && c_elt->indx == b_elt->indx)
2569 : {
2570 13279872 : BITMAP_WORD overall = 0;
2571 13279872 : and_elt_ptr = &and_elt;
2572 13279872 : and_elt.indx = b_elt->indx;
2573 39839616 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2574 : {
2575 26559744 : and_elt.bits[ix] = b_elt->bits[ix] & ~c_elt->bits[ix];
2576 26559744 : overall |= and_elt.bits[ix];
2577 : }
2578 13279872 : if (!overall)
2579 : {
2580 1267437 : b_elt = b_elt->next;
2581 1267437 : continue;
2582 : }
2583 : }
2584 : else
2585 : and_elt_ptr = b_elt;
2586 :
2587 44312136 : b_elt = b_elt->next;
2588 :
2589 : /* Now find a place to insert AND_ELT. */
2590 51167032 : do
2591 : {
2592 51167032 : ix = a_elt ? a_elt->indx : and_elt_ptr->indx;
2593 51167032 : if (ix == and_elt_ptr->indx)
2594 43076047 : changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt,
2595 : and_elt_ptr, changed);
2596 8090985 : else if (ix > and_elt_ptr->indx)
2597 1236089 : changed = bitmap_elt_copy (a, NULL, a_prev, and_elt_ptr, changed);
2598 :
2599 51167032 : a_prev = *a_prev_pnext;
2600 51167032 : a_prev_pnext = &a_prev->next;
2601 51167032 : a_elt = *a_prev_pnext;
2602 :
2603 : /* If A lagged behind B/C, we advanced it so loop once more. */
2604 : }
2605 51167032 : while (ix < and_elt_ptr->indx);
2606 : }
2607 :
2608 20125295 : gcc_checking_assert (!a->current == !a->first);
2609 20125295 : if (a->current)
2610 20125295 : a->indx = a->current->indx;
2611 : return changed;
2612 : }
2613 :
2614 : /* A |= (B & C). Return true if A changes. */
2615 :
2616 : bool
2617 11699163 : bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c)
2618 : {
2619 11699163 : bitmap_element *a_elt = a->first;
2620 11699163 : const bitmap_element *b_elt = b->first;
2621 11699163 : const bitmap_element *c_elt = c->first;
2622 11699163 : bitmap_element and_elt;
2623 11699163 : bitmap_element *a_prev = NULL;
2624 11699163 : bitmap_element **a_prev_pnext = &a->first;
2625 11699163 : bool changed = false;
2626 11699163 : unsigned ix;
2627 :
2628 11699163 : gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form);
2629 :
2630 11699163 : if (b == c)
2631 0 : return bitmap_ior_into (a, b);
2632 11699163 : if (bitmap_empty_p (b) || bitmap_empty_p (c))
2633 : return false;
2634 :
2635 : and_elt.indx = -1;
2636 26869783 : while (b_elt && c_elt)
2637 : {
2638 : BITMAP_WORD overall;
2639 :
2640 : /* Find a common item of B and C. */
2641 21698906 : while (b_elt->indx != c_elt->indx)
2642 : {
2643 6528284 : if (b_elt->indx < c_elt->indx)
2644 : {
2645 683964 : b_elt = b_elt->next;
2646 683964 : if (!b_elt)
2647 196740 : goto done;
2648 : }
2649 : else
2650 : {
2651 5844320 : c_elt = c_elt->next;
2652 5844320 : if (!c_elt)
2653 207698 : goto done;
2654 : }
2655 : }
2656 :
2657 15170622 : overall = 0;
2658 15170622 : and_elt.indx = b_elt->indx;
2659 45511866 : for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2660 : {
2661 30341244 : and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix];
2662 30341244 : overall |= and_elt.bits[ix];
2663 : }
2664 :
2665 15170622 : b_elt = b_elt->next;
2666 15170622 : c_elt = c_elt->next;
2667 15170622 : if (!overall)
2668 4527551 : continue;
2669 :
2670 : /* Now find a place to insert AND_ELT. */
2671 10643180 : do
2672 : {
2673 10643180 : ix = a_elt ? a_elt->indx : and_elt.indx;
2674 10643180 : if (ix == and_elt.indx)
2675 10591886 : changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed);
2676 51294 : else if (ix > and_elt.indx)
2677 51185 : changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed);
2678 :
2679 10643180 : a_prev = *a_prev_pnext;
2680 10643180 : a_prev_pnext = &a_prev->next;
2681 10643180 : a_elt = *a_prev_pnext;
2682 :
2683 : /* If A lagged behind B/C, we advanced it so loop once more. */
2684 : }
2685 10643180 : while (ix < and_elt.indx);
2686 : }
2687 :
2688 11294723 : done:
2689 11699161 : gcc_checking_assert (!a->current == !a->first);
2690 11699161 : if (a->current)
2691 9020888 : a->indx = a->current->indx;
2692 : return changed;
2693 : }
2694 :
2695 : /* Compute hash of bitmap (for purposes of hashing). */
2696 :
2697 : hashval_t
2698 261101288 : bitmap_hash (const_bitmap head)
2699 : {
2700 261101288 : const bitmap_element *ptr;
2701 261101288 : BITMAP_WORD hash = 0;
2702 261101288 : int ix;
2703 :
2704 261101288 : gcc_checking_assert (!head->tree_form);
2705 :
2706 596105905 : for (ptr = head->first; ptr; ptr = ptr->next)
2707 : {
2708 335004617 : hash ^= ptr->indx;
2709 1005013851 : for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
2710 670009234 : hash ^= ptr->bits[ix];
2711 : }
2712 261101288 : 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 2581 : bitmap_print (FILE *file, const_bitmap head, const char *prefix,
2808 : const char *suffix)
2809 : {
2810 2581 : const char *comma = "";
2811 2581 : unsigned i;
2812 :
2813 2581 : fputs (prefix, file);
2814 2581 : 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 2412 : bitmap_iterator bi;
2835 23025 : EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
2836 : {
2837 20613 : fprintf (file, "%s%d", comma, i);
2838 20613 : comma = ", ";
2839 : }
2840 : }
2841 2581 : fputs (suffix, file);
2842 2581 : }
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"
|
