Mercurial > hg > CbC > CbC_gcc

comparison gcc/sbitmap.c @ 111:04ced10e8804

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