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