]>
Commit | Line | Data |
---|---|---|
096ab9ea | 1 | /* Functions to support general ended bitmaps. |
6fb5fa3c | 2 | Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005, |
d652f226 | 3 | 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc. |
096ab9ea | 4 | |
1322177d | 5 | This file is part of GCC. |
096ab9ea | 6 | |
1322177d LB |
7 | GCC is free software; you can redistribute it and/or modify it under |
8 | the terms of the GNU General Public License as published by the Free | |
9dcd6f09 | 9 | Software Foundation; either version 3, or (at your option) any later |
1322177d | 10 | version. |
096ab9ea | 11 | |
1322177d LB |
12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 | for more details. | |
096ab9ea RK |
16 | |
17 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
096ab9ea | 20 | |
096ab9ea | 21 | #include "config.h" |
670ee920 | 22 | #include "system.h" |
4977bab6 | 23 | #include "coretypes.h" |
096ab9ea | 24 | #include "obstack.h" |
e2500fed | 25 | #include "ggc.h" |
efc9bd41 | 26 | #include "bitmap.h" |
f75709c6 JH |
27 | #include "hashtab.h" |
28 | ||
29 | #ifdef GATHER_STATISTICS | |
30 | ||
31 | /* Store information about each particular bitmap. */ | |
32 | struct bitmap_descriptor | |
33 | { | |
34 | const char *function; | |
35 | const char *file; | |
36 | int line; | |
f75709c6 | 37 | int created; |
e2d87023 BL |
38 | HOST_WIDEST_INT allocated; |
39 | HOST_WIDEST_INT peak; | |
40 | HOST_WIDEST_INT current; | |
f75709c6 | 41 | int nsearches; |
d4fb676f | 42 | int search_iter; |
f75709c6 JH |
43 | }; |
44 | ||
45 | /* Hashtable mapping bitmap names to descriptors. */ | |
46 | static htab_t bitmap_desc_hash; | |
47 | ||
48 | /* Hashtable helpers. */ | |
49 | static hashval_t | |
50 | hash_descriptor (const void *p) | |
51 | { | |
aebde504 KG |
52 | const struct bitmap_descriptor *const d = |
53 | (const struct bitmap_descriptor *) p; | |
f75709c6 JH |
54 | return htab_hash_pointer (d->file) + d->line; |
55 | } | |
56 | struct loc | |
57 | { | |
58 | const char *file; | |
59 | const char *function; | |
60 | int line; | |
61 | }; | |
62 | static int | |
63 | eq_descriptor (const void *p1, const void *p2) | |
64 | { | |
aebde504 KG |
65 | const struct bitmap_descriptor *const d = |
66 | (const struct bitmap_descriptor *) p1; | |
67 | const struct loc *const l = (const struct loc *) p2; | |
f75709c6 JH |
68 | return d->file == l->file && d->function == l->function && d->line == l->line; |
69 | } | |
70 | ||
71 | /* For given file and line, return descriptor, create new if needed. */ | |
72 | static struct bitmap_descriptor * | |
73 | bitmap_descriptor (const char *file, const char *function, int line) | |
74 | { | |
75 | struct bitmap_descriptor **slot; | |
76 | struct loc loc; | |
77 | ||
78 | loc.file = file; | |
79 | loc.function = function; | |
80 | loc.line = line; | |
81 | ||
82 | if (!bitmap_desc_hash) | |
83 | bitmap_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL); | |
84 | ||
85 | slot = (struct bitmap_descriptor **) | |
86 | htab_find_slot_with_hash (bitmap_desc_hash, &loc, | |
87 | htab_hash_pointer (file) + line, | |
f136c8ae | 88 | INSERT); |
f75709c6 JH |
89 | if (*slot) |
90 | return *slot; | |
aebde504 | 91 | *slot = XCNEW (struct bitmap_descriptor); |
f75709c6 JH |
92 | (*slot)->file = file; |
93 | (*slot)->function = function; | |
94 | (*slot)->line = line; | |
95 | return *slot; | |
96 | } | |
97 | ||
98 | /* Register new bitmap. */ | |
99 | void | |
100 | bitmap_register (bitmap b MEM_STAT_DECL) | |
101 | { | |
102 | b->desc = bitmap_descriptor (_loc_name, _loc_function, _loc_line); | |
103 | b->desc->created++; | |
104 | } | |
105 | ||
106 | /* Account the overhead. */ | |
107 | static void | |
108 | register_overhead (bitmap b, int amount) | |
109 | { | |
110 | b->desc->current += amount; | |
111 | if (amount > 0) | |
112 | b->desc->allocated += amount; | |
113 | gcc_assert (b->desc->current >= 0); | |
114 | if (b->desc->peak < b->desc->current) | |
115 | b->desc->peak = b->desc->current; | |
116 | } | |
117 | #endif | |
096ab9ea | 118 | |
096ab9ea | 119 | /* Global data */ |
7932a3db NS |
120 | bitmap_element bitmap_zero_bits; /* An element of all zero bits. */ |
121 | bitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */ | |
a68ab351 | 122 | static int bitmap_default_obstack_depth; |
7932a3db NS |
123 | static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of |
124 | GC'd elements. */ | |
096ab9ea | 125 | |
4682ae04 AJ |
126 | static void bitmap_elem_to_freelist (bitmap, bitmap_element *); |
127 | static void bitmap_element_free (bitmap, bitmap_element *); | |
128 | static bitmap_element *bitmap_element_allocate (bitmap); | |
e326eeb5 | 129 | static int bitmap_element_zerop (const bitmap_element *); |
4682ae04 | 130 | static void bitmap_element_link (bitmap, bitmap_element *); |
1bc40c7e | 131 | static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int); |
88c4f655 | 132 | static void bitmap_elt_clear_from (bitmap, bitmap_element *); |
4682ae04 | 133 | static bitmap_element *bitmap_find_bit (bitmap, unsigned int); |
096ab9ea | 134 | \f |
88c4f655 | 135 | |
e2500fed | 136 | /* Add ELEM to the appropriate freelist. */ |
47c321d4 | 137 | static inline void |
4682ae04 | 138 | bitmap_elem_to_freelist (bitmap head, bitmap_element *elt) |
e2500fed | 139 | { |
7932a3db | 140 | bitmap_obstack *bit_obstack = head->obstack; |
c22cacf3 | 141 | |
5765e552 | 142 | elt->next = NULL; |
7932a3db | 143 | if (bit_obstack) |
e2500fed | 144 | { |
5765e552 | 145 | elt->prev = bit_obstack->elements; |
7932a3db | 146 | bit_obstack->elements = elt; |
e2500fed GK |
147 | } |
148 | else | |
149 | { | |
5765e552 | 150 | elt->prev = bitmap_ggc_free; |
e2500fed GK |
151 | bitmap_ggc_free = elt; |
152 | } | |
153 | } | |
154 | ||
a615c28a RH |
155 | /* Free a bitmap element. Since these are allocated off the |
156 | bitmap_obstack, "free" actually means "put onto the freelist". */ | |
096ab9ea | 157 | |
47c321d4 | 158 | static inline void |
4682ae04 | 159 | bitmap_element_free (bitmap head, bitmap_element *elt) |
096ab9ea RK |
160 | { |
161 | bitmap_element *next = elt->next; | |
162 | bitmap_element *prev = elt->prev; | |
163 | ||
164 | if (prev) | |
165 | prev->next = next; | |
166 | ||
167 | if (next) | |
168 | next->prev = prev; | |
169 | ||
170 | if (head->first == elt) | |
171 | head->first = next; | |
172 | ||
173 | /* Since the first thing we try is to insert before current, | |
174 | make current the next entry in preference to the previous. */ | |
175 | if (head->current == elt) | |
87a2e7a8 DB |
176 | { |
177 | head->current = next != 0 ? next : prev; | |
178 | if (head->current) | |
179 | head->indx = head->current->indx; | |
c22cacf3 | 180 | else |
1bc40c7e | 181 | head->indx = 0; |
87a2e7a8 | 182 | } |
f75709c6 JH |
183 | #ifdef GATHER_STATISTICS |
184 | register_overhead (head, -((int)sizeof (bitmap_element))); | |
185 | #endif | |
e2500fed | 186 | bitmap_elem_to_freelist (head, elt); |
096ab9ea RK |
187 | } |
188 | \f | |
189 | /* Allocate a bitmap element. The bits are cleared, but nothing else is. */ | |
190 | ||
47c321d4 | 191 | static inline bitmap_element * |
4682ae04 | 192 | bitmap_element_allocate (bitmap head) |
096ab9ea RK |
193 | { |
194 | bitmap_element *element; | |
7932a3db | 195 | bitmap_obstack *bit_obstack = head->obstack; |
c22cacf3 | 196 | |
7932a3db | 197 | if (bit_obstack) |
22fa5b8a | 198 | { |
7932a3db | 199 | element = bit_obstack->elements; |
c22cacf3 | 200 | |
7932a3db | 201 | if (element) |
5765e552 KZ |
202 | /* Use up the inner list first before looking at the next |
203 | element of the outer list. */ | |
204 | if (element->next) | |
205 | { | |
206 | bit_obstack->elements = element->next; | |
207 | bit_obstack->elements->prev = element->prev; | |
208 | } | |
209 | else | |
210 | /* Inner list was just a singleton. */ | |
211 | bit_obstack->elements = element->prev; | |
e2500fed | 212 | else |
7932a3db | 213 | element = XOBNEW (&bit_obstack->obstack, bitmap_element); |
e2500fed GK |
214 | } |
215 | else | |
216 | { | |
7932a3db NS |
217 | element = bitmap_ggc_free; |
218 | if (element) | |
5765e552 KZ |
219 | /* Use up the inner list first before looking at the next |
220 | element of the outer list. */ | |
221 | if (element->next) | |
222 | { | |
223 | bitmap_ggc_free = element->next; | |
224 | bitmap_ggc_free->prev = element->prev; | |
225 | } | |
226 | else | |
227 | /* Inner list was just a singleton. */ | |
228 | bitmap_ggc_free = element->prev; | |
e2500fed | 229 | else |
a9429e29 | 230 | element = ggc_alloc_bitmap_element_def (); |
22fa5b8a | 231 | } |
096ab9ea | 232 | |
f75709c6 JH |
233 | #ifdef GATHER_STATISTICS |
234 | register_overhead (head, sizeof (bitmap_element)); | |
235 | #endif | |
a615c28a | 236 | memset (element->bits, 0, sizeof (element->bits)); |
096ab9ea RK |
237 | |
238 | return element; | |
239 | } | |
240 | ||
7932a3db | 241 | /* Remove ELT and all following elements from bitmap HEAD. */ |
87e08c69 RH |
242 | |
243 | void | |
7932a3db NS |
244 | bitmap_elt_clear_from (bitmap head, bitmap_element *elt) |
245 | { | |
5765e552 KZ |
246 | bitmap_element *prev; |
247 | bitmap_obstack *bit_obstack = head->obstack; | |
f75709c6 JH |
248 | #ifdef GATHER_STATISTICS |
249 | int n; | |
250 | #endif | |
5765e552 KZ |
251 | |
252 | if (!elt) return; | |
f75709c6 JH |
253 | #ifdef GATHER_STATISTICS |
254 | n = 0; | |
255 | for (prev = elt; prev; prev = prev->next) | |
256 | n++; | |
257 | register_overhead (head, -sizeof (bitmap_element) * n); | |
258 | #endif | |
7932a3db | 259 | |
5765e552 KZ |
260 | prev = elt->prev; |
261 | if (prev) | |
262 | { | |
263 | prev->next = NULL; | |
264 | if (head->current->indx > prev->indx) | |
265 | { | |
266 | head->current = prev; | |
267 | head->indx = prev->indx; | |
268 | } | |
c22cacf3 | 269 | } |
5765e552 KZ |
270 | else |
271 | { | |
272 | head->first = NULL; | |
273 | head->current = NULL; | |
274 | head->indx = 0; | |
275 | } | |
276 | ||
c22cacf3 | 277 | /* Put the entire list onto the free list in one operation. */ |
5765e552 | 278 | if (bit_obstack) |
7932a3db | 279 | { |
c22cacf3 | 280 | elt->prev = bit_obstack->elements; |
5765e552 KZ |
281 | bit_obstack->elements = elt; |
282 | } | |
283 | else | |
284 | { | |
285 | elt->prev = bitmap_ggc_free; | |
286 | bitmap_ggc_free = elt; | |
7932a3db NS |
287 | } |
288 | } | |
289 | ||
290 | /* Clear a bitmap by freeing the linked list. */ | |
291 | ||
5fd8300b | 292 | void |
7932a3db | 293 | bitmap_clear (bitmap head) |
87e08c69 | 294 | { |
5765e552 KZ |
295 | if (head->first) |
296 | bitmap_elt_clear_from (head, head->first); | |
7932a3db NS |
297 | } |
298 | \f | |
299 | /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize | |
300 | the default bitmap obstack. */ | |
301 | ||
302 | void | |
303 | bitmap_obstack_initialize (bitmap_obstack *bit_obstack) | |
304 | { | |
305 | if (!bit_obstack) | |
a68ab351 JJ |
306 | { |
307 | if (bitmap_default_obstack_depth++) | |
308 | return; | |
309 | bit_obstack = &bitmap_default_obstack; | |
310 | } | |
7932a3db NS |
311 | |
312 | #if !defined(__GNUC__) || (__GNUC__ < 2) | |
313 | #define __alignof__(type) 0 | |
314 | #endif | |
315 | ||
316 | bit_obstack->elements = NULL; | |
317 | bit_obstack->heads = NULL; | |
318 | obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE, | |
319 | __alignof__ (bitmap_element), | |
320 | obstack_chunk_alloc, | |
321 | obstack_chunk_free); | |
87e08c69 RH |
322 | } |
323 | ||
7932a3db NS |
324 | /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL, |
325 | release the default bitmap obstack. */ | |
326 | ||
327 | void | |
328 | bitmap_obstack_release (bitmap_obstack *bit_obstack) | |
329 | { | |
330 | if (!bit_obstack) | |
a68ab351 JJ |
331 | { |
332 | if (--bitmap_default_obstack_depth) | |
333 | { | |
334 | gcc_assert (bitmap_default_obstack_depth > 0); | |
335 | return; | |
336 | } | |
337 | bit_obstack = &bitmap_default_obstack; | |
338 | } | |
c22cacf3 | 339 | |
7932a3db NS |
340 | bit_obstack->elements = NULL; |
341 | bit_obstack->heads = NULL; | |
342 | obstack_free (&bit_obstack->obstack, NULL); | |
343 | } | |
344 | ||
345 | /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create | |
346 | it on the default bitmap obstack. */ | |
347 | ||
348 | bitmap | |
f75709c6 | 349 | bitmap_obstack_alloc_stat (bitmap_obstack *bit_obstack MEM_STAT_DECL) |
7932a3db NS |
350 | { |
351 | bitmap map; | |
352 | ||
353 | if (!bit_obstack) | |
354 | bit_obstack = &bitmap_default_obstack; | |
355 | map = bit_obstack->heads; | |
356 | if (map) | |
dba2cc0c | 357 | bit_obstack->heads = (struct bitmap_head_def *) map->first; |
7932a3db NS |
358 | else |
359 | map = XOBNEW (&bit_obstack->obstack, bitmap_head); | |
f75709c6 JH |
360 | bitmap_initialize_stat (map, bit_obstack PASS_MEM_STAT); |
361 | #ifdef GATHER_STATISTICS | |
362 | register_overhead (map, sizeof (bitmap_head)); | |
363 | #endif | |
7932a3db NS |
364 | |
365 | return map; | |
366 | } | |
367 | ||
368 | /* Create a new GCd bitmap. */ | |
369 | ||
370 | bitmap | |
f75709c6 | 371 | bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL) |
7932a3db NS |
372 | { |
373 | bitmap map; | |
374 | ||
a9429e29 | 375 | map = ggc_alloc_bitmap_head_def (); |
f75709c6 JH |
376 | bitmap_initialize_stat (map, NULL PASS_MEM_STAT); |
377 | #ifdef GATHER_STATISTICS | |
378 | register_overhead (map, sizeof (bitmap_head)); | |
379 | #endif | |
7932a3db NS |
380 | |
381 | return map; | |
382 | } | |
383 | ||
7932a3db NS |
384 | /* Release an obstack allocated bitmap. */ |
385 | ||
386 | void | |
387 | bitmap_obstack_free (bitmap map) | |
388 | { | |
cc175e7c NS |
389 | if (map) |
390 | { | |
391 | bitmap_clear (map); | |
dba2cc0c | 392 | map->first = (bitmap_element *) map->obstack->heads; |
f75709c6 JH |
393 | #ifdef GATHER_STATISTICS |
394 | register_overhead (map, -((int)sizeof (bitmap_head))); | |
395 | #endif | |
cc175e7c NS |
396 | map->obstack->heads = map; |
397 | } | |
7932a3db NS |
398 | } |
399 | ||
7932a3db | 400 | \f |
096ab9ea RK |
401 | /* Return nonzero if all bits in an element are zero. */ |
402 | ||
47c321d4 | 403 | static inline int |
e326eeb5 | 404 | bitmap_element_zerop (const bitmap_element *element) |
096ab9ea RK |
405 | { |
406 | #if BITMAP_ELEMENT_WORDS == 2 | |
407 | return (element->bits[0] | element->bits[1]) == 0; | |
408 | #else | |
65a6f342 | 409 | unsigned i; |
096ab9ea RK |
410 | |
411 | for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
412 | if (element->bits[i] != 0) | |
413 | return 0; | |
414 | ||
415 | return 1; | |
416 | #endif | |
417 | } | |
418 | \f | |
419 | /* Link the bitmap element into the current bitmap linked list. */ | |
420 | ||
47c321d4 | 421 | static inline void |
4682ae04 | 422 | bitmap_element_link (bitmap head, bitmap_element *element) |
096ab9ea RK |
423 | { |
424 | unsigned int indx = element->indx; | |
425 | bitmap_element *ptr; | |
426 | ||
427 | /* If this is the first and only element, set it in. */ | |
428 | if (head->first == 0) | |
429 | { | |
430 | element->next = element->prev = 0; | |
431 | head->first = element; | |
432 | } | |
433 | ||
434 | /* If this index is less than that of the current element, it goes someplace | |
435 | before the current element. */ | |
436 | else if (indx < head->indx) | |
437 | { | |
438 | for (ptr = head->current; | |
439 | ptr->prev != 0 && ptr->prev->indx > indx; | |
440 | ptr = ptr->prev) | |
441 | ; | |
442 | ||
443 | if (ptr->prev) | |
444 | ptr->prev->next = element; | |
445 | else | |
446 | head->first = element; | |
447 | ||
448 | element->prev = ptr->prev; | |
449 | element->next = ptr; | |
450 | ptr->prev = element; | |
451 | } | |
452 | ||
453 | /* Otherwise, it must go someplace after the current element. */ | |
454 | else | |
455 | { | |
456 | for (ptr = head->current; | |
457 | ptr->next != 0 && ptr->next->indx < indx; | |
458 | ptr = ptr->next) | |
459 | ; | |
460 | ||
461 | if (ptr->next) | |
462 | ptr->next->prev = element; | |
463 | ||
464 | element->next = ptr->next; | |
465 | element->prev = ptr; | |
466 | ptr->next = element; | |
467 | } | |
468 | ||
469 | /* Set up so this is the first element searched. */ | |
470 | head->current = element; | |
471 | head->indx = indx; | |
472 | } | |
88c4f655 NS |
473 | |
474 | /* Insert a new uninitialized element into bitmap HEAD after element | |
475 | ELT. If ELT is NULL, insert the element at the start. Return the | |
476 | new element. */ | |
477 | ||
478 | static bitmap_element * | |
1bc40c7e | 479 | bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx) |
88c4f655 NS |
480 | { |
481 | bitmap_element *node = bitmap_element_allocate (head); | |
1bc40c7e | 482 | node->indx = indx; |
88c4f655 NS |
483 | |
484 | if (!elt) | |
485 | { | |
486 | if (!head->current) | |
1bc40c7e KZ |
487 | { |
488 | head->current = node; | |
489 | head->indx = indx; | |
490 | } | |
88c4f655 NS |
491 | node->next = head->first; |
492 | if (node->next) | |
493 | node->next->prev = node; | |
494 | head->first = node; | |
495 | node->prev = NULL; | |
496 | } | |
497 | else | |
498 | { | |
377002a9 | 499 | gcc_checking_assert (head->current); |
88c4f655 NS |
500 | node->next = elt->next; |
501 | if (node->next) | |
502 | node->next->prev = node; | |
503 | elt->next = node; | |
504 | node->prev = elt; | |
505 | } | |
506 | return node; | |
507 | } | |
096ab9ea | 508 | \f |
a615c28a | 509 | /* Copy a bitmap to another bitmap. */ |
096ab9ea RK |
510 | |
511 | void | |
e326eeb5 | 512 | bitmap_copy (bitmap to, const_bitmap from) |
096ab9ea | 513 | { |
e326eeb5 KG |
514 | const bitmap_element *from_ptr; |
515 | bitmap_element *to_ptr = 0; | |
096ab9ea RK |
516 | |
517 | bitmap_clear (to); | |
518 | ||
f9da5064 | 519 | /* Copy elements in forward direction one at a time. */ |
096ab9ea RK |
520 | for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next) |
521 | { | |
e2500fed | 522 | bitmap_element *to_elt = bitmap_element_allocate (to); |
096ab9ea RK |
523 | |
524 | to_elt->indx = from_ptr->indx; | |
fd6132db | 525 | memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits)); |
096ab9ea RK |
526 | |
527 | /* Here we have a special case of bitmap_element_link, for the case | |
528 | where we know the links are being entered in sequence. */ | |
529 | if (to_ptr == 0) | |
530 | { | |
531 | to->first = to->current = to_elt; | |
532 | to->indx = from_ptr->indx; | |
533 | to_elt->next = to_elt->prev = 0; | |
534 | } | |
535 | else | |
536 | { | |
537 | to_elt->prev = to_ptr; | |
538 | to_elt->next = 0; | |
539 | to_ptr->next = to_elt; | |
540 | } | |
541 | ||
542 | to_ptr = to_elt; | |
543 | } | |
544 | } | |
545 | \f | |
546 | /* Find a bitmap element that would hold a bitmap's bit. | |
547 | Update the `current' field even if we can't find an element that | |
548 | would hold the bitmap's bit to make eventual allocation | |
549 | faster. */ | |
550 | ||
47c321d4 | 551 | static inline bitmap_element * |
4682ae04 | 552 | bitmap_find_bit (bitmap head, unsigned int bit) |
096ab9ea RK |
553 | { |
554 | bitmap_element *element; | |
72e42e26 | 555 | unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS; |
096ab9ea | 556 | |
279be7c8 RE |
557 | if (head->current == 0 |
558 | || head->indx == indx) | |
559 | return head->current; | |
d4fb676f JH |
560 | #ifdef GATHER_STATISTICS |
561 | head->desc->nsearches++; | |
562 | #endif | |
096ab9ea | 563 | |
3aeee1b4 KH |
564 | if (head->indx < indx) |
565 | /* INDX is beyond head->indx. Search from head->current | |
566 | forward. */ | |
567 | for (element = head->current; | |
568 | element->next != 0 && element->indx < indx; | |
569 | element = element->next) | |
d4fb676f JH |
570 | #ifdef GATHER_STATISTICS |
571 | head->desc->search_iter++; | |
572 | #else | |
3aeee1b4 | 573 | ; |
d4fb676f | 574 | #endif |
3aeee1b4 KH |
575 | |
576 | else if (head->indx / 2 < indx) | |
577 | /* INDX is less than head->indx and closer to head->indx than to | |
578 | 0. Search from head->current backward. */ | |
096ab9ea RK |
579 | for (element = head->current; |
580 | element->prev != 0 && element->indx > indx; | |
581 | element = element->prev) | |
d4fb676f JH |
582 | #ifdef GATHER_STATISTICS |
583 | head->desc->search_iter++; | |
584 | #else | |
096ab9ea | 585 | ; |
d4fb676f | 586 | #endif |
096ab9ea RK |
587 | |
588 | else | |
3aeee1b4 KH |
589 | /* INDX is less than head->indx and closer to 0 than to |
590 | head->indx. Search from head->first forward. */ | |
591 | for (element = head->first; | |
096ab9ea RK |
592 | element->next != 0 && element->indx < indx; |
593 | element = element->next) | |
d4fb676f JH |
594 | #ifdef GATHER_STATISTICS |
595 | head->desc->search_iter++; | |
596 | #else | |
096ab9ea | 597 | ; |
d4fb676f | 598 | #endif |
096ab9ea RK |
599 | |
600 | /* `element' is the nearest to the one we want. If it's not the one we | |
601 | want, the one we want doesn't exist. */ | |
602 | head->current = element; | |
603 | head->indx = element->indx; | |
604 | if (element != 0 && element->indx != indx) | |
605 | element = 0; | |
606 | ||
607 | return element; | |
608 | } | |
609 | \f | |
5f0d975b | 610 | /* Clear a single bit in a bitmap. Return true if the bit changed. */ |
096ab9ea | 611 | |
5f0d975b | 612 | bool |
4682ae04 | 613 | bitmap_clear_bit (bitmap head, int bit) |
096ab9ea | 614 | { |
e326eeb5 | 615 | bitmap_element *const ptr = bitmap_find_bit (head, bit); |
096ab9ea RK |
616 | |
617 | if (ptr != 0) | |
618 | { | |
72e42e26 SB |
619 | unsigned bit_num = bit % BITMAP_WORD_BITS; |
620 | unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; | |
5f0d975b RG |
621 | BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; |
622 | bool res = (ptr->bits[word_num] & bit_val) != 0; | |
623 | if (res) | |
07309d58 UB |
624 | { |
625 | ptr->bits[word_num] &= ~bit_val; | |
626 | /* If we cleared the entire word, free up the element. */ | |
627 | if (!ptr->bits[word_num] | |
628 | && bitmap_element_zerop (ptr)) | |
629 | bitmap_element_free (head, ptr); | |
630 | } | |
5f0d975b RG |
631 | |
632 | return res; | |
096ab9ea | 633 | } |
5f0d975b RG |
634 | |
635 | return false; | |
096ab9ea RK |
636 | } |
637 | ||
5f0d975b | 638 | /* Set a single bit in a bitmap. Return true if the bit changed. */ |
096ab9ea | 639 | |
5f0d975b | 640 | bool |
4682ae04 | 641 | bitmap_set_bit (bitmap head, int bit) |
096ab9ea RK |
642 | { |
643 | bitmap_element *ptr = bitmap_find_bit (head, bit); | |
72e42e26 SB |
644 | unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; |
645 | unsigned bit_num = bit % BITMAP_WORD_BITS; | |
646 | BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; | |
096ab9ea RK |
647 | |
648 | if (ptr == 0) | |
649 | { | |
e2500fed | 650 | ptr = bitmap_element_allocate (head); |
096ab9ea RK |
651 | ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS; |
652 | ptr->bits[word_num] = bit_val; | |
653 | bitmap_element_link (head, ptr); | |
5f0d975b | 654 | return true; |
096ab9ea RK |
655 | } |
656 | else | |
5f0d975b RG |
657 | { |
658 | bool res = (ptr->bits[word_num] & bit_val) == 0; | |
659 | if (res) | |
660 | ptr->bits[word_num] |= bit_val; | |
661 | return res; | |
662 | } | |
096ab9ea | 663 | } |
a615c28a | 664 | |
096ab9ea RK |
665 | /* Return whether a bit is set within a bitmap. */ |
666 | ||
667 | int | |
4682ae04 | 668 | bitmap_bit_p (bitmap head, int bit) |
096ab9ea RK |
669 | { |
670 | bitmap_element *ptr; | |
671 | unsigned bit_num; | |
672 | unsigned word_num; | |
673 | ||
674 | ptr = bitmap_find_bit (head, bit); | |
675 | if (ptr == 0) | |
676 | return 0; | |
677 | ||
72e42e26 SB |
678 | bit_num = bit % BITMAP_WORD_BITS; |
679 | word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; | |
096ab9ea | 680 | |
8229306b | 681 | return (ptr->bits[word_num] >> bit_num) & 1; |
096ab9ea RK |
682 | } |
683 | \f | |
1bc40c7e KZ |
684 | #if GCC_VERSION < 3400 |
685 | /* Table of number of set bits in a character, indexed by value of char. */ | |
e326eeb5 | 686 | static const unsigned char popcount_table[] = |
1bc40c7e KZ |
687 | { |
688 | 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, | |
689 | 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, | |
690 | 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, | |
691 | 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, | |
692 | 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, | |
693 | 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, | |
694 | 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, | |
695 | 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, | |
696 | }; | |
697 | ||
698 | static unsigned long | |
699 | bitmap_popcount (BITMAP_WORD a) | |
700 | { | |
701 | unsigned long ret = 0; | |
702 | unsigned i; | |
703 | ||
704 | /* Just do this the table way for now */ | |
705 | for (i = 0; i < BITMAP_WORD_BITS; i+= 8) | |
706 | ret += popcount_table[(a >> i) & 0xff]; | |
707 | return ret; | |
708 | } | |
709 | #endif | |
710 | /* Count the number of bits set in the bitmap, and return it. */ | |
711 | ||
712 | unsigned long | |
e326eeb5 | 713 | bitmap_count_bits (const_bitmap a) |
1bc40c7e KZ |
714 | { |
715 | unsigned long count = 0; | |
e326eeb5 | 716 | const bitmap_element *elt; |
1bc40c7e KZ |
717 | unsigned ix; |
718 | ||
719 | for (elt = a->first; elt; elt = elt->next) | |
720 | { | |
721 | for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
722 | { | |
723 | #if GCC_VERSION >= 3400 | |
724 | /* Note that popcountl matches BITMAP_WORD in type, so the actual size | |
725 | of BITMAP_WORD is not material. */ | |
726 | count += __builtin_popcountl (elt->bits[ix]); | |
727 | #else | |
c22cacf3 | 728 | count += bitmap_popcount (elt->bits[ix]); |
1bc40c7e KZ |
729 | #endif |
730 | } | |
731 | } | |
732 | return count; | |
733 | } | |
c22cacf3 | 734 | |
76e910c6 RG |
735 | /* Return true if the bitmap has a single bit set. Otherwise return |
736 | false. */ | |
737 | ||
738 | bool | |
739 | bitmap_single_bit_set_p (const_bitmap a) | |
740 | { | |
741 | unsigned long count = 0; | |
742 | const bitmap_element *elt; | |
743 | unsigned ix; | |
744 | ||
745 | if (bitmap_empty_p (a)) | |
746 | return false; | |
747 | ||
748 | elt = a->first; | |
749 | /* As there are no completely empty bitmap elements, a second one | |
750 | means we have more than one bit set. */ | |
751 | if (elt->next != NULL) | |
752 | return false; | |
753 | ||
754 | for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
755 | { | |
756 | #if GCC_VERSION >= 3400 | |
757 | /* Note that popcountl matches BITMAP_WORD in type, so the actual size | |
758 | of BITMAP_WORD is not material. */ | |
759 | count += __builtin_popcountl (elt->bits[ix]); | |
760 | #else | |
761 | count += bitmap_popcount (elt->bits[ix]); | |
762 | #endif | |
763 | if (count > 1) | |
764 | return false; | |
765 | } | |
766 | ||
767 | return count == 1; | |
768 | } | |
1bc40c7e KZ |
769 | |
770 | ||
65a6f342 NS |
771 | /* Return the bit number of the first set bit in the bitmap. The |
772 | bitmap must be non-empty. */ | |
87e08c69 | 773 | |
65a6f342 | 774 | unsigned |
e326eeb5 | 775 | bitmap_first_set_bit (const_bitmap a) |
87e08c69 | 776 | { |
e326eeb5 | 777 | const bitmap_element *elt = a->first; |
65a6f342 | 778 | unsigned bit_no; |
72e42e26 | 779 | BITMAP_WORD word; |
65a6f342 | 780 | unsigned ix; |
c22cacf3 | 781 | |
377002a9 | 782 | gcc_checking_assert (elt); |
65a6f342 NS |
783 | bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; |
784 | for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
785 | { | |
786 | word = elt->bits[ix]; | |
787 | if (word) | |
788 | goto found_bit; | |
789 | } | |
298e6adc | 790 | gcc_unreachable (); |
65a6f342 NS |
791 | found_bit: |
792 | bit_no += ix * BITMAP_WORD_BITS; | |
87e08c69 | 793 | |
65a6f342 NS |
794 | #if GCC_VERSION >= 3004 |
795 | gcc_assert (sizeof(long) == sizeof (word)); | |
796 | bit_no += __builtin_ctzl (word); | |
87e08c69 | 797 | #else |
65a6f342 NS |
798 | /* Binary search for the first set bit. */ |
799 | #if BITMAP_WORD_BITS > 64 | |
800 | #error "Fill out the table." | |
87e08c69 | 801 | #endif |
65a6f342 NS |
802 | #if BITMAP_WORD_BITS > 32 |
803 | if (!(word & 0xffffffff)) | |
804 | word >>= 32, bit_no += 32; | |
87e08c69 | 805 | #endif |
65a6f342 NS |
806 | if (!(word & 0xffff)) |
807 | word >>= 16, bit_no += 16; | |
808 | if (!(word & 0xff)) | |
809 | word >>= 8, bit_no += 8; | |
810 | if (!(word & 0xf)) | |
811 | word >>= 4, bit_no += 4; | |
812 | if (!(word & 0x3)) | |
813 | word >>= 2, bit_no += 2; | |
814 | if (!(word & 0x1)) | |
815 | word >>= 1, bit_no += 1; | |
c22cacf3 | 816 | |
377002a9 | 817 | gcc_checking_assert (word & 1); |
87e08c69 | 818 | #endif |
65a6f342 | 819 | return bit_no; |
87e08c69 | 820 | } |
12802c2b JH |
821 | |
822 | /* Return the bit number of the first set bit in the bitmap. The | |
823 | bitmap must be non-empty. */ | |
824 | ||
825 | unsigned | |
826 | bitmap_last_set_bit (const_bitmap a) | |
827 | { | |
828 | const bitmap_element *elt = a->current ? a->current : a->first; | |
829 | unsigned bit_no; | |
830 | BITMAP_WORD word; | |
831 | int ix; | |
832 | ||
377002a9 | 833 | gcc_checking_assert (elt); |
12802c2b JH |
834 | while (elt->next) |
835 | elt = elt->next; | |
836 | bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; | |
837 | for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--) | |
838 | { | |
839 | word = elt->bits[ix]; | |
840 | if (word) | |
841 | goto found_bit; | |
842 | } | |
843 | gcc_unreachable (); | |
844 | found_bit: | |
845 | bit_no += ix * BITMAP_WORD_BITS; | |
846 | ||
847 | /* Binary search for the last set bit. */ | |
848 | #if GCC_VERSION >= 3004 | |
849 | gcc_assert (sizeof(long) == sizeof (word)); | |
850 | bit_no += sizeof (long) * 8 - __builtin_ctzl (word); | |
851 | #else | |
852 | #if BITMAP_WORD_BITS > 64 | |
853 | #error "Fill out the table." | |
854 | #endif | |
855 | #if BITMAP_WORD_BITS > 32 | |
856 | if ((word & 0xffffffff00000000)) | |
857 | word >>= 32, bit_no += 32; | |
858 | #endif | |
859 | if (word & 0xffff0000) | |
860 | word >>= 16, bit_no += 16; | |
861 | if (!(word & 0xff00)) | |
862 | word >>= 8, bit_no += 8; | |
863 | if (!(word & 0xf0)) | |
864 | word >>= 4, bit_no += 4; | |
865 | if (!(word & 12)) | |
866 | word >>= 2, bit_no += 2; | |
867 | if (!(word & 2)) | |
868 | word >>= 1, bit_no += 1; | |
869 | #endif | |
870 | ||
377002a9 | 871 | gcc_checking_assert (word & 1); |
12802c2b JH |
872 | return bit_no; |
873 | } | |
87e08c69 | 874 | \f |
096ab9ea | 875 | |
e28d0cfb | 876 | /* DST = A & B. */ |
88c4f655 NS |
877 | |
878 | void | |
e326eeb5 | 879 | bitmap_and (bitmap dst, const_bitmap a, const_bitmap b) |
096ab9ea | 880 | { |
88c4f655 | 881 | bitmap_element *dst_elt = dst->first; |
e326eeb5 KG |
882 | const bitmap_element *a_elt = a->first; |
883 | const bitmap_element *b_elt = b->first; | |
88c4f655 | 884 | bitmap_element *dst_prev = NULL; |
8229306b | 885 | |
08a3c5cd KZ |
886 | gcc_assert (dst != a && dst != b); |
887 | ||
888 | if (a == b) | |
889 | { | |
890 | bitmap_copy (dst, a); | |
891 | return; | |
892 | } | |
893 | ||
88c4f655 NS |
894 | while (a_elt && b_elt) |
895 | { | |
896 | if (a_elt->indx < b_elt->indx) | |
897 | a_elt = a_elt->next; | |
898 | else if (b_elt->indx < a_elt->indx) | |
899 | b_elt = b_elt->next; | |
900 | else | |
901 | { | |
902 | /* Matching elts, generate A & B. */ | |
903 | unsigned ix; | |
904 | BITMAP_WORD ior = 0; | |
905 | ||
906 | if (!dst_elt) | |
1bc40c7e | 907 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); |
c22cacf3 | 908 | else |
1bc40c7e | 909 | dst_elt->indx = a_elt->indx; |
a2b709cc | 910 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
88c4f655 NS |
911 | { |
912 | BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; | |
096ab9ea | 913 | |
88c4f655 NS |
914 | dst_elt->bits[ix] = r; |
915 | ior |= r; | |
916 | } | |
917 | if (ior) | |
918 | { | |
919 | dst_prev = dst_elt; | |
920 | dst_elt = dst_elt->next; | |
921 | } | |
922 | a_elt = a_elt->next; | |
923 | b_elt = b_elt->next; | |
924 | } | |
925 | } | |
5ce02e40 SP |
926 | /* Ensure that dst->current is valid. */ |
927 | dst->current = dst->first; | |
88c4f655 | 928 | bitmap_elt_clear_from (dst, dst_elt); |
7a40b8b1 | 929 | gcc_checking_assert (!dst->current == !dst->first); |
88c4f655 NS |
930 | if (dst->current) |
931 | dst->indx = dst->current->indx; | |
932 | } | |
933 | ||
934 | /* A &= B. */ | |
935 | ||
936 | void | |
e326eeb5 | 937 | bitmap_and_into (bitmap a, const_bitmap b) |
88c4f655 NS |
938 | { |
939 | bitmap_element *a_elt = a->first; | |
e326eeb5 | 940 | const bitmap_element *b_elt = b->first; |
88c4f655 | 941 | bitmap_element *next; |
096ab9ea | 942 | |
c22cacf3 | 943 | if (a == b) |
08a3c5cd KZ |
944 | return; |
945 | ||
88c4f655 | 946 | while (a_elt && b_elt) |
096ab9ea | 947 | { |
88c4f655 NS |
948 | if (a_elt->indx < b_elt->indx) |
949 | { | |
950 | next = a_elt->next; | |
951 | bitmap_element_free (a, a_elt); | |
952 | a_elt = next; | |
953 | } | |
954 | else if (b_elt->indx < a_elt->indx) | |
955 | b_elt = b_elt->next; | |
956 | else | |
096ab9ea | 957 | { |
88c4f655 NS |
958 | /* Matching elts, generate A &= B. */ |
959 | unsigned ix; | |
960 | BITMAP_WORD ior = 0; | |
961 | ||
a2b709cc | 962 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
88c4f655 NS |
963 | { |
964 | BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; | |
965 | ||
966 | a_elt->bits[ix] = r; | |
967 | ior |= r; | |
968 | } | |
969 | next = a_elt->next; | |
970 | if (!ior) | |
971 | bitmap_element_free (a, a_elt); | |
972 | a_elt = next; | |
973 | b_elt = b_elt->next; | |
096ab9ea | 974 | } |
88c4f655 NS |
975 | } |
976 | bitmap_elt_clear_from (a, a_elt); | |
7a40b8b1 JH |
977 | gcc_checking_assert (!a->current == !a->first |
978 | && (!a->current || a->indx == a->current->indx)); | |
88c4f655 NS |
979 | } |
980 | ||
6fb5fa3c DB |
981 | |
982 | /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT | |
983 | if non-NULL. CHANGED is true if the destination bitmap had already been | |
984 | changed; the new value of CHANGED is returned. */ | |
985 | ||
986 | static inline bool | |
987 | bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, | |
e326eeb5 | 988 | const bitmap_element *src_elt, bool changed) |
6fb5fa3c DB |
989 | { |
990 | if (!changed && dst_elt && dst_elt->indx == src_elt->indx) | |
991 | { | |
992 | unsigned ix; | |
993 | ||
a2b709cc | 994 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
6fb5fa3c DB |
995 | if (src_elt->bits[ix] != dst_elt->bits[ix]) |
996 | { | |
997 | dst_elt->bits[ix] = src_elt->bits[ix]; | |
998 | changed = true; | |
999 | } | |
1000 | } | |
1001 | else | |
1002 | { | |
1003 | changed = true; | |
1004 | if (!dst_elt) | |
1005 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, src_elt->indx); | |
1006 | else | |
1007 | dst_elt->indx = src_elt->indx; | |
1008 | memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits)); | |
1009 | } | |
1010 | return changed; | |
1011 | } | |
1012 | ||
1013 | ||
1014 | ||
88c4f655 NS |
1015 | /* DST = A & ~B */ |
1016 | ||
6fb5fa3c | 1017 | bool |
e326eeb5 | 1018 | bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b) |
88c4f655 NS |
1019 | { |
1020 | bitmap_element *dst_elt = dst->first; | |
e326eeb5 KG |
1021 | const bitmap_element *a_elt = a->first; |
1022 | const bitmap_element *b_elt = b->first; | |
88c4f655 | 1023 | bitmap_element *dst_prev = NULL; |
6fb5fa3c DB |
1024 | bitmap_element **dst_prev_pnext = &dst->first; |
1025 | bool changed = false; | |
88c4f655 | 1026 | |
08a3c5cd | 1027 | gcc_assert (dst != a && dst != b); |
c22cacf3 | 1028 | |
08a3c5cd KZ |
1029 | if (a == b) |
1030 | { | |
6fb5fa3c | 1031 | changed = !bitmap_empty_p (dst); |
08a3c5cd | 1032 | bitmap_clear (dst); |
6fb5fa3c | 1033 | return changed; |
08a3c5cd KZ |
1034 | } |
1035 | ||
88c4f655 NS |
1036 | while (a_elt) |
1037 | { | |
6fb5fa3c DB |
1038 | while (b_elt && b_elt->indx < a_elt->indx) |
1039 | b_elt = b_elt->next; | |
1040 | ||
1041 | if (!b_elt || b_elt->indx > a_elt->indx) | |
096ab9ea | 1042 | { |
6fb5fa3c DB |
1043 | changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed); |
1044 | dst_prev = *dst_prev_pnext; | |
1045 | dst_prev_pnext = &dst_prev->next; | |
1046 | dst_elt = *dst_prev_pnext; | |
88c4f655 | 1047 | a_elt = a_elt->next; |
096ab9ea | 1048 | } |
6fb5fa3c | 1049 | |
096ab9ea RK |
1050 | else |
1051 | { | |
88c4f655 NS |
1052 | /* Matching elts, generate A & ~B. */ |
1053 | unsigned ix; | |
1054 | BITMAP_WORD ior = 0; | |
1055 | ||
6fb5fa3c DB |
1056 | if (!changed && dst_elt && dst_elt->indx == a_elt->indx) |
1057 | { | |
a2b709cc | 1058 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
6fb5fa3c DB |
1059 | { |
1060 | BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; | |
1061 | ||
1062 | if (dst_elt->bits[ix] != r) | |
1063 | { | |
1064 | changed = true; | |
1065 | dst_elt->bits[ix] = r; | |
1066 | } | |
1067 | ior |= r; | |
1068 | } | |
1069 | } | |
c22cacf3 | 1070 | else |
88c4f655 | 1071 | { |
6fb5fa3c DB |
1072 | bool new_element; |
1073 | if (!dst_elt || dst_elt->indx > a_elt->indx) | |
1074 | { | |
1075 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); | |
1076 | new_element = true; | |
1077 | } | |
1078 | else | |
1079 | { | |
1080 | dst_elt->indx = a_elt->indx; | |
1081 | new_element = false; | |
1082 | } | |
88c4f655 | 1083 | |
a2b709cc | 1084 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
6fb5fa3c DB |
1085 | { |
1086 | BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; | |
1087 | ||
1088 | dst_elt->bits[ix] = r; | |
1089 | ior |= r; | |
1090 | } | |
1091 | ||
1092 | if (ior) | |
1093 | changed = true; | |
1094 | else | |
1095 | { | |
1096 | changed |= !new_element; | |
1097 | bitmap_element_free (dst, dst_elt); | |
1098 | dst_elt = *dst_prev_pnext; | |
1099 | } | |
88c4f655 | 1100 | } |
6fb5fa3c | 1101 | |
88c4f655 NS |
1102 | if (ior) |
1103 | { | |
6fb5fa3c DB |
1104 | dst_prev = *dst_prev_pnext; |
1105 | dst_prev_pnext = &dst_prev->next; | |
1106 | dst_elt = *dst_prev_pnext; | |
88c4f655 NS |
1107 | } |
1108 | a_elt = a_elt->next; | |
1109 | b_elt = b_elt->next; | |
096ab9ea | 1110 | } |
88c4f655 | 1111 | } |
6fb5fa3c | 1112 | |
5ce02e40 SP |
1113 | /* Ensure that dst->current is valid. */ |
1114 | dst->current = dst->first; | |
6fb5fa3c DB |
1115 | |
1116 | if (dst_elt) | |
1117 | { | |
1118 | changed = true; | |
1119 | bitmap_elt_clear_from (dst, dst_elt); | |
1120 | } | |
7a40b8b1 | 1121 | gcc_checking_assert (!dst->current == !dst->first); |
88c4f655 NS |
1122 | if (dst->current) |
1123 | dst->indx = dst->current->indx; | |
6fb5fa3c DB |
1124 | |
1125 | return changed; | |
88c4f655 NS |
1126 | } |
1127 | ||
90bb1c1f | 1128 | /* A &= ~B. Returns true if A changes */ |
096ab9ea | 1129 | |
90bb1c1f | 1130 | bool |
e326eeb5 | 1131 | bitmap_and_compl_into (bitmap a, const_bitmap b) |
88c4f655 NS |
1132 | { |
1133 | bitmap_element *a_elt = a->first; | |
e326eeb5 | 1134 | const bitmap_element *b_elt = b->first; |
88c4f655 | 1135 | bitmap_element *next; |
90bb1c1f | 1136 | BITMAP_WORD changed = 0; |
88c4f655 | 1137 | |
08a3c5cd KZ |
1138 | if (a == b) |
1139 | { | |
1140 | if (bitmap_empty_p (a)) | |
1141 | return false; | |
1142 | else | |
1143 | { | |
1144 | bitmap_clear (a); | |
1145 | return true; | |
1146 | } | |
1147 | } | |
1148 | ||
88c4f655 NS |
1149 | while (a_elt && b_elt) |
1150 | { | |
1151 | if (a_elt->indx < b_elt->indx) | |
1152 | a_elt = a_elt->next; | |
1153 | else if (b_elt->indx < a_elt->indx) | |
1154 | b_elt = b_elt->next; | |
1155 | else | |
8229306b | 1156 | { |
88c4f655 NS |
1157 | /* Matching elts, generate A &= ~B. */ |
1158 | unsigned ix; | |
1159 | BITMAP_WORD ior = 0; | |
1160 | ||
a2b709cc | 1161 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
88c4f655 | 1162 | { |
90bb1c1f NS |
1163 | BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; |
1164 | BITMAP_WORD r = a_elt->bits[ix] ^ cleared; | |
88c4f655 NS |
1165 | |
1166 | a_elt->bits[ix] = r; | |
90bb1c1f | 1167 | changed |= cleared; |
88c4f655 NS |
1168 | ior |= r; |
1169 | } | |
1170 | next = a_elt->next; | |
1171 | if (!ior) | |
1172 | bitmap_element_free (a, a_elt); | |
1173 | a_elt = next; | |
1174 | b_elt = b_elt->next; | |
8229306b | 1175 | } |
88c4f655 | 1176 | } |
7a40b8b1 JH |
1177 | gcc_checking_assert (!a->current == !a->first |
1178 | && (!a->current || a->indx == a->current->indx)); | |
90bb1c1f | 1179 | return changed != 0; |
88c4f655 NS |
1180 | } |
1181 | ||
6fb5fa3c DB |
1182 | /* Set COUNT bits from START in HEAD. */ |
1183 | void | |
1184 | bitmap_set_range (bitmap head, unsigned int start, unsigned int count) | |
1185 | { | |
1186 | unsigned int first_index, end_bit_plus1, last_index; | |
1187 | bitmap_element *elt, *elt_prev; | |
1188 | unsigned int i; | |
1189 | ||
1190 | if (!count) | |
1191 | return; | |
1192 | ||
1193 | first_index = start / BITMAP_ELEMENT_ALL_BITS; | |
1194 | end_bit_plus1 = start + count; | |
1195 | last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; | |
1196 | elt = bitmap_find_bit (head, start); | |
1197 | ||
1198 | /* If bitmap_find_bit returns zero, the current is the closest block | |
1199 | to the result. Otherwise, just use bitmap_element_allocate to | |
1200 | ensure ELT is set; in the loop below, ELT == NULL means "insert | |
1201 | at the end of the bitmap". */ | |
1202 | if (!elt) | |
1203 | { | |
1204 | elt = bitmap_element_allocate (head); | |
1205 | elt->indx = first_index; | |
1206 | bitmap_element_link (head, elt); | |
1207 | } | |
1208 | ||
377002a9 | 1209 | gcc_checking_assert (elt->indx == first_index); |
6fb5fa3c DB |
1210 | elt_prev = elt->prev; |
1211 | for (i = first_index; i <= last_index; i++) | |
1212 | { | |
1213 | unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS; | |
1214 | unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; | |
1215 | ||
1216 | unsigned int first_word_to_mod; | |
1217 | BITMAP_WORD first_mask; | |
1218 | unsigned int last_word_to_mod; | |
1219 | BITMAP_WORD last_mask; | |
1220 | unsigned int ix; | |
1221 | ||
1222 | if (!elt || elt->indx != i) | |
1223 | elt = bitmap_elt_insert_after (head, elt_prev, i); | |
1224 | ||
1225 | if (elt_start_bit <= start) | |
1226 | { | |
1227 | /* The first bit to turn on is somewhere inside this | |
1228 | elt. */ | |
1229 | first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS; | |
1230 | ||
1231 | /* This mask should have 1s in all bits >= start position. */ | |
1232 | first_mask = | |
1233 | (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1; | |
1234 | first_mask = ~first_mask; | |
1235 | } | |
1236 | else | |
1237 | { | |
1238 | /* The first bit to turn on is below this start of this elt. */ | |
1239 | first_word_to_mod = 0; | |
1240 | first_mask = ~(BITMAP_WORD) 0; | |
1241 | } | |
1242 | ||
1243 | if (elt_end_bit_plus1 <= end_bit_plus1) | |
1244 | { | |
1245 | /* The last bit to turn on is beyond this elt. */ | |
1246 | last_word_to_mod = BITMAP_ELEMENT_WORDS - 1; | |
1247 | last_mask = ~(BITMAP_WORD) 0; | |
1248 | } | |
1249 | else | |
1250 | { | |
1251 | /* The last bit to turn on is inside to this elt. */ | |
1252 | last_word_to_mod = | |
1253 | (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS; | |
1254 | ||
1255 | /* The last mask should have 1s below the end bit. */ | |
1256 | last_mask = | |
1257 | (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1; | |
1258 | } | |
1259 | ||
1260 | if (first_word_to_mod == last_word_to_mod) | |
1261 | { | |
1262 | BITMAP_WORD mask = first_mask & last_mask; | |
1263 | elt->bits[first_word_to_mod] |= mask; | |
1264 | } | |
1265 | else | |
1266 | { | |
1267 | elt->bits[first_word_to_mod] |= first_mask; | |
1268 | if (BITMAP_ELEMENT_WORDS > 2) | |
1269 | for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++) | |
1270 | elt->bits[ix] = ~(BITMAP_WORD) 0; | |
1271 | elt->bits[last_word_to_mod] |= last_mask; | |
1272 | } | |
1273 | ||
1274 | elt_prev = elt; | |
1275 | elt = elt->next; | |
1276 | } | |
1277 | ||
1278 | head->current = elt ? elt : elt_prev; | |
1279 | head->indx = head->current->indx; | |
1280 | } | |
1281 | ||
1bc40c7e KZ |
1282 | /* Clear COUNT bits from START in HEAD. */ |
1283 | void | |
1284 | bitmap_clear_range (bitmap head, unsigned int start, unsigned int count) | |
1285 | { | |
6fb5fa3c DB |
1286 | unsigned int first_index, end_bit_plus1, last_index; |
1287 | bitmap_element *elt; | |
1288 | ||
1289 | if (!count) | |
1290 | return; | |
1291 | ||
1292 | first_index = start / BITMAP_ELEMENT_ALL_BITS; | |
1293 | end_bit_plus1 = start + count; | |
1294 | last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; | |
1295 | elt = bitmap_find_bit (head, start); | |
1bc40c7e KZ |
1296 | |
1297 | /* If bitmap_find_bit returns zero, the current is the closest block | |
1298 | to the result. If the current is less than first index, find the | |
1299 | next one. Otherwise, just set elt to be current. */ | |
1300 | if (!elt) | |
c22cacf3 | 1301 | { |
1bc40c7e KZ |
1302 | if (head->current) |
1303 | { | |
1304 | if (head->indx < first_index) | |
1305 | { | |
1306 | elt = head->current->next; | |
1307 | if (!elt) | |
1308 | return; | |
1309 | } | |
c22cacf3 | 1310 | else |
1bc40c7e KZ |
1311 | elt = head->current; |
1312 | } | |
1313 | else | |
1314 | return; | |
1315 | } | |
1316 | ||
1317 | while (elt && (elt->indx <= last_index)) | |
1318 | { | |
1319 | bitmap_element * next_elt = elt->next; | |
1320 | unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS; | |
1321 | unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; | |
1322 | ||
1323 | ||
1324 | if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1) | |
1325 | /* Get rid of the entire elt and go to the next one. */ | |
1326 | bitmap_element_free (head, elt); | |
c22cacf3 | 1327 | else |
1bc40c7e KZ |
1328 | { |
1329 | /* Going to have to knock out some bits in this elt. */ | |
c22cacf3 MS |
1330 | unsigned int first_word_to_mod; |
1331 | BITMAP_WORD first_mask; | |
1bc40c7e KZ |
1332 | unsigned int last_word_to_mod; |
1333 | BITMAP_WORD last_mask; | |
1334 | unsigned int i; | |
1335 | bool clear = true; | |
1336 | ||
1337 | if (elt_start_bit <= start) | |
1338 | { | |
1339 | /* The first bit to turn off is somewhere inside this | |
1340 | elt. */ | |
1341 | first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS; | |
1342 | ||
1343 | /* This mask should have 1s in all bits >= start position. */ | |
c22cacf3 | 1344 | first_mask = |
1bc40c7e KZ |
1345 | (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1; |
1346 | first_mask = ~first_mask; | |
1347 | } | |
1348 | else | |
1349 | { | |
1350 | /* The first bit to turn off is below this start of this elt. */ | |
1351 | first_word_to_mod = 0; | |
1352 | first_mask = 0; | |
1353 | first_mask = ~first_mask; | |
c22cacf3 MS |
1354 | } |
1355 | ||
1bc40c7e KZ |
1356 | if (elt_end_bit_plus1 <= end_bit_plus1) |
1357 | { | |
1358 | /* The last bit to turn off is beyond this elt. */ | |
1359 | last_word_to_mod = BITMAP_ELEMENT_WORDS - 1; | |
1360 | last_mask = 0; | |
1361 | last_mask = ~last_mask; | |
1362 | } | |
1363 | else | |
1364 | { | |
1365 | /* The last bit to turn off is inside to this elt. */ | |
c22cacf3 | 1366 | last_word_to_mod = |
1bc40c7e KZ |
1367 | (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS; |
1368 | ||
1369 | /* The last mask should have 1s below the end bit. */ | |
c22cacf3 | 1370 | last_mask = |
1bc40c7e KZ |
1371 | (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1; |
1372 | } | |
1373 | ||
1374 | ||
1375 | if (first_word_to_mod == last_word_to_mod) | |
1376 | { | |
1377 | BITMAP_WORD mask = first_mask & last_mask; | |
1378 | elt->bits[first_word_to_mod] &= ~mask; | |
1379 | } | |
1380 | else | |
1381 | { | |
1382 | elt->bits[first_word_to_mod] &= ~first_mask; | |
6fb5fa3c DB |
1383 | if (BITMAP_ELEMENT_WORDS > 2) |
1384 | for (i = first_word_to_mod + 1; i < last_word_to_mod; i++) | |
1385 | elt->bits[i] = 0; | |
1bc40c7e KZ |
1386 | elt->bits[last_word_to_mod] &= ~last_mask; |
1387 | } | |
1388 | for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
1389 | if (elt->bits[i]) | |
1390 | { | |
1391 | clear = false; | |
1392 | break; | |
1393 | } | |
1394 | /* Check to see if there are any bits left. */ | |
1395 | if (clear) | |
1396 | bitmap_element_free (head, elt); | |
1397 | } | |
1398 | elt = next_elt; | |
1399 | } | |
c22cacf3 | 1400 | |
1bc40c7e KZ |
1401 | if (elt) |
1402 | { | |
1403 | head->current = elt; | |
1404 | head->indx = head->current->indx; | |
1405 | } | |
1406 | } | |
1407 | ||
1408 | /* A = ~A & B. */ | |
1409 | ||
1410 | void | |
e326eeb5 | 1411 | bitmap_compl_and_into (bitmap a, const_bitmap b) |
1bc40c7e KZ |
1412 | { |
1413 | bitmap_element *a_elt = a->first; | |
e326eeb5 | 1414 | const bitmap_element *b_elt = b->first; |
1bc40c7e KZ |
1415 | bitmap_element *a_prev = NULL; |
1416 | bitmap_element *next; | |
1417 | ||
1418 | gcc_assert (a != b); | |
1419 | ||
1420 | if (bitmap_empty_p (a)) | |
1421 | { | |
1422 | bitmap_copy (a, b); | |
1423 | return; | |
1424 | } | |
1425 | if (bitmap_empty_p (b)) | |
1426 | { | |
1427 | bitmap_clear (a); | |
1428 | return; | |
1429 | } | |
1430 | ||
1431 | while (a_elt || b_elt) | |
1432 | { | |
1433 | if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) | |
1434 | { | |
1435 | /* A is before B. Remove A */ | |
1436 | next = a_elt->next; | |
1437 | a_prev = a_elt->prev; | |
1438 | bitmap_element_free (a, a_elt); | |
1439 | a_elt = next; | |
1440 | } | |
1441 | else if (!a_elt || b_elt->indx < a_elt->indx) | |
1442 | { | |
1443 | /* B is before A. Copy B. */ | |
1444 | next = bitmap_elt_insert_after (a, a_prev, b_elt->indx); | |
1445 | memcpy (next->bits, b_elt->bits, sizeof (next->bits)); | |
1446 | a_prev = next; | |
1447 | b_elt = b_elt->next; | |
1448 | } | |
1449 | else | |
1450 | { | |
1451 | /* Matching elts, generate A = ~A & B. */ | |
1452 | unsigned ix; | |
1453 | BITMAP_WORD ior = 0; | |
1454 | ||
a2b709cc | 1455 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
1bc40c7e KZ |
1456 | { |
1457 | BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; | |
1458 | BITMAP_WORD r = b_elt->bits[ix] ^ cleared; | |
1459 | ||
1460 | a_elt->bits[ix] = r; | |
1461 | ior |= r; | |
1462 | } | |
1463 | next = a_elt->next; | |
1464 | if (!ior) | |
1465 | bitmap_element_free (a, a_elt); | |
1466 | else | |
1467 | a_prev = a_elt; | |
1468 | a_elt = next; | |
1469 | b_elt = b_elt->next; | |
1470 | } | |
1471 | } | |
7a40b8b1 JH |
1472 | gcc_checking_assert (!a->current == !a->first |
1473 | && (!a->current || a->indx == a->current->indx)); | |
1bc40c7e KZ |
1474 | return; |
1475 | } | |
1476 | ||
6fb5fa3c DB |
1477 | |
1478 | /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV, | |
1479 | overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap | |
1480 | had already been changed; the new value of CHANGED is returned. */ | |
1481 | ||
1482 | static inline bool | |
1483 | bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, | |
e326eeb5 | 1484 | const bitmap_element *a_elt, const bitmap_element *b_elt, |
6fb5fa3c DB |
1485 | bool changed) |
1486 | { | |
1487 | gcc_assert (a_elt || b_elt); | |
1488 | ||
1489 | if (a_elt && b_elt && a_elt->indx == b_elt->indx) | |
1490 | { | |
1491 | /* Matching elts, generate A | B. */ | |
1492 | unsigned ix; | |
1493 | ||
1494 | if (!changed && dst_elt && dst_elt->indx == a_elt->indx) | |
1495 | { | |
a2b709cc | 1496 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
6fb5fa3c DB |
1497 | { |
1498 | BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; | |
1499 | if (r != dst_elt->bits[ix]) | |
1500 | { | |
1501 | dst_elt->bits[ix] = r; | |
1502 | changed = true; | |
1503 | } | |
1504 | } | |
1505 | } | |
1506 | else | |
1507 | { | |
1508 | changed = true; | |
1509 | if (!dst_elt) | |
1510 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); | |
1511 | else | |
1512 | dst_elt->indx = a_elt->indx; | |
a2b709cc | 1513 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
6fb5fa3c DB |
1514 | { |
1515 | BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; | |
1516 | dst_elt->bits[ix] = r; | |
1517 | } | |
1518 | } | |
1519 | } | |
1520 | else | |
1521 | { | |
1522 | /* Copy a single element. */ | |
e326eeb5 | 1523 | const bitmap_element *src; |
6fb5fa3c DB |
1524 | |
1525 | if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) | |
1526 | src = a_elt; | |
1527 | else | |
1528 | src = b_elt; | |
1529 | ||
377002a9 | 1530 | gcc_checking_assert (src); |
6fb5fa3c DB |
1531 | changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed); |
1532 | } | |
1533 | return changed; | |
1534 | } | |
1535 | ||
1536 | ||
88c4f655 NS |
1537 | /* DST = A | B. Return true if DST changes. */ |
1538 | ||
1539 | bool | |
e326eeb5 | 1540 | bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b) |
88c4f655 NS |
1541 | { |
1542 | bitmap_element *dst_elt = dst->first; | |
e326eeb5 KG |
1543 | const bitmap_element *a_elt = a->first; |
1544 | const bitmap_element *b_elt = b->first; | |
88c4f655 | 1545 | bitmap_element *dst_prev = NULL; |
6fb5fa3c | 1546 | bitmap_element **dst_prev_pnext = &dst->first; |
c22cacf3 | 1547 | bool changed = false; |
88c4f655 | 1548 | |
08a3c5cd KZ |
1549 | gcc_assert (dst != a && dst != b); |
1550 | ||
88c4f655 NS |
1551 | while (a_elt || b_elt) |
1552 | { | |
6fb5fa3c DB |
1553 | changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed); |
1554 | ||
88c4f655 | 1555 | if (a_elt && b_elt && a_elt->indx == b_elt->indx) |
8229306b | 1556 | { |
88c4f655 NS |
1557 | a_elt = a_elt->next; |
1558 | b_elt = b_elt->next; | |
8229306b RH |
1559 | } |
1560 | else | |
096ab9ea | 1561 | { |
6fb5fa3c DB |
1562 | if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx)) |
1563 | a_elt = a_elt->next; | |
1564 | else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx)) | |
1565 | b_elt = b_elt->next; | |
096ab9ea | 1566 | } |
6fb5fa3c DB |
1567 | |
1568 | dst_prev = *dst_prev_pnext; | |
1569 | dst_prev_pnext = &dst_prev->next; | |
1570 | dst_elt = *dst_prev_pnext; | |
88c4f655 NS |
1571 | } |
1572 | ||
1573 | if (dst_elt) | |
1574 | { | |
1575 | changed = true; | |
1576 | bitmap_elt_clear_from (dst, dst_elt); | |
1577 | } | |
7a40b8b1 | 1578 | gcc_checking_assert (!dst->current == !dst->first); |
88c4f655 NS |
1579 | if (dst->current) |
1580 | dst->indx = dst->current->indx; | |
1581 | return changed; | |
1582 | } | |
096ab9ea | 1583 | |
88c4f655 NS |
1584 | /* A |= B. Return true if A changes. */ |
1585 | ||
1586 | bool | |
e326eeb5 | 1587 | bitmap_ior_into (bitmap a, const_bitmap b) |
88c4f655 NS |
1588 | { |
1589 | bitmap_element *a_elt = a->first; | |
e326eeb5 | 1590 | const bitmap_element *b_elt = b->first; |
88c4f655 | 1591 | bitmap_element *a_prev = NULL; |
6fb5fa3c | 1592 | bitmap_element **a_prev_pnext = &a->first; |
88c4f655 NS |
1593 | bool changed = false; |
1594 | ||
08a3c5cd KZ |
1595 | if (a == b) |
1596 | return false; | |
1597 | ||
88c4f655 NS |
1598 | while (b_elt) |
1599 | { | |
6fb5fa3c DB |
1600 | /* If A lags behind B, just advance it. */ |
1601 | if (!a_elt || a_elt->indx == b_elt->indx) | |
88c4f655 | 1602 | { |
6fb5fa3c | 1603 | changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed); |
88c4f655 | 1604 | b_elt = b_elt->next; |
b9a73e32 | 1605 | } |
6fb5fa3c | 1606 | else if (a_elt->indx > b_elt->indx) |
b9a73e32 | 1607 | { |
6fb5fa3c | 1608 | changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed); |
88c4f655 | 1609 | b_elt = b_elt->next; |
096ab9ea | 1610 | } |
6fb5fa3c DB |
1611 | |
1612 | a_prev = *a_prev_pnext; | |
1613 | a_prev_pnext = &a_prev->next; | |
1614 | a_elt = *a_prev_pnext; | |
096ab9ea | 1615 | } |
6fb5fa3c | 1616 | |
7a40b8b1 | 1617 | gcc_checking_assert (!a->current == !a->first); |
88c4f655 NS |
1618 | if (a->current) |
1619 | a->indx = a->current->indx; | |
1620 | return changed; | |
1621 | } | |
1622 | ||
1623 | /* DST = A ^ B */ | |
096ab9ea | 1624 | |
88c4f655 | 1625 | void |
e326eeb5 | 1626 | bitmap_xor (bitmap dst, const_bitmap a, const_bitmap b) |
88c4f655 NS |
1627 | { |
1628 | bitmap_element *dst_elt = dst->first; | |
e326eeb5 KG |
1629 | const bitmap_element *a_elt = a->first; |
1630 | const bitmap_element *b_elt = b->first; | |
88c4f655 NS |
1631 | bitmap_element *dst_prev = NULL; |
1632 | ||
08a3c5cd KZ |
1633 | gcc_assert (dst != a && dst != b); |
1634 | if (a == b) | |
1635 | { | |
1636 | bitmap_clear (dst); | |
1637 | return; | |
1638 | } | |
1639 | ||
88c4f655 | 1640 | while (a_elt || b_elt) |
096ab9ea | 1641 | { |
88c4f655 | 1642 | if (a_elt && b_elt && a_elt->indx == b_elt->indx) |
e2500fed | 1643 | { |
88c4f655 NS |
1644 | /* Matching elts, generate A ^ B. */ |
1645 | unsigned ix; | |
1646 | BITMAP_WORD ior = 0; | |
1647 | ||
1648 | if (!dst_elt) | |
1bc40c7e KZ |
1649 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); |
1650 | else | |
1651 | dst_elt->indx = a_elt->indx; | |
a2b709cc | 1652 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
88c4f655 NS |
1653 | { |
1654 | BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; | |
1655 | ||
1656 | ior |= r; | |
1657 | dst_elt->bits[ix] = r; | |
1658 | } | |
1659 | a_elt = a_elt->next; | |
1660 | b_elt = b_elt->next; | |
1661 | if (ior) | |
1662 | { | |
1663 | dst_prev = dst_elt; | |
1664 | dst_elt = dst_elt->next; | |
1665 | } | |
e2500fed GK |
1666 | } |
1667 | else | |
1668 | { | |
88c4f655 | 1669 | /* Copy a single element. */ |
e326eeb5 | 1670 | const bitmap_element *src; |
88c4f655 NS |
1671 | |
1672 | if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) | |
1673 | { | |
1674 | src = a_elt; | |
1675 | a_elt = a_elt->next; | |
1676 | } | |
1677 | else | |
1678 | { | |
1679 | src = b_elt; | |
1680 | b_elt = b_elt->next; | |
1681 | } | |
1682 | ||
1683 | if (!dst_elt) | |
1bc40c7e | 1684 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx); |
c22cacf3 | 1685 | else |
1bc40c7e | 1686 | dst_elt->indx = src->indx; |
88c4f655 NS |
1687 | memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits)); |
1688 | dst_prev = dst_elt; | |
1689 | dst_elt = dst_elt->next; | |
e2500fed | 1690 | } |
096ab9ea | 1691 | } |
5ce02e40 SP |
1692 | /* Ensure that dst->current is valid. */ |
1693 | dst->current = dst->first; | |
88c4f655 | 1694 | bitmap_elt_clear_from (dst, dst_elt); |
7a40b8b1 | 1695 | gcc_checking_assert (!dst->current == !dst->first); |
88c4f655 NS |
1696 | if (dst->current) |
1697 | dst->indx = dst->current->indx; | |
1698 | } | |
096ab9ea | 1699 | |
88c4f655 | 1700 | /* A ^= B */ |
8229306b | 1701 | |
88c4f655 | 1702 | void |
e326eeb5 | 1703 | bitmap_xor_into (bitmap a, const_bitmap b) |
88c4f655 NS |
1704 | { |
1705 | bitmap_element *a_elt = a->first; | |
e326eeb5 | 1706 | const bitmap_element *b_elt = b->first; |
88c4f655 NS |
1707 | bitmap_element *a_prev = NULL; |
1708 | ||
08a3c5cd KZ |
1709 | if (a == b) |
1710 | { | |
1711 | bitmap_clear (a); | |
1712 | return; | |
1713 | } | |
1714 | ||
88c4f655 NS |
1715 | while (b_elt) |
1716 | { | |
1717 | if (!a_elt || b_elt->indx < a_elt->indx) | |
1718 | { | |
1719 | /* Copy b_elt. */ | |
1bc40c7e | 1720 | bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx); |
88c4f655 NS |
1721 | memcpy (dst->bits, b_elt->bits, sizeof (dst->bits)); |
1722 | a_prev = dst; | |
1723 | b_elt = b_elt->next; | |
1724 | } | |
1725 | else if (a_elt->indx < b_elt->indx) | |
1726 | { | |
1727 | a_prev = a_elt; | |
1728 | a_elt = a_elt->next; | |
1729 | } | |
1730 | else | |
1731 | { | |
1732 | /* Matching elts, generate A ^= B. */ | |
1733 | unsigned ix; | |
1734 | BITMAP_WORD ior = 0; | |
1735 | bitmap_element *next = a_elt->next; | |
1736 | ||
a2b709cc | 1737 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
88c4f655 NS |
1738 | { |
1739 | BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; | |
1740 | ||
1741 | ior |= r; | |
1742 | a_elt->bits[ix] = r; | |
1743 | } | |
1744 | b_elt = b_elt->next; | |
1745 | if (ior) | |
1746 | a_prev = a_elt; | |
1747 | else | |
1748 | bitmap_element_free (a, a_elt); | |
1749 | a_elt = next; | |
1750 | } | |
1751 | } | |
7a40b8b1 | 1752 | gcc_checking_assert (!a->current == !a->first); |
88c4f655 NS |
1753 | if (a->current) |
1754 | a->indx = a->current->indx; | |
8229306b RH |
1755 | } |
1756 | ||
55994078 NS |
1757 | /* Return true if two bitmaps are identical. |
1758 | We do not bother with a check for pointer equality, as that never | |
1759 | occurs in practice. */ | |
8229306b | 1760 | |
55994078 | 1761 | bool |
e326eeb5 | 1762 | bitmap_equal_p (const_bitmap a, const_bitmap b) |
8229306b | 1763 | { |
e326eeb5 KG |
1764 | const bitmap_element *a_elt; |
1765 | const bitmap_element *b_elt; | |
55994078 | 1766 | unsigned ix; |
c22cacf3 | 1767 | |
55994078 NS |
1768 | for (a_elt = a->first, b_elt = b->first; |
1769 | a_elt && b_elt; | |
1770 | a_elt = a_elt->next, b_elt = b_elt->next) | |
1771 | { | |
1772 | if (a_elt->indx != b_elt->indx) | |
1773 | return false; | |
a2b709cc | 1774 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
55994078 NS |
1775 | if (a_elt->bits[ix] != b_elt->bits[ix]) |
1776 | return false; | |
1777 | } | |
1778 | return !a_elt && !b_elt; | |
1779 | } | |
1780 | ||
1781 | /* Return true if A AND B is not empty. */ | |
1782 | ||
1783 | bool | |
e326eeb5 | 1784 | bitmap_intersect_p (const_bitmap a, const_bitmap b) |
55994078 | 1785 | { |
e326eeb5 KG |
1786 | const bitmap_element *a_elt; |
1787 | const bitmap_element *b_elt; | |
55994078 | 1788 | unsigned ix; |
c22cacf3 | 1789 | |
55994078 NS |
1790 | for (a_elt = a->first, b_elt = b->first; |
1791 | a_elt && b_elt;) | |
1792 | { | |
1793 | if (a_elt->indx < b_elt->indx) | |
1794 | a_elt = a_elt->next; | |
1795 | else if (b_elt->indx < a_elt->indx) | |
1796 | b_elt = b_elt->next; | |
1797 | else | |
1798 | { | |
a2b709cc | 1799 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
55994078 NS |
1800 | if (a_elt->bits[ix] & b_elt->bits[ix]) |
1801 | return true; | |
1802 | a_elt = a_elt->next; | |
1803 | b_elt = b_elt->next; | |
1804 | } | |
1805 | } | |
1806 | return false; | |
1807 | } | |
8229306b | 1808 | |
55994078 | 1809 | /* Return true if A AND NOT B is not empty. */ |
8229306b | 1810 | |
55994078 | 1811 | bool |
e326eeb5 | 1812 | bitmap_intersect_compl_p (const_bitmap a, const_bitmap b) |
55994078 | 1813 | { |
e326eeb5 KG |
1814 | const bitmap_element *a_elt; |
1815 | const bitmap_element *b_elt; | |
55994078 NS |
1816 | unsigned ix; |
1817 | for (a_elt = a->first, b_elt = b->first; | |
1818 | a_elt && b_elt;) | |
1819 | { | |
1820 | if (a_elt->indx < b_elt->indx) | |
1821 | return true; | |
1822 | else if (b_elt->indx < a_elt->indx) | |
1823 | b_elt = b_elt->next; | |
1824 | else | |
1825 | { | |
a2b709cc | 1826 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
55994078 NS |
1827 | if (a_elt->bits[ix] & ~b_elt->bits[ix]) |
1828 | return true; | |
1829 | a_elt = a_elt->next; | |
1830 | b_elt = b_elt->next; | |
1831 | } | |
1832 | } | |
1833 | return a_elt != NULL; | |
096ab9ea | 1834 | } |
55994078 | 1835 | |
096ab9ea | 1836 | \f |
88c4f655 | 1837 | /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */ |
096ab9ea | 1838 | |
7ef7b345 | 1839 | bool |
e326eeb5 | 1840 | bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill) |
096ab9ea | 1841 | { |
6fb5fa3c | 1842 | bool changed = false; |
7932a3db | 1843 | |
6fb5fa3c | 1844 | bitmap_element *dst_elt = dst->first; |
e326eeb5 KG |
1845 | const bitmap_element *a_elt = a->first; |
1846 | const bitmap_element *b_elt = b->first; | |
1847 | const bitmap_element *kill_elt = kill->first; | |
6fb5fa3c DB |
1848 | bitmap_element *dst_prev = NULL; |
1849 | bitmap_element **dst_prev_pnext = &dst->first; | |
1850 | ||
1851 | gcc_assert (dst != a && dst != b && dst != kill); | |
1852 | ||
1853 | /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */ | |
1854 | if (b == kill || bitmap_empty_p (b)) | |
1855 | { | |
1856 | changed = !bitmap_equal_p (dst, a); | |
1857 | if (changed) | |
1858 | bitmap_copy (dst, a); | |
1859 | return changed; | |
1860 | } | |
1861 | if (bitmap_empty_p (kill)) | |
1862 | return bitmap_ior (dst, a, b); | |
1863 | if (bitmap_empty_p (a)) | |
1864 | return bitmap_and_compl (dst, b, kill); | |
1865 | ||
1866 | while (a_elt || b_elt) | |
1867 | { | |
1868 | bool new_element = false; | |
1869 | ||
1870 | if (b_elt) | |
1871 | while (kill_elt && kill_elt->indx < b_elt->indx) | |
1872 | kill_elt = kill_elt->next; | |
1873 | ||
1874 | if (b_elt && kill_elt && kill_elt->indx == b_elt->indx | |
1875 | && (!a_elt || a_elt->indx >= b_elt->indx)) | |
1876 | { | |
1877 | bitmap_element tmp_elt; | |
1878 | unsigned ix; | |
1879 | ||
1880 | BITMAP_WORD ior = 0; | |
1881 | tmp_elt.indx = b_elt->indx; | |
a2b709cc | 1882 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
6fb5fa3c DB |
1883 | { |
1884 | BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix]; | |
1885 | ior |= r; | |
1886 | tmp_elt.bits[ix] = r; | |
1887 | } | |
1888 | ||
1889 | if (ior) | |
1890 | { | |
1891 | changed = bitmap_elt_ior (dst, dst_elt, dst_prev, | |
1892 | a_elt, &tmp_elt, changed); | |
1893 | new_element = true; | |
1894 | if (a_elt && a_elt->indx == b_elt->indx) | |
1895 | a_elt = a_elt->next; | |
1896 | } | |
1897 | ||
1898 | b_elt = b_elt->next; | |
1899 | kill_elt = kill_elt->next; | |
1900 | } | |
1901 | else | |
1902 | { | |
1903 | changed = bitmap_elt_ior (dst, dst_elt, dst_prev, | |
1904 | a_elt, b_elt, changed); | |
1905 | new_element = true; | |
1906 | ||
1907 | if (a_elt && b_elt && a_elt->indx == b_elt->indx) | |
1908 | { | |
1909 | a_elt = a_elt->next; | |
1910 | b_elt = b_elt->next; | |
1911 | } | |
1912 | else | |
1913 | { | |
1914 | if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx)) | |
1915 | a_elt = a_elt->next; | |
1916 | else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx)) | |
1917 | b_elt = b_elt->next; | |
1918 | } | |
1919 | } | |
1920 | ||
1921 | if (new_element) | |
1922 | { | |
1923 | dst_prev = *dst_prev_pnext; | |
1924 | dst_prev_pnext = &dst_prev->next; | |
1925 | dst_elt = *dst_prev_pnext; | |
1926 | } | |
1927 | } | |
1928 | ||
1929 | if (dst_elt) | |
1930 | { | |
1931 | changed = true; | |
1932 | bitmap_elt_clear_from (dst, dst_elt); | |
1933 | } | |
7a40b8b1 | 1934 | gcc_checking_assert (!dst->current == !dst->first); |
6fb5fa3c DB |
1935 | if (dst->current) |
1936 | dst->indx = dst->current->indx; | |
88c4f655 | 1937 | |
eb59b8de | 1938 | return changed; |
096ab9ea | 1939 | } |
87e08c69 | 1940 | |
88c4f655 | 1941 | /* A |= (FROM1 & ~FROM2). Return true if A changes. */ |
7ef7b345 NS |
1942 | |
1943 | bool | |
e326eeb5 | 1944 | bitmap_ior_and_compl_into (bitmap a, const_bitmap from1, const_bitmap from2) |
87e08c69 RH |
1945 | { |
1946 | bitmap_head tmp; | |
88c4f655 | 1947 | bool changed; |
c22cacf3 | 1948 | |
7932a3db | 1949 | bitmap_initialize (&tmp, &bitmap_default_obstack); |
88c4f655 NS |
1950 | bitmap_and_compl (&tmp, from1, from2); |
1951 | changed = bitmap_ior_into (a, &tmp); | |
87e08c69 RH |
1952 | bitmap_clear (&tmp); |
1953 | ||
1954 | return changed; | |
1955 | } | |
6fb5fa3c | 1956 | |
7ff23740 PB |
1957 | /* A |= (B & C). Return true if A changes. */ |
1958 | ||
1959 | bool | |
1960 | bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c) | |
1961 | { | |
1962 | bitmap_element *a_elt = a->first; | |
1963 | const bitmap_element *b_elt = b->first; | |
1964 | const bitmap_element *c_elt = c->first; | |
1965 | bitmap_element and_elt; | |
1966 | bitmap_element *a_prev = NULL; | |
1967 | bitmap_element **a_prev_pnext = &a->first; | |
1968 | bool changed = false; | |
1969 | unsigned ix; | |
1970 | ||
1971 | if (b == c) | |
1972 | return bitmap_ior_into (a, b); | |
1973 | if (bitmap_empty_p (b) || bitmap_empty_p (c)) | |
1974 | return false; | |
1975 | ||
1976 | and_elt.indx = -1; | |
1977 | while (b_elt && c_elt) | |
1978 | { | |
1979 | BITMAP_WORD overall; | |
1980 | ||
1981 | /* Find a common item of B and C. */ | |
1982 | while (b_elt->indx != c_elt->indx) | |
1983 | { | |
1984 | if (b_elt->indx < c_elt->indx) | |
1985 | { | |
1986 | b_elt = b_elt->next; | |
1987 | if (!b_elt) | |
1988 | goto done; | |
1989 | } | |
1990 | else | |
1991 | { | |
1992 | c_elt = c_elt->next; | |
1993 | if (!c_elt) | |
1994 | goto done; | |
1995 | } | |
1996 | } | |
1997 | ||
1998 | overall = 0; | |
1999 | and_elt.indx = b_elt->indx; | |
a2b709cc | 2000 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
7ff23740 PB |
2001 | { |
2002 | and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix]; | |
2003 | overall |= and_elt.bits[ix]; | |
2004 | } | |
2005 | ||
2006 | b_elt = b_elt->next; | |
2007 | c_elt = c_elt->next; | |
2008 | if (!overall) | |
2009 | continue; | |
2010 | ||
2011 | /* Now find a place to insert AND_ELT. */ | |
2012 | do | |
2013 | { | |
2014 | ix = a_elt ? a_elt->indx : and_elt.indx; | |
2015 | if (ix == and_elt.indx) | |
2016 | changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed); | |
2017 | else if (ix > and_elt.indx) | |
2018 | changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed); | |
2019 | ||
2020 | a_prev = *a_prev_pnext; | |
2021 | a_prev_pnext = &a_prev->next; | |
2022 | a_elt = *a_prev_pnext; | |
2023 | ||
2024 | /* If A lagged behind B/C, we advanced it so loop once more. */ | |
2025 | } | |
2026 | while (ix < and_elt.indx); | |
2027 | } | |
2028 | ||
2029 | done: | |
7a40b8b1 | 2030 | gcc_checking_assert (!a->current == !a->first); |
7ff23740 PB |
2031 | if (a->current) |
2032 | a->indx = a->current->indx; | |
2033 | return changed; | |
2034 | } | |
096ab9ea | 2035 | \f |
096ab9ea RK |
2036 | /* Debugging function to print out the contents of a bitmap. */ |
2037 | ||
24e47c76 | 2038 | DEBUG_FUNCTION void |
e326eeb5 | 2039 | debug_bitmap_file (FILE *file, const_bitmap head) |
096ab9ea | 2040 | { |
e326eeb5 | 2041 | const bitmap_element *ptr; |
096ab9ea | 2042 | |
edb89024 DR |
2043 | fprintf (file, "\nfirst = " HOST_PTR_PRINTF |
2044 | " current = " HOST_PTR_PRINTF " indx = %u\n", | |
75b6f3fd | 2045 | (void *) head->first, (void *) head->current, head->indx); |
096ab9ea RK |
2046 | |
2047 | for (ptr = head->first; ptr; ptr = ptr->next) | |
2048 | { | |
72e42e26 | 2049 | unsigned int i, j, col = 26; |
096ab9ea | 2050 | |
edb89024 DR |
2051 | fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF |
2052 | " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {", | |
e326eeb5 KG |
2053 | (const void*) ptr, (const void*) ptr->next, |
2054 | (const void*) ptr->prev, ptr->indx); | |
096ab9ea RK |
2055 | |
2056 | for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
72e42e26 | 2057 | for (j = 0; j < BITMAP_WORD_BITS; j++) |
8229306b | 2058 | if ((ptr->bits[i] >> j) & 1) |
096ab9ea RK |
2059 | { |
2060 | if (col > 70) | |
2061 | { | |
2062 | fprintf (file, "\n\t\t\t"); | |
2063 | col = 24; | |
2064 | } | |
2065 | ||
2066 | fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS | |
72e42e26 | 2067 | + i * BITMAP_WORD_BITS + j)); |
096ab9ea RK |
2068 | col += 4; |
2069 | } | |
2070 | ||
2071 | fprintf (file, " }\n"); | |
2072 | } | |
2073 | } | |
a615c28a | 2074 | |
096ab9ea RK |
2075 | /* Function to be called from the debugger to print the contents |
2076 | of a bitmap. */ | |
2077 | ||
24e47c76 | 2078 | DEBUG_FUNCTION void |
e326eeb5 | 2079 | debug_bitmap (const_bitmap head) |
096ab9ea | 2080 | { |
bfd38496 | 2081 | debug_bitmap_file (stdout, head); |
096ab9ea | 2082 | } |
a615c28a | 2083 | |
bfd38496 | 2084 | /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file, |
22fa5b8a MM |
2085 | it does not print anything but the bits. */ |
2086 | ||
24e47c76 | 2087 | DEBUG_FUNCTION void |
e326eeb5 | 2088 | bitmap_print (FILE *file, const_bitmap head, const char *prefix, const char *suffix) |
22fa5b8a | 2089 | { |
5d5993dd | 2090 | const char *comma = ""; |
3cd8c58a | 2091 | unsigned i; |
87c476a2 | 2092 | bitmap_iterator bi; |
22fa5b8a MM |
2093 | |
2094 | fputs (prefix, file); | |
87c476a2 ZD |
2095 | EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi) |
2096 | { | |
2097 | fprintf (file, "%s%d", comma, i); | |
2098 | comma = ", "; | |
2099 | } | |
22fa5b8a MM |
2100 | fputs (suffix, file); |
2101 | } | |
f75709c6 JH |
2102 | #ifdef GATHER_STATISTICS |
2103 | ||
2104 | ||
2105 | /* Used to accumulate statistics about bitmap sizes. */ | |
2106 | struct output_info | |
2107 | { | |
e2d87023 | 2108 | HOST_WIDEST_INT size; |
f75709c6 | 2109 | int count; |
f75709c6 JH |
2110 | }; |
2111 | ||
2112 | /* Called via htab_traverse. Output bitmap descriptor pointed out by SLOT | |
2113 | and update statistics. */ | |
2114 | static int | |
2115 | print_statistics (void **slot, void *b) | |
2116 | { | |
2117 | struct bitmap_descriptor *d = (struct bitmap_descriptor *) *slot; | |
2118 | struct output_info *i = (struct output_info *) b; | |
2119 | char s[4096]; | |
2120 | ||
2121 | if (d->allocated) | |
2122 | { | |
2123 | const char *s1 = d->file; | |
2124 | const char *s2; | |
2125 | while ((s2 = strstr (s1, "gcc/"))) | |
2126 | s1 = s2 + 4; | |
2127 | sprintf (s, "%s:%i (%s)", s1, d->line, d->function); | |
2128 | s[41] = 0; | |
e2d87023 | 2129 | fprintf (stderr, "%-41s %8d %15"HOST_WIDEST_INT_PRINT"d %15" |
d4fb676f JH |
2130 | HOST_WIDEST_INT_PRINT"d %15"HOST_WIDEST_INT_PRINT"d %10d %10d\n", |
2131 | s, d->created, d->allocated, d->peak, d->current, d->nsearches, | |
2132 | d->search_iter); | |
f75709c6 JH |
2133 | i->size += d->allocated; |
2134 | i->count += d->created; | |
2135 | } | |
2136 | return 1; | |
2137 | } | |
2138 | #endif | |
2139 | /* Output per-bitmap memory usage statistics. */ | |
2140 | void | |
2141 | dump_bitmap_statistics (void) | |
2142 | { | |
2143 | #ifdef GATHER_STATISTICS | |
2144 | struct output_info info; | |
2145 | ||
2146 | if (!bitmap_desc_hash) | |
2147 | return; | |
2148 | ||
2149 | fprintf (stderr, "\nBitmap Overall " | |
d4fb676f JH |
2150 | " Allocated Peak Leak searched " |
2151 | " search itr\n"); | |
f75709c6 JH |
2152 | fprintf (stderr, "---------------------------------------------------------------------------------\n"); |
2153 | info.count = 0; | |
2154 | info.size = 0; | |
2155 | htab_traverse (bitmap_desc_hash, print_statistics, &info); | |
2156 | fprintf (stderr, "---------------------------------------------------------------------------------\n"); | |
e2d87023 | 2157 | fprintf (stderr, "%-40s %9d %15"HOST_WIDEST_INT_PRINT"d\n", |
f75709c6 JH |
2158 | "Total", info.count, info.size); |
2159 | fprintf (stderr, "---------------------------------------------------------------------------------\n"); | |
2160 | #endif | |
2161 | } | |
e2500fed | 2162 | |
1af4bba8 JH |
2163 | /* Compute hash of bitmap (for purposes of hashing). */ |
2164 | hashval_t | |
e326eeb5 | 2165 | bitmap_hash (const_bitmap head) |
1af4bba8 | 2166 | { |
e326eeb5 | 2167 | const bitmap_element *ptr; |
1af4bba8 JH |
2168 | BITMAP_WORD hash = 0; |
2169 | int ix; | |
2170 | ||
2171 | for (ptr = head->first; ptr; ptr = ptr->next) | |
2172 | { | |
2173 | hash ^= ptr->indx; | |
2174 | for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
2175 | hash ^= ptr->bits[ix]; | |
2176 | } | |
2177 | return (hashval_t)hash; | |
2178 | } | |
2179 | ||
e2500fed | 2180 | #include "gt-bitmap.h" |