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