|
0
|
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
|
