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