sbitmap.c revision 52284
1100280Sgordon/* Simple bitmaps. 225184Sjkh Copyright (C) 1999 Free Software Foundation, Inc. 350472Speter 466830SobrienThis file is part of GNU CC. 525184Sjkh 6100280SgordonGNU CC is free software; you can redistribute it and/or modify 7100280Sgordonit under the terms of the GNU General Public License as published by 8100280Sgordonthe Free Software Foundation; either version 2, or (at your option) 925184Sjkhany later version. 10100280Sgordon 1125184SjkhGNU CC is distributed in the hope that it will be useful, 12100280Sgordonbut WITHOUT ANY WARRANTY; without even the implied warranty of 13100280SgordonMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14100280SgordonGNU General Public License for more details. 15100280Sgordon 16100280SgordonYou should have received a copy of the GNU General Public License 17100280Sgordonalong with GNU CC; see the file COPYING. If not, write to 18100280Sgordonthe Free Software Foundation, 59 Temple Place - Suite 330, 19100280SgordonBoston, MA 02111-1307, USA. */ 20100280Sgordon 21100280Sgordon#include "config.h" 22100280Sgordon#include "system.h" 23100280Sgordon#include "rtl.h" 24100280Sgordon#include "flags.h" 25100280Sgordon#include "basic-block.h" 26100280Sgordon 27100280Sgordon/* Bitmap manipulation routines. */ 28100280Sgordon 29100280Sgordon/* Allocate a simple bitmap of N_ELMS bits. */ 30100280Sgordon 31100280Sgordonsbitmap 32100280Sgordonsbitmap_alloc (n_elms) 33100280Sgordon int n_elms; 34100280Sgordon{ 35100280Sgordon int bytes, size, amt; 36100280Sgordon sbitmap bmap; 37100280Sgordon 38100280Sgordon size = SBITMAP_SET_SIZE (n_elms); 39100280Sgordon bytes = size * sizeof (SBITMAP_ELT_TYPE); 40100280Sgordon amt = (sizeof (struct simple_bitmap_def) 41100280Sgordon + bytes - sizeof (SBITMAP_ELT_TYPE)); 42100280Sgordon bmap = (sbitmap) xmalloc (amt); 43100280Sgordon bmap->n_bits = n_elms; 44100280Sgordon bmap->size = size; 45100280Sgordon bmap->bytes = bytes; 46100280Sgordon return bmap; 47100280Sgordon} 48100280Sgordon 49100280Sgordon/* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */ 50100280Sgordon 51100280Sgordonsbitmap * 52100280Sgordonsbitmap_vector_alloc (n_vecs, n_elms) 53100280Sgordon int n_vecs, n_elms; 54100280Sgordon{ 55100280Sgordon int i, bytes, offset, elm_bytes, size, amt, vector_bytes; 56100280Sgordon sbitmap *bitmap_vector; 57100280Sgordon 58100280Sgordon size = SBITMAP_SET_SIZE (n_elms); 59100280Sgordon bytes = size * sizeof (SBITMAP_ELT_TYPE); 60100280Sgordon elm_bytes = (sizeof (struct simple_bitmap_def) 61100280Sgordon + bytes - sizeof (SBITMAP_ELT_TYPE)); 62100280Sgordon vector_bytes = n_vecs * sizeof (sbitmap *); 63100280Sgordon 64100282Sdougb /* Round up `vector_bytes' to account for the alignment requirements 65100282Sdougb of an sbitmap. One could allocate the vector-table and set of sbitmaps 66100282Sdougb separately, but that requires maintaining two pointers or creating 67100282Sdougb a cover struct to hold both pointers (so our result is still just 68100282Sdougb one pointer). Neither is a bad idea, but this is simpler for now. */ 69100282Sdougb { 70100282Sdougb /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */ 71100282Sdougb struct { char x; SBITMAP_ELT_TYPE y; } align; 72100282Sdougb int alignment = (char *) & align.y - & align.x; 73100282Sdougb vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1); 74100282Sdougb } 75100282Sdougb 76100282Sdougb amt = vector_bytes + (n_vecs * elm_bytes); 77100282Sdougb bitmap_vector = (sbitmap *) xmalloc (amt); 78103710Sume 79100282Sdougb for (i = 0, offset = vector_bytes; 80100282Sdougb i < n_vecs; 81100282Sdougb i++, offset += elm_bytes) 82100282Sdougb { 83100282Sdougb sbitmap b = (sbitmap) ((char *) bitmap_vector + offset); 84100282Sdougb bitmap_vector[i] = b; 85100282Sdougb b->n_bits = n_elms; 86100280Sgordon b->size = size; 87100280Sgordon b->bytes = bytes; 88100280Sgordon } 89100280Sgordon 90100280Sgordon return bitmap_vector; 91100280Sgordon} 9285831Sdes 9385831Sdes/* Copy sbitmap SRC to DST. */ 9485831Sdes 9586163Sfennervoid 9685831Sdessbitmap_copy (dst, src) 9785831Sdes sbitmap dst, src; 9885831Sdes{ 9965532Snectar bcopy ((PTR) src->elms, (PTR) dst->elms, 10085831Sdes sizeof (SBITMAP_ELT_TYPE) * dst->size); 10185831Sdes} 10270108Sdougb 10370108Sdougb/* Zero all elements in a bitmap. */ 10485831Sdes 10585831Sdesvoid 10665532Snectarsbitmap_zero (bmap) 10765532Snectar sbitmap bmap; 10851231Ssheldonh{ 10951231Ssheldonh bzero ((char *) bmap->elms, bmap->bytes); 11051231Ssheldonh} 11151231Ssheldonh 11251231Ssheldonh/* Set to ones all elements in a bitmap. */ 11351231Ssheldonh 11425184Sjkhvoid 11551231Ssheldonhsbitmap_ones (bmap) 11651231Ssheldonh sbitmap bmap; 117100283Sdougb{ 118100283Sdougb memset (bmap->elms, -1, bmap->bytes); 119100283Sdougb} 120100283Sdougb 12151231Ssheldonh/* Zero a vector of N_VECS bitmaps. */ 12251231Ssheldonh 123100283Sdougbvoid 124100283Sdougbsbitmap_vector_zero (bmap, n_vecs) 12540006Sphk sbitmap *bmap; 126100282Sdougb int n_vecs; 127100282Sdougb{ 12883677Sbrooks int i; 12983677Sbrooks 13083677Sbrooks for (i = 0; i < n_vecs; i++) 13183677Sbrooks sbitmap_zero (bmap[i]); 13283677Sbrooks} 133100282Sdougb 134100282Sdougb/* Set to ones a vector of N_VECS bitmaps. */ 135100282Sdougb 13651231Ssheldonhvoid 13751231Ssheldonhsbitmap_vector_ones (bmap, n_vecs) 13851231Ssheldonh sbitmap *bmap; 13951231Ssheldonh int n_vecs; 14051231Ssheldonh{ 14151231Ssheldonh int i; 14283677Sbrooks 14383677Sbrooks for (i = 0; i < n_vecs; i++) 14483677Sbrooks sbitmap_ones (bmap[i]); 14551231Ssheldonh} 14649122Sbrian 14754458Sobrien/* Set DST to be A union (B - C). 14851231Ssheldonh DST = A | (B & ~C). 14951231Ssheldonh Return non-zero if any change is made. */ 15051231Ssheldonh 15154458Sobrienint 15251231Ssheldonhsbitmap_union_of_diff (dst, a, b, c) 15349122Sbrian sbitmap dst, a, b, c; 15451231Ssheldonh{ 15551231Ssheldonh int i,changed; 15651231Ssheldonh sbitmap_ptr dstp, ap, bp, cp; 15729300Sdanny 15851231Ssheldonh changed = 0; 15951231Ssheldonh dstp = dst->elms; 16051231Ssheldonh ap = a->elms; 16151231Ssheldonh bp = b->elms; 16254458Sobrien cp = c->elms; 16354458Sobrien for (i = 0; i < dst->size; i++) 16454458Sobrien { 16551231Ssheldonh SBITMAP_ELT_TYPE tmp = *ap | (*bp & ~*cp); 16651231Ssheldonh if (*dstp != tmp) 16751231Ssheldonh changed = 1; 16854458Sobrien *dstp = tmp; 16951231Ssheldonh dstp++; ap++; bp++; cp++; 17051231Ssheldonh } 17154458Sobrien return changed; 17251231Ssheldonh} 17354458Sobrien 174100281Sgordon/* Set bitmap DST to the bitwise negation of the bitmap SRC. */ 175100281Sgordon 17654458Sobrienvoid 17754458Sobriensbitmap_not (dst, src) 17851231Ssheldonh sbitmap dst, src; 17951231Ssheldonh{ 18051231Ssheldonh int i; 18151231Ssheldonh sbitmap_ptr dstp, ap; 18251231Ssheldonh 18351231Ssheldonh dstp = dst->elms; 18451231Ssheldonh ap = src->elms; 18554458Sobrien for (i = 0; i < dst->size; i++) 18686342Ssheldonh { 18751231Ssheldonh SBITMAP_ELT_TYPE tmp = ~(*ap); 18851231Ssheldonh *dstp = tmp; 18951231Ssheldonh dstp++; ap++; 19051231Ssheldonh } 19151231Ssheldonh} 19251231Ssheldonh 19351231Ssheldonh/* Set the bits in DST to be the difference between the bits 19451231Ssheldonh in A and the bits in B. i.e. dst = a - b. 19551231Ssheldonh The - operator is implemented as a & (~b). */ 19651231Ssheldonh 19754458Sobrienvoid 19851231Ssheldonhsbitmap_difference (dst, a, b) 19954458Sobrien sbitmap dst, a, b; 20051231Ssheldonh{ 201101594Sgordon int i; 20254458Sobrien sbitmap_ptr dstp, ap, bp; 20354458Sobrien 20454458Sobrien dstp = dst->elms; 20551231Ssheldonh ap = a->elms; 20654458Sobrien bp = b->elms; 20751231Ssheldonh for (i = 0; i < dst->size; i++) 20851231Ssheldonh *dstp++ = *ap++ & (~*bp++); 209100280Sgordon} 210100280Sgordon 21125184Sjkh/* Set DST to be (A and B)). 21225184Sjkh Return non-zero if any change is made. */ 213100280Sgordon 214100280Sgordonint 215100282Sdougbsbitmap_a_and_b (dst, a, b) 21625184Sjkh sbitmap dst, a, b; 217100280Sgordon{ 218100280Sgordon int i,changed; 219100282Sdougb sbitmap_ptr dstp, ap, bp; 220100280Sgordon 22153314Sache changed = 0; 222100282Sdougb dstp = dst->elms; 22353314Sache ap = a->elms; 22465532Snectar bp = b->elms; 225100280Sgordon for (i = 0; i < dst->size; i++) 226100280Sgordon { 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