]>
Commit | Line | Data |
---|---|---|
5f6c11d6 RH |
1 | /* Simple bitmaps. |
2 | Copyright (C) 1999 Free Software Foundation, Inc. | |
3 | ||
4 | This file is part of GNU CC. | |
5 | ||
6 | GNU CC is free software; you can redistribute it and/or modify | |
7 | it under the terms of the GNU General Public License as published by | |
8 | the Free Software Foundation; either version 2, or (at your option) | |
9 | any later version. | |
10 | ||
11 | GNU CC is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | GNU General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
17 | along with GNU CC; see the file COPYING. If not, write to | |
18 | the Free Software Foundation, 59 Temple Place - Suite 330, | |
19 | Boston, MA 02111-1307, USA. */ | |
20 | ||
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "rtl.h" | |
24 | #include "flags.h" | |
25 | #include "basic-block.h" | |
26 | ||
27 | /* Bitmap manipulation routines. */ | |
28 | ||
29 | /* Allocate a simple bitmap of N_ELMS bits. */ | |
30 | ||
31 | sbitmap | |
32 | sbitmap_alloc (n_elms) | |
33 | int n_elms; | |
34 | { | |
35 | int bytes, size, amt; | |
36 | sbitmap bmap; | |
37 | ||
38 | size = SBITMAP_SET_SIZE (n_elms); | |
39 | bytes = size * sizeof (SBITMAP_ELT_TYPE); | |
40 | amt = (sizeof (struct simple_bitmap_def) | |
41 | + bytes - sizeof (SBITMAP_ELT_TYPE)); | |
42 | bmap = (sbitmap) xmalloc (amt); | |
43 | bmap->n_bits = n_elms; | |
44 | bmap->size = size; | |
45 | bmap->bytes = bytes; | |
46 | return bmap; | |
47 | } | |
48 | ||
49 | /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */ | |
50 | ||
51 | sbitmap * | |
52 | sbitmap_vector_alloc (n_vecs, n_elms) | |
53 | int n_vecs, n_elms; | |
54 | { | |
55 | int i, bytes, offset, elm_bytes, size, amt, vector_bytes; | |
56 | sbitmap *bitmap_vector; | |
57 | ||
58 | size = SBITMAP_SET_SIZE (n_elms); | |
59 | bytes = size * sizeof (SBITMAP_ELT_TYPE); | |
60 | elm_bytes = (sizeof (struct simple_bitmap_def) | |
61 | + bytes - sizeof (SBITMAP_ELT_TYPE)); | |
62 | vector_bytes = n_vecs * sizeof (sbitmap *); | |
63 | ||
64 | /* Round up `vector_bytes' to account for the alignment requirements | |
65 | of an sbitmap. One could allocate the vector-table and set of sbitmaps | |
66 | separately, but that requires maintaining two pointers or creating | |
67 | a cover struct to hold both pointers (so our result is still just | |
68 | one pointer). Neither is a bad idea, but this is simpler for now. */ | |
69 | { | |
70 | /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */ | |
71 | struct { char x; SBITMAP_ELT_TYPE y; } align; | |
72 | int alignment = (char *) & align.y - & align.x; | |
73 | vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1); | |
74 | } | |
75 | ||
76 | amt = vector_bytes + (n_vecs * elm_bytes); | |
77 | bitmap_vector = (sbitmap *) xmalloc (amt); | |
78 | ||
79 | for (i = 0, offset = vector_bytes; | |
80 | i < n_vecs; | |
81 | i++, offset += elm_bytes) | |
82 | { | |
83 | sbitmap b = (sbitmap) ((char *) bitmap_vector + offset); | |
84 | bitmap_vector[i] = b; | |
85 | b->n_bits = n_elms; | |
86 | b->size = size; | |
87 | b->bytes = bytes; | |
88 | } | |
89 | ||
90 | return bitmap_vector; | |
91 | } | |
92 | ||
93 | /* Copy sbitmap SRC to DST. */ | |
94 | ||
95 | void | |
96 | sbitmap_copy (dst, src) | |
97 | sbitmap dst, src; | |
98 | { | |
47c3ed98 KG |
99 | bcopy ((PTR) src->elms, (PTR) dst->elms, |
100 | sizeof (SBITMAP_ELT_TYPE) * dst->size); | |
5f6c11d6 RH |
101 | } |
102 | ||
103 | /* Zero all elements in a bitmap. */ | |
104 | ||
105 | void | |
106 | sbitmap_zero (bmap) | |
107 | sbitmap bmap; | |
108 | { | |
109 | bzero ((char *) bmap->elms, bmap->bytes); | |
110 | } | |
111 | ||
112 | /* Set to ones all elements in a bitmap. */ | |
113 | ||
114 | void | |
115 | sbitmap_ones (bmap) | |
116 | sbitmap bmap; | |
117 | { | |
118 | memset (bmap->elms, -1, bmap->bytes); | |
119 | } | |
120 | ||
121 | /* Zero a vector of N_VECS bitmaps. */ | |
122 | ||
123 | void | |
124 | sbitmap_vector_zero (bmap, n_vecs) | |
125 | sbitmap *bmap; | |
126 | int n_vecs; | |
127 | { | |
128 | int i; | |
129 | ||
130 | for (i = 0; i < n_vecs; i++) | |
131 | sbitmap_zero (bmap[i]); | |
132 | } | |
133 | ||
134 | /* Set to ones a vector of N_VECS bitmaps. */ | |
135 | ||
136 | void | |
137 | sbitmap_vector_ones (bmap, n_vecs) | |
138 | sbitmap *bmap; | |
139 | int n_vecs; | |
140 | { | |
141 | int i; | |
142 | ||
143 | for (i = 0; i < n_vecs; i++) | |
144 | sbitmap_ones (bmap[i]); | |
145 | } | |
146 | ||
147 | /* Set DST to be A union (B - C). | |
148 | DST = A | (B & ~C). | |
149 | Return non-zero if any change is made. */ | |
150 | ||
151 | int | |
152 | sbitmap_union_of_diff (dst, a, b, c) | |
153 | sbitmap dst, a, b, c; | |
154 | { | |
155 | int i,changed; | |
156 | sbitmap_ptr dstp, ap, bp, cp; | |
157 | ||
158 | changed = 0; | |
159 | dstp = dst->elms; | |
160 | ap = a->elms; | |
161 | bp = b->elms; | |
162 | cp = c->elms; | |
163 | for (i = 0; i < dst->size; i++) | |
164 | { | |
165 | SBITMAP_ELT_TYPE tmp = *ap | (*bp & ~*cp); | |
166 | if (*dstp != tmp) | |
167 | changed = 1; | |
168 | *dstp = tmp; | |
169 | dstp++; ap++; bp++; cp++; | |
170 | } | |
171 | return changed; | |
172 | } | |
173 | ||
174 | /* Set bitmap DST to the bitwise negation of the bitmap SRC. */ | |
175 | ||
176 | void | |
177 | sbitmap_not (dst, src) | |
178 | sbitmap dst, src; | |
179 | { | |
180 | int i; | |
181 | sbitmap_ptr dstp, ap; | |
182 | ||
183 | dstp = dst->elms; | |
184 | ap = src->elms; | |
185 | for (i = 0; i < dst->size; i++) | |
186 | { | |
187 | SBITMAP_ELT_TYPE tmp = ~(*ap); | |
188 | *dstp = tmp; | |
189 | dstp++; ap++; | |
190 | } | |
191 | } | |
192 | ||
193 | /* Set the bits in DST to be the difference between the bits | |
194 | in A and the bits in B. i.e. dst = a - b. | |
195 | The - operator is implemented as a & (~b). */ | |
196 | ||
197 | void | |
198 | sbitmap_difference (dst, a, b) | |
199 | sbitmap dst, a, b; | |
200 | { | |
201 | int i; | |
202 | sbitmap_ptr dstp, ap, bp; | |
203 | ||
204 | dstp = dst->elms; | |
205 | ap = a->elms; | |
206 | bp = b->elms; | |
207 | for (i = 0; i < dst->size; i++) | |
208 | *dstp++ = *ap++ & (~*bp++); | |
209 | } | |
210 | ||
211 | /* Set DST to be (A and B)). | |
212 | Return non-zero if any change is made. */ | |
213 | ||
214 | int | |
215 | sbitmap_a_and_b (dst, a, b) | |
216 | sbitmap dst, a, b; | |
217 | { | |
218 | int i,changed; | |
219 | sbitmap_ptr dstp, ap, bp; | |
220 | ||
221 | changed = 0; | |
222 | dstp = dst->elms; | |
223 | ap = a->elms; | |
224 | bp = b->elms; | |
225 | for (i = 0; i < dst->size; i++) | |
226 | { | |
227 | SBITMAP_ELT_TYPE tmp = *ap & *bp; | |
228 | if (*dstp != tmp) | |
229 | changed = 1; | |
230 | *dstp = tmp; | |
231 | dstp++; ap++; bp++; | |
232 | } | |
233 | return changed; | |
234 | } | |
235 | /* Set DST to be (A or B)). | |
236 | Return non-zero if any change is made. */ | |
237 | ||
238 | int | |
239 | sbitmap_a_or_b (dst, a, b) | |
240 | sbitmap dst, a, b; | |
241 | { | |
242 | int i,changed; | |
243 | sbitmap_ptr dstp, ap, bp; | |
244 | ||
245 | changed = 0; | |
246 | dstp = dst->elms; | |
247 | ap = a->elms; | |
248 | bp = b->elms; | |
249 | for (i = 0; i < dst->size; i++) | |
250 | { | |
251 | SBITMAP_ELT_TYPE tmp = *ap | *bp; | |
252 | if (*dstp != tmp) | |
253 | changed = 1; | |
254 | *dstp = tmp; | |
255 | dstp++; ap++; bp++; | |
256 | } | |
257 | return changed; | |
258 | } | |
259 | ||
260 | /* Set DST to be (A or (B and C)). | |
261 | Return non-zero if any change is made. */ | |
262 | ||
263 | int | |
264 | sbitmap_a_or_b_and_c (dst, a, b, c) | |
265 | sbitmap dst, a, b, c; | |
266 | { | |
267 | int i,changed; | |
268 | sbitmap_ptr dstp, ap, bp, cp; | |
269 | ||
270 | changed = 0; | |
271 | dstp = dst->elms; | |
272 | ap = a->elms; | |
273 | bp = b->elms; | |
274 | cp = c->elms; | |
275 | for (i = 0; i < dst->size; i++) | |
276 | { | |
277 | SBITMAP_ELT_TYPE tmp = *ap | (*bp & *cp); | |
278 | if (*dstp != tmp) | |
279 | changed = 1; | |
280 | *dstp = tmp; | |
281 | dstp++; ap++; bp++; cp++; | |
282 | } | |
283 | return changed; | |
284 | } | |
285 | ||
286 | /* Set DST to be (A ann (B or C)). | |
287 | Return non-zero if any change is made. */ | |
288 | ||
289 | int | |
290 | sbitmap_a_and_b_or_c (dst, a, b, c) | |
291 | sbitmap dst, a, b, c; | |
292 | { | |
293 | int i,changed; | |
294 | sbitmap_ptr dstp, ap, bp, cp; | |
295 | ||
296 | changed = 0; | |
297 | dstp = dst->elms; | |
298 | ap = a->elms; | |
299 | bp = b->elms; | |
300 | cp = c->elms; | |
301 | for (i = 0; i < dst->size; i++) | |
302 | { | |
303 | SBITMAP_ELT_TYPE tmp = *ap & (*bp | *cp); | |
304 | if (*dstp != tmp) | |
305 | changed = 1; | |
306 | *dstp = tmp; | |
307 | dstp++; ap++; bp++; cp++; | |
308 | } | |
309 | return changed; | |
310 | } | |
311 | ||
312 | /* Set the bitmap DST to the intersection of SRC of all predecessors or | |
313 | successors of block number BB (PRED_SUCC says which). */ | |
314 | ||
315 | void | |
316 | sbitmap_intersect_of_predsucc (dst, src, bb, pred_succ) | |
317 | sbitmap dst; | |
318 | sbitmap *src; | |
319 | int bb; | |
320 | int_list_ptr *pred_succ; | |
321 | { | |
322 | int_list_ptr ps; | |
323 | int ps_bb; | |
324 | int set_size = dst->size; | |
325 | ||
326 | ps = pred_succ[bb]; | |
327 | ||
328 | /* It is possible that there are no predecessors(/successors). | |
329 | This can happen for example in unreachable code. */ | |
330 | ||
331 | if (ps == NULL) | |
332 | { | |
333 | /* In APL-speak this is the `and' reduction of the empty set and thus | |
334 | the result is the identity for `and'. */ | |
335 | sbitmap_ones (dst); | |
336 | return; | |
337 | } | |
338 | ||
339 | /* Set result to first predecessor/successor. */ | |
340 | ||
341 | for ( ; ps != NULL; ps = ps->next) | |
342 | { | |
343 | ps_bb = INT_LIST_VAL (ps); | |
344 | if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK) | |
345 | continue; | |
346 | sbitmap_copy (dst, src[ps_bb]); | |
347 | /* Break out since we're only doing first predecessor. */ | |
348 | break; | |
349 | } | |
350 | if (ps == NULL) | |
351 | return; | |
352 | ||
353 | /* Now do the remaining predecessors/successors. */ | |
354 | ||
355 | for (ps = ps->next; ps != NULL; ps = ps->next) | |
356 | { | |
357 | int i; | |
358 | sbitmap_ptr p,r; | |
359 | ||
360 | ps_bb = INT_LIST_VAL (ps); | |
361 | if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK) | |
362 | continue; | |
363 | ||
364 | p = src[ps_bb]->elms; | |
365 | r = dst->elms; | |
366 | ||
367 | for (i = 0; i < set_size; i++) | |
368 | *r++ &= *p++; | |
369 | } | |
370 | } | |
371 | ||
372 | /* Set the bitmap DST to the union of SRC of all predecessors/successors of | |
373 | block number BB. */ | |
374 | ||
375 | void | |
376 | sbitmap_union_of_predsucc (dst, src, bb, pred_succ) | |
377 | sbitmap dst; | |
378 | sbitmap *src; | |
379 | int bb; | |
380 | int_list_ptr *pred_succ; | |
381 | { | |
382 | int_list_ptr ps; | |
383 | int ps_bb; | |
384 | int set_size = dst->size; | |
385 | ||
386 | ps = pred_succ[bb]; | |
387 | ||
388 | /* It is possible that there are no predecessors(/successors). | |
389 | This can happen for example in unreachable code. */ | |
390 | ||
391 | if (ps == NULL) | |
392 | { | |
393 | /* In APL-speak this is the `or' reduction of the empty set and thus | |
394 | the result is the identity for `or'. */ | |
395 | sbitmap_zero (dst); | |
396 | return; | |
397 | } | |
398 | ||
399 | /* Set result to first predecessor/successor. */ | |
400 | ||
401 | for ( ; ps != NULL; ps = ps->next) | |
402 | { | |
403 | ps_bb = INT_LIST_VAL (ps); | |
404 | if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK) | |
405 | continue; | |
406 | sbitmap_copy (dst, src[ps_bb]); | |
407 | /* Break out since we're only doing first predecessor. */ | |
408 | break; | |
409 | } | |
410 | if (ps == NULL) | |
411 | return; | |
412 | ||
413 | /* Now do the remaining predecessors/successors. */ | |
414 | ||
415 | for (ps = ps->next; ps != NULL; ps = ps->next) | |
416 | { | |
417 | int i; | |
418 | sbitmap_ptr p,r; | |
419 | ||
420 | ps_bb = INT_LIST_VAL (ps); | |
421 | if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK) | |
422 | continue; | |
423 | ||
424 | p = src[ps_bb]->elms; | |
425 | r = dst->elms; | |
426 | ||
427 | for (i = 0; i < set_size; i++) | |
428 | *r++ |= *p++; | |
429 | } | |
430 | } | |
431 | ||
432 | void | |
433 | dump_sbitmap (file, bmap) | |
434 | FILE *file; | |
435 | sbitmap bmap; | |
436 | { | |
437 | int i,j,n; | |
438 | int set_size = bmap->size; | |
439 | int total_bits = bmap->n_bits; | |
440 | ||
441 | fprintf (file, " "); | |
442 | for (i = n = 0; i < set_size && n < total_bits; i++) | |
443 | { | |
444 | for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++) | |
445 | { | |
446 | if (n != 0 && n % 10 == 0) | |
447 | fprintf (file, " "); | |
448 | fprintf (file, "%d", (bmap->elms[i] & (1L << j)) != 0); | |
449 | } | |
450 | } | |
451 | fprintf (file, "\n"); | |
452 | } | |
453 | ||
454 | void | |
455 | dump_sbitmap_vector (file, title, subtitle, bmaps, n_maps) | |
456 | FILE *file; | |
dff01034 | 457 | const char *title, *subtitle; |
5f6c11d6 RH |
458 | sbitmap *bmaps; |
459 | int n_maps; | |
460 | { | |
461 | int bb; | |
462 | ||
463 | fprintf (file, "%s\n", title); | |
464 | for (bb = 0; bb < n_maps; bb++) | |
465 | { | |
466 | fprintf (file, "%s %d\n", subtitle, bb); | |
467 | dump_sbitmap (file, bmaps[bb]); | |
468 | } | |
469 | fprintf (file, "\n"); | |
470 | } |