Mercurial > hg > CbC > CbC_gcc

comparison gcc/sbitmap.c @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 77e2b8dfacca
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
1 /* Simple bitmaps.
2 Copyright (C) 1999, 2000, 2002, 2003, 2004, 2006, 2007, 2008
3 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
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
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
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.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "flags.h"
27 #include "hard-reg-set.h"
28 #include "obstack.h"
29 #include "basic-block.h"
30
31 #if GCC_VERSION >= 3400
32 #if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG
33 #define do_popcount(x) __builtin_popcountl(x)
34 #elif HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONGLONG
35 #define do_popcount(x) __builtin_popcountll(x)
36 #else
37 #error "internal error: sbitmap.h and hwint.h are inconsistent"
38 #endif
39 #else
40 static unsigned long sbitmap_elt_popcount (SBITMAP_ELT_TYPE);
41 #define do_popcount(x) sbitmap_elt_popcount((x))
42 #endif
43
44 /* This macro controls debugging that is as expensive as the
45 operations it verifies. */
46
47 /* #define BITMAP_DEBUGGING */
48 #ifdef BITMAP_DEBUGGING
49
50 /* Verify the population count of sbitmap A matches the cached value,
51 if there is a cached value. */
52
53 void
54 sbitmap_verify_popcount (const_sbitmap a)
55 {
56 unsigned ix;
57 unsigned int lastword;
58
59 if (!a->popcount)
60 return;
61
62 lastword = a->size;
63 for (ix = 0; ix < lastword; ix++)
64 gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
65 }
66 #endif
67
68 /* Bitmap manipulation routines. */
69
70 /* Allocate a simple bitmap of N_ELMS bits. */
71
72 sbitmap
73 sbitmap_alloc (unsigned int n_elms)
74 {
75 unsigned int bytes, size, amt;
76 sbitmap bmap;
77
78 size = SBITMAP_SET_SIZE (n_elms);
79 bytes = size * sizeof (SBITMAP_ELT_TYPE);
80 amt = (sizeof (struct simple_bitmap_def)
81 + bytes - sizeof (SBITMAP_ELT_TYPE));
82 bmap = (sbitmap) xmalloc (amt);
83 bmap->n_bits = n_elms;
84 bmap->size = size;
85 bmap->popcount = NULL;
86 return bmap;
87 }
88
89 /* Allocate a simple bitmap of N_ELMS bits, and a popcount array. */
90
91 sbitmap
92 sbitmap_alloc_with_popcount (unsigned int n_elms)
93 {
94 sbitmap const bmap = sbitmap_alloc (n_elms);
95 bmap->popcount = XNEWVEC (unsigned char, bmap->size);
96 return bmap;
97 }
98
99 /* Resize a simple bitmap BMAP to N_ELMS bits. If increasing the
100 size of BMAP, clear the new bits to zero if the DEF argument
101 is zero, and set them to one otherwise. */
102
103 sbitmap
104 sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
105 {
106 unsigned int bytes, size, amt;
107 unsigned int last_bit;
108
109 size = SBITMAP_SET_SIZE (n_elms);
110 bytes = size * sizeof (SBITMAP_ELT_TYPE);
111 if (bytes > SBITMAP_SIZE_BYTES (bmap))
112 {
113 amt = (sizeof (struct simple_bitmap_def)
114 + bytes - sizeof (SBITMAP_ELT_TYPE));
115 bmap = (sbitmap) xrealloc (bmap, amt);
116 if (bmap->popcount)
117 bmap->popcount = XRESIZEVEC (unsigned char, bmap->popcount, size);
118 }
119
120 if (n_elms > bmap->n_bits)
121 {
122 if (def)
123 {
124 memset (bmap->elms + bmap->size, -1,
125 bytes - SBITMAP_SIZE_BYTES (bmap));
126
127 /* Set the new bits if the original last element. */
128 last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
129 if (last_bit)
130 bmap->elms[bmap->size - 1]
131 |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
132
133 /* Clear the unused bit in the new last element. */
134 last_bit = n_elms % SBITMAP_ELT_BITS;
135 if (last_bit)
136 bmap->elms[size - 1]
137 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
138 }
139 else
140 {
141 memset (bmap->elms + bmap->size, 0,
142 bytes - SBITMAP_SIZE_BYTES (bmap));
143 if (bmap->popcount)
144 memset (bmap->popcount + bmap->size, 0,
145 (size * sizeof (unsigned char))
146 - (bmap->size * sizeof (unsigned char)));
147
148 }
149 }
150 else if (n_elms < bmap->n_bits)
151 {
152 /* Clear the surplus bits in the last word. */
153 last_bit = n_elms % SBITMAP_ELT_BITS;
154 if (last_bit)
155 {
156 bmap->elms[size - 1]
157 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
158 if (bmap->popcount)
159 bmap->popcount[size - 1] = do_popcount (bmap->elms[size - 1]);
160 }
161 }
162
163 bmap->n_bits = n_elms;
164 bmap->size = size;
165 return bmap;
166 }
167
168 /* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized. */
169
170 sbitmap
171 sbitmap_realloc (sbitmap src, unsigned int n_elms)
172 {
173 unsigned int bytes, size, amt;
174 sbitmap bmap;
175
176 size = SBITMAP_SET_SIZE (n_elms);
177 bytes = size * sizeof (SBITMAP_ELT_TYPE);
178 amt = (sizeof (struct simple_bitmap_def)
179 + bytes - sizeof (SBITMAP_ELT_TYPE));
180
181 if (SBITMAP_SIZE_BYTES (src) >= bytes)
182 {
183 src->n_bits = n_elms;
184 return src;
185 }
186
187 bmap = (sbitmap) xrealloc (src, amt);
188 bmap->n_bits = n_elms;
189 bmap->size = size;
190 return bmap;
191 }
192
193 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */
194
195 sbitmap *
196 sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
197 {
198 unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes;
199 sbitmap *bitmap_vector;
200
201 size = SBITMAP_SET_SIZE (n_elms);
202 bytes = size * sizeof (SBITMAP_ELT_TYPE);
203 elm_bytes = (sizeof (struct simple_bitmap_def)
204 + bytes - sizeof (SBITMAP_ELT_TYPE));
205 vector_bytes = n_vecs * sizeof (sbitmap *);
206
207 /* Round up `vector_bytes' to account for the alignment requirements
208 of an sbitmap. One could allocate the vector-table and set of sbitmaps
209 separately, but that requires maintaining two pointers or creating
210 a cover struct to hold both pointers (so our result is still just
211 one pointer). Neither is a bad idea, but this is simpler for now. */
212 {
213 /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */
214 struct { char x; SBITMAP_ELT_TYPE y; } align;
215 int alignment = (char *) & align.y - & align.x;
216 vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
217 }
218
219 amt = vector_bytes + (n_vecs * elm_bytes);
220 bitmap_vector = (sbitmap *) xmalloc (amt);
221
222 for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
223 {
224 sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
225
226 bitmap_vector[i] = b;
227 b->n_bits = n_elms;
228 b->size = size;
229 b->popcount = NULL;
230 }
231
232 return bitmap_vector;
233 }
234
235 /* Copy sbitmap SRC to DST. */
236
237 void
238 sbitmap_copy (sbitmap dst, const_sbitmap src)
239 {
240 memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
241 if (dst->popcount)
242 memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * dst->size);
243 }
244
245 /* Copy the first N elements of sbitmap SRC to DST. */
246
247 void
248 sbitmap_copy_n (sbitmap dst, const_sbitmap src, unsigned int n)
249 {
250 memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * n);
251 if (dst->popcount)
252 memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * n);
253 }
254
255 /* Determine if a == b. */
256 int
257 sbitmap_equal (const_sbitmap a, const_sbitmap b)
258 {
259 return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
260 }
261
262 /* Return true if the bitmap is empty. */
263
264 bool
265 sbitmap_empty_p (const_sbitmap bmap)
266 {
267 unsigned int i;
268 for (i=0; i<bmap->size; i++)
269 if (bmap->elms[i])
270 return false;
271
272 return true;
273 }
274
275 /* Return false if any of the N bits are set in MAP starting at
276 START. */
277
278 bool
279 sbitmap_range_empty_p (const_sbitmap bmap, unsigned int start, unsigned int n)
280 {
281 unsigned int i = start / SBITMAP_ELT_BITS;
282 SBITMAP_ELT_TYPE elm;
283 unsigned int shift = start % SBITMAP_ELT_BITS;
284
285 gcc_assert (bmap->n_bits >= start + n);
286
287 elm = bmap->elms[i];
288 elm = elm >> shift;
289
290 if (shift + n <= SBITMAP_ELT_BITS)
291 {
292 /* The bits are totally contained in a single element. */
293 if (shift + n < SBITMAP_ELT_BITS)
294 elm &= ((1 << n) - 1);
295 return (elm == 0);
296 }
297
298 if (elm)
299 return false;
300
301 n -= SBITMAP_ELT_BITS - shift;
302 i++;
303
304 /* Deal with full elts. */
305 while (n >= SBITMAP_ELT_BITS)
306 {
307 if (bmap->elms[i])
308 return false;
309 i++;
310 n -= SBITMAP_ELT_BITS;
311 }
312
313 /* The leftover bits. */
314 if (n)
315 {
316 elm = bmap->elms[i];
317 elm &= ((1 << n) - 1);
318 return (elm == 0);
319 }
320
321 return true;
322 }
323
324
325
326 /* Zero all elements in a bitmap. */
327
328 void
329 sbitmap_zero (sbitmap bmap)
330 {
331 memset (bmap->elms, 0, SBITMAP_SIZE_BYTES (bmap));
332 if (bmap->popcount)
333 memset (bmap->popcount, 0, bmap->size * sizeof (unsigned char));
334 }
335
336 /* Set all elements in a bitmap to ones. */
337
338 void
339 sbitmap_ones (sbitmap bmap)
340 {
341 unsigned int last_bit;
342
343 memset (bmap->elms, -1, SBITMAP_SIZE_BYTES (bmap));
344 if (bmap->popcount)
345 memset (bmap->popcount, -1, bmap->size * sizeof (unsigned char));
346
347 last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
348 if (last_bit)
349 {
350 bmap->elms[bmap->size - 1]
351 = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
352 if (bmap->popcount)
353 bmap->popcount[bmap->size - 1]
354 = do_popcount (bmap->elms[bmap->size - 1]);
355 }
356 }
357
358 /* Zero a vector of N_VECS bitmaps. */
359
360 void
361 sbitmap_vector_zero (sbitmap *bmap, unsigned int n_vecs)
362 {
363 unsigned int i;
364
365 for (i = 0; i < n_vecs; i++)
366 sbitmap_zero (bmap[i]);
367 }
368
369 /* Set a vector of N_VECS bitmaps to ones. */
370
371 void
372 sbitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
373 {
374 unsigned int i;
375
376 for (i = 0; i < n_vecs; i++)
377 sbitmap_ones (bmap[i]);
378 }
379
380 /* Set DST to be A union (B - C).
381 DST = A | (B & ~C).
382 Returns true if any change is made. */
383
384 bool
385 sbitmap_union_of_diff_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
386 {
387 unsigned int i, n = dst->size;
388 sbitmap_ptr dstp = dst->elms;
389 const_sbitmap_ptr ap = a->elms;
390 const_sbitmap_ptr bp = b->elms;
391 const_sbitmap_ptr cp = c->elms;
392 SBITMAP_ELT_TYPE changed = 0;
393
394 gcc_assert (!dst->popcount);
395
396 for (i = 0; i < n; i++)
397 {
398 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
399 changed |= *dstp ^ tmp;
400 *dstp++ = tmp;
401 }
402
403 return changed != 0;
404 }
405
406 void
407 sbitmap_union_of_diff (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
408 {
409 unsigned int i, n = dst->size;
410 sbitmap_ptr dstp = dst->elms;
411 const_sbitmap_ptr ap = a->elms;
412 const_sbitmap_ptr bp = b->elms;
413 const_sbitmap_ptr cp = c->elms;
414
415 gcc_assert (!dst->popcount && !a->popcount
416 && !b->popcount && !c->popcount);
417
418 for (i = 0; i < n; i++)
419 *dstp++ = *ap++ | (*bp++ & ~*cp++);
420 }
421
422 /* Set bitmap DST to the bitwise negation of the bitmap SRC. */
423
424 void
425 sbitmap_not (sbitmap dst, const_sbitmap src)
426 {
427 unsigned int i, n = dst->size;
428 sbitmap_ptr dstp = dst->elms;
429 const_sbitmap_ptr srcp = src->elms;
430 unsigned int last_bit;
431
432 gcc_assert (!dst->popcount);
433
434 for (i = 0; i < n; i++)
435 *dstp++ = ~*srcp++;
436
437 /* Zero all bits past n_bits, by ANDing dst with sbitmap_ones. */
438 last_bit = src->n_bits % SBITMAP_ELT_BITS;
439 if (last_bit)
440 dst->elms[n-1] = dst->elms[n-1]
441 & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
442 }
443
444 /* Set the bits in DST to be the difference between the bits
445 in A and the bits in B. i.e. dst = a & (~b). */
446
447 void
448 sbitmap_difference (sbitmap dst, const_sbitmap a, const_sbitmap b)
449 {
450 unsigned int i, dst_size = dst->size;
451 unsigned int min_size = dst->size;
452 sbitmap_ptr dstp = dst->elms;
453 const_sbitmap_ptr ap = a->elms;
454 const_sbitmap_ptr bp = b->elms;
455
456 gcc_assert (!dst->popcount);
457
458 /* A should be at least as large as DEST, to have a defined source. */
459 gcc_assert (a->size >= dst_size);
460 /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
461 only copy the subtrahend into dest. */
462 if (b->size < min_size)
463 min_size = b->size;
464 for (i = 0; i < min_size; i++)
465 *dstp++ = *ap++ & (~*bp++);
466 /* Now fill the rest of dest from A, if B was too short.
467 This makes sense only when destination and A differ. */
468 if (dst != a && i != dst_size)
469 for (; i < dst_size; i++)
470 *dstp++ = *ap++;
471 }
472
473 /* Return true if there are any bits set in A are also set in B.
474 Return false otherwise. */
475
476 bool
477 sbitmap_any_common_bits (const_sbitmap a, const_sbitmap b)
478 {
479 const_sbitmap_ptr ap = a->elms;
480 const_sbitmap_ptr bp = b->elms;
481 unsigned int i, n;
482
483 n = MIN (a->size, b->size);
484 for (i = 0; i < n; i++)
485 if ((*ap++ & *bp++) != 0)
486 return true;
487
488 return false;
489 }
490
491 /* Set DST to be (A and B).
492 Return nonzero if any change is made. */
493
494 bool
495 sbitmap_a_and_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
496 {
497 unsigned int i, n = dst->size;
498 sbitmap_ptr dstp = dst->elms;
499 const_sbitmap_ptr ap = a->elms;
500 const_sbitmap_ptr bp = b->elms;
501 SBITMAP_ELT_TYPE changed = 0;
502
503 gcc_assert (!dst->popcount);
504
505 for (i = 0; i < n; i++)
506 {
507 const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
508 changed |= *dstp ^ tmp;
509 *dstp++ = tmp;
510 }
511
512 return changed != 0;
513 }
514
515 void
516 sbitmap_a_and_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
517 {
518 unsigned int i, n = dst->size;
519 sbitmap_ptr dstp = dst->elms;
520 const_sbitmap_ptr ap = a->elms;
521 const_sbitmap_ptr bp = b->elms;
522 bool has_popcount = dst->popcount != NULL;
523 unsigned char *popcountp = dst->popcount;
524
525 for (i = 0; i < n; i++)
526 {
527 const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
528 if (has_popcount)
529 {
530 bool wordchanged = (*dstp ^ tmp) != 0;
531 if (wordchanged)
532 *popcountp = do_popcount (tmp);
533 popcountp++;
534 }
535 *dstp++ = tmp;
536 }
537 #ifdef BITMAP_DEBUGGING
538 if (has_popcount)
539 sbitmap_verify_popcount (dst);
540 #endif
541 }
542
543 /* Set DST to be (A xor B)).
544 Return nonzero if any change is made. */
545
546 bool
547 sbitmap_a_xor_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
548 {
549 unsigned int i, n = dst->size;
550 sbitmap_ptr dstp = dst->elms;
551 const_sbitmap_ptr ap = a->elms;
552 const_sbitmap_ptr bp = b->elms;
553 SBITMAP_ELT_TYPE changed = 0;
554
555 gcc_assert (!dst->popcount);
556
557 for (i = 0; i < n; i++)
558 {
559 const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
560 changed |= *dstp ^ tmp;
561 *dstp++ = tmp;
562 }
563
564 return changed != 0;
565 }
566
567 void
568 sbitmap_a_xor_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
569 {
570 unsigned int i, n = dst->size;
571 sbitmap_ptr dstp = dst->elms;
572 const_sbitmap_ptr ap = a->elms;
573 const_sbitmap_ptr bp = b->elms;
574 bool has_popcount = dst->popcount != NULL;
575 unsigned char *popcountp = dst->popcount;
576
577 for (i = 0; i < n; i++)
578 {
579 const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
580 if (has_popcount)
581 {
582 bool wordchanged = (*dstp ^ tmp) != 0;
583 if (wordchanged)
584 *popcountp = do_popcount (tmp);
585 popcountp++;
586 }
587 *dstp++ = tmp;
588 }
589 #ifdef BITMAP_DEBUGGING
590 if (has_popcount)
591 sbitmap_verify_popcount (dst);
592 #endif
593 }
594
595 /* Set DST to be (A or B)).
596 Return nonzero if any change is made. */
597
598 bool
599 sbitmap_a_or_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
600 {
601 unsigned int i, n = dst->size;
602 sbitmap_ptr dstp = dst->elms;
603 const_sbitmap_ptr ap = a->elms;
604 const_sbitmap_ptr bp = b->elms;
605 SBITMAP_ELT_TYPE changed = 0;
606
607 gcc_assert (!dst->popcount);
608
609 for (i = 0; i < n; i++)
610 {
611 const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
612 changed |= *dstp ^ tmp;
613 *dstp++ = tmp;
614 }
615
616 return changed != 0;
617 }
618
619 void
620 sbitmap_a_or_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
621 {
622 unsigned int i, n = dst->size;
623 sbitmap_ptr dstp = dst->elms;
624 const_sbitmap_ptr ap = a->elms;
625 const_sbitmap_ptr bp = b->elms;
626 bool has_popcount = dst->popcount != NULL;
627 unsigned char *popcountp = dst->popcount;
628
629 for (i = 0; i < n; i++)
630 {
631 const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
632 if (has_popcount)
633 {
634 bool wordchanged = (*dstp ^ tmp) != 0;
635 if (wordchanged)
636 *popcountp = do_popcount (tmp);
637 popcountp++;
638 }
639 *dstp++ = tmp;
640 }
641 #ifdef BITMAP_DEBUGGING
642 if (has_popcount)
643 sbitmap_verify_popcount (dst);
644 #endif
645 }
646
647 /* Return nonzero if A is a subset of B. */
648
649 bool
650 sbitmap_a_subset_b_p (const_sbitmap a, const_sbitmap b)
651 {
652 unsigned int i, n = a->size;
653 const_sbitmap_ptr ap, bp;
654
655 for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
656 if ((*ap | *bp) != *bp)
657 return false;
658
659 return true;
660 }
661
662 /* Set DST to be (A or (B and C)).
663 Return nonzero if any change is made. */
664
665 bool
666 sbitmap_a_or_b_and_c_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
667 {
668 unsigned int i, n = dst->size;
669 sbitmap_ptr dstp = dst->elms;
670 const_sbitmap_ptr ap = a->elms;
671 const_sbitmap_ptr bp = b->elms;
672 const_sbitmap_ptr cp = c->elms;
673 SBITMAP_ELT_TYPE changed = 0;
674
675 gcc_assert (!dst->popcount);
676
677 for (i = 0; i < n; i++)
678 {
679 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
680 changed |= *dstp ^ tmp;
681 *dstp++ = tmp;
682 }
683
684 return changed != 0;
685 }
686
687 void
688 sbitmap_a_or_b_and_c (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
689 {
690 unsigned int i, n = dst->size;
691 sbitmap_ptr dstp = dst->elms;
692 const_sbitmap_ptr ap = a->elms;
693 const_sbitmap_ptr bp = b->elms;
694 const_sbitmap_ptr cp = c->elms;
695
696 gcc_assert (!dst->popcount);
697
698 for (i = 0; i < n; i++)
699 *dstp++ = *ap++ | (*bp++ & *cp++);
700 }
701
702 /* Set DST to be (A and (B or C)).
703 Return nonzero if any change is made. */
704
705 bool
706 sbitmap_a_and_b_or_c_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
707 {
708 unsigned int i, n = dst->size;
709 sbitmap_ptr dstp = dst->elms;
710 const_sbitmap_ptr ap = a->elms;
711 const_sbitmap_ptr bp = b->elms;
712 const_sbitmap_ptr cp = c->elms;
713 SBITMAP_ELT_TYPE changed = 0;
714
715 gcc_assert (!dst->popcount);
716
717 for (i = 0; i < n; i++)
718 {
719 const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
720 changed |= *dstp ^ tmp;
721 *dstp++ = tmp;
722 }
723
724 return changed != 0;
725 }
726
727 void
728 sbitmap_a_and_b_or_c (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
729 {
730 unsigned int i, n = dst->size;
731 sbitmap_ptr dstp = dst->elms;
732 const_sbitmap_ptr ap = a->elms;
733 const_sbitmap_ptr bp = b->elms;
734 const_sbitmap_ptr cp = c->elms;
735
736 for (i = 0; i < n; i++)
737 *dstp++ = *ap++ & (*bp++ | *cp++);
738 }
739
740 #ifdef IN_GCC
741 /* Set the bitmap DST to the intersection of SRC of successors of
742 block number BB, using the new flow graph structures. */
743
744 void
745 sbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, int bb)
746 {
747 basic_block b = BASIC_BLOCK (bb);
748 unsigned int set_size = dst->size;
749 edge e;
750 unsigned ix;
751
752 gcc_assert (!dst->popcount);
753
754 for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
755 {
756 e = EDGE_SUCC (b, ix);
757 if (e->dest == EXIT_BLOCK_PTR)
758 continue;
759
760 sbitmap_copy (dst, src[e->dest->index]);
761 break;
762 }
763
764 if (e == 0)
765 sbitmap_ones (dst);
766 else
767 for (++ix; ix < EDGE_COUNT (b->succs); ix++)
768 {
769 unsigned int i;
770 sbitmap_ptr p, r;
771
772 e = EDGE_SUCC (b, ix);
773 if (e->dest == EXIT_BLOCK_PTR)
774 continue;
775
776 p = src[e->dest->index]->elms;
777 r = dst->elms;
778 for (i = 0; i < set_size; i++)
779 *r++ &= *p++;
780 }
781 }
782
783 /* Set the bitmap DST to the intersection of SRC of predecessors of
784 block number BB, using the new flow graph structures. */
785
786 void
787 sbitmap_intersection_of_preds (sbitmap dst, sbitmap *src, int bb)
788 {
789 basic_block b = BASIC_BLOCK (bb);
790 unsigned int set_size = dst->size;
791 edge e;
792 unsigned ix;
793
794 gcc_assert (!dst->popcount);
795
796 for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
797 {
798 e = EDGE_PRED (b, ix);
799 if (e->src == ENTRY_BLOCK_PTR)
800 continue;
801
802 sbitmap_copy (dst, src[e->src->index]);
803 break;
804 }
805
806 if (e == 0)
807 sbitmap_ones (dst);
808 else
809 for (++ix; ix < EDGE_COUNT (b->preds); ix++)
810 {
811 unsigned int i;
812 sbitmap_ptr p, r;
813
814 e = EDGE_PRED (b, ix);
815 if (e->src == ENTRY_BLOCK_PTR)
816 continue;
817
818 p = src[e->src->index]->elms;
819 r = dst->elms;
820 for (i = 0; i < set_size; i++)
821 *r++ &= *p++;
822 }
823 }
824
825 /* Set the bitmap DST to the union of SRC of successors of
826 block number BB, using the new flow graph structures. */
827
828 void
829 sbitmap_union_of_succs (sbitmap dst, sbitmap *src, int bb)
830 {
831 basic_block b = BASIC_BLOCK (bb);
832 unsigned int set_size = dst->size;
833 edge e;
834 unsigned ix;
835
836 gcc_assert (!dst->popcount);
837
838 for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
839 {
840 e = EDGE_SUCC (b, ix);
841 if (e->dest == EXIT_BLOCK_PTR)
842 continue;
843
844 sbitmap_copy (dst, src[e->dest->index]);
845 break;
846 }
847
848 if (ix == EDGE_COUNT (b->succs))
849 sbitmap_zero (dst);
850 else
851 for (ix++; ix < EDGE_COUNT (b->succs); ix++)
852 {
853 unsigned int i;
854 sbitmap_ptr p, r;
855
856 e = EDGE_SUCC (b, ix);
857 if (e->dest == EXIT_BLOCK_PTR)
858 continue;
859
860 p = src[e->dest->index]->elms;
861 r = dst->elms;
862 for (i = 0; i < set_size; i++)
863 *r++ |= *p++;
864 }
865 }
866
867 /* Set the bitmap DST to the union of SRC of predecessors of
868 block number BB, using the new flow graph structures. */
869
870 void
871 sbitmap_union_of_preds (sbitmap dst, sbitmap *src, int bb)
872 {
873 basic_block b = BASIC_BLOCK (bb);
874 unsigned int set_size = dst->size;
875 edge e;
876 unsigned ix;
877
878 gcc_assert (!dst->popcount);
879
880 for (ix = 0; ix < EDGE_COUNT (b->preds); ix++)
881 {
882 e = EDGE_PRED (b, ix);
883 if (e->src== ENTRY_BLOCK_PTR)
884 continue;
885
886 sbitmap_copy (dst, src[e->src->index]);
887 break;
888 }
889
890 if (ix == EDGE_COUNT (b->preds))
891 sbitmap_zero (dst);
892 else
893 for (ix++; ix < EDGE_COUNT (b->preds); ix++)
894 {
895 unsigned int i;
896 sbitmap_ptr p, r;
897
898 e = EDGE_PRED (b, ix);
899 if (e->src == ENTRY_BLOCK_PTR)
900 continue;
901
902 p = src[e->src->index]->elms;
903 r = dst->elms;
904 for (i = 0; i < set_size; i++)
905 *r++ |= *p++;
906 }
907 }
908 #endif
909
910 /* Return number of first bit set in the bitmap, -1 if none. */
911
912 int
913 sbitmap_first_set_bit (const_sbitmap bmap)
914 {
915 unsigned int n = 0;
916 sbitmap_iterator sbi;
917
918 EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, sbi)
919 return n;
920 return -1;
921 }
922
923 /* Return number of last bit set in the bitmap, -1 if none. */
924
925 int
926 sbitmap_last_set_bit (const_sbitmap bmap)
927 {
928 int i;
929 const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
930
931 for (i = bmap->size - 1; i >= 0; i--)
932 {
933 const SBITMAP_ELT_TYPE word = ptr[i];
934
935 if (word != 0)
936 {
937 unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
938 SBITMAP_ELT_TYPE mask
939 = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
940
941 while (1)
942 {
943 if ((word & mask) != 0)
944 return index;
945
946 mask >>= 1;
947 index--;
948 }
949 }
950 }
951
952 return -1;
953 }
954
955 void
956 dump_sbitmap (FILE *file, const_sbitmap bmap)
957 {
958 unsigned int i, n, j;
959 unsigned int set_size = bmap->size;
960 unsigned int total_bits = bmap->n_bits;
961
962 fprintf (file, " ");
963 for (i = n = 0; i < set_size && n < total_bits; i++)
964 for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
965 {
966 if (n != 0 && n % 10 == 0)
967 fprintf (file, " ");
968
969 fprintf (file, "%d",
970 (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
971 }
972
973 fprintf (file, "\n");
974 }
975
976 void
977 dump_sbitmap_file (FILE *file, const_sbitmap bmap)
978 {
979 unsigned int i, pos;
980
981 fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
982
983 for (pos = 30, i = 0; i < bmap->n_bits; i++)
984 if (TEST_BIT (bmap, i))
985 {
986 if (pos > 70)
987 {
988 fprintf (file, "\n ");
989 pos = 0;
990 }
991
992 fprintf (file, "%d ", i);
993 pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
994 }
995
996 fprintf (file, "}\n");
997 }
998
999 void
1000 debug_sbitmap (const_sbitmap bmap)
1001 {
1002 dump_sbitmap_file (stderr, bmap);
1003 }
1004
1005 void
1006 dump_sbitmap_vector (FILE *file, const char *title, const char *subtitle,
1007 sbitmap *bmaps, int n_maps)
1008 {
1009 int bb;
1010
1011 fprintf (file, "%s\n", title);
1012 for (bb = 0; bb < n_maps; bb++)
1013 {
1014 fprintf (file, "%s %d\n", subtitle, bb);
1015 dump_sbitmap (file, bmaps[bb]);
1016 }
1017
1018 fprintf (file, "\n");
1019 }
1020
1021 #if GCC_VERSION < 3400
1022 /* Table of number of set bits in a character, indexed by value of char. */
1023 static const unsigned char popcount_table[] =
1024 {
1025 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,
1026 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,
1027 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,
1028 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,
1029 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,
1030 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,
1031 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,
1032 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,
1033 };
1034
1035 /* Count the bits in an SBITMAP element A. */
1036
1037 static unsigned long
1038 sbitmap_elt_popcount (SBITMAP_ELT_TYPE a)
1039 {
1040 unsigned long ret = 0;
1041 unsigned i;
1042
1043 if (a == 0)
1044 return 0;
1045
1046 /* Just do this the table way for now */
1047 for (i = 0; i < SBITMAP_ELT_BITS; i += 8)
1048 ret += popcount_table[(a >> i) & 0xff];
1049 return ret;
1050 }
1051 #endif
1052
1053 /* Count the number of bits in SBITMAP a, up to bit MAXBIT. */
1054
1055 unsigned long
1056 sbitmap_popcount (const_sbitmap a, unsigned long maxbit)
1057 {
1058 unsigned long count = 0;
1059 unsigned ix;
1060 unsigned int lastword;
1061
1062 if (maxbit == 0)
1063 return 0;
1064
1065 if (maxbit >= a->n_bits)
1066 maxbit = a->n_bits;
1067
1068 /* Count the bits in the full word. */
1069 lastword = MIN (a->size, SBITMAP_SET_SIZE (maxbit + 1) - 1);
1070 for (ix = 0; ix < lastword; ix++)
1071 {
1072 if (a->popcount)
1073 {
1074 count += a->popcount[ix];
1075 #ifdef BITMAP_DEBUGGING
1076 gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
1077 #endif
1078 }
1079 else
1080 count += do_popcount (a->elms[ix]);
1081 }
1082
1083 /* Count the remaining bits. */
1084 if (lastword < a->size)
1085 {
1086 unsigned int bitindex;
1087 SBITMAP_ELT_TYPE theword = a->elms[lastword];
1088
1089 bitindex = maxbit % SBITMAP_ELT_BITS;
1090 if (bitindex != 0)
1091 {
1092 theword &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - bitindex);
1093 count += do_popcount (theword);
1094 }
1095 }
1096 return count;
1097 }
1098