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