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