1/* Simple bitmaps. 2 Copyright (C) 1999 Free Software Foundation, Inc. 3 4This file is part of GNU CC. 5 6GNU CC is free software; you can redistribute it and/or modify 7it under the terms of the GNU General Public License as published by 8the Free Software Foundation; either version 2, or (at your option) 9any later version. 10 11GNU CC is distributed in the hope that it will be useful, 12but WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14GNU General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along with GNU CC; see the file COPYING. If not, write to 18the Free Software Foundation, 59 Temple Place - Suite 330, 19Boston, 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 31sbitmap 32sbitmap_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 51sbitmap * 52sbitmap_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 95void 96sbitmap_copy (dst, src) 97 sbitmap dst, src; 98{ 99 bcopy ((PTR) src->elms, (PTR) dst->elms, 100 sizeof (SBITMAP_ELT_TYPE) * dst->size); 101} 102 103/* Zero all elements in a bitmap. */ 104 105void 106sbitmap_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 114void 115sbitmap_ones (bmap) 116 sbitmap bmap; 117{ 118 memset (bmap->elms, -1, bmap->bytes); 119} 120 121/* Zero a vector of N_VECS bitmaps. */ 122 123void 124sbitmap_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 136void 137sbitmap_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 151int 152sbitmap_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 176void 177sbitmap_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 197void 198sbitmap_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 214int 215sbitmap_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 238int 239sbitmap_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 263int 264sbitmap_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 289int 290sbitmap_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 315void 316sbitmap_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 375void 376sbitmap_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 432void 433dump_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 454void 455dump_sbitmap_vector (file, title, subtitle, bmaps, n_maps) 456 FILE *file; 457 const char *title, *subtitle; 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} 471