1/* Functions to support general ended bitmaps. 2 Copyright (C) 1997, 1998 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 "obstack.h" 26#include "regs.h" 27#include "basic-block.h" 28 29/* Obstack to allocate bitmap elements from. */ 30static struct obstack bitmap_obstack; 31static int bitmap_obstack_init = FALSE; 32 33 34#ifndef INLINE 35#ifndef __GNUC__ 36#define INLINE 37#else 38#define INLINE __inline__ 39#endif 40#endif 41 42/* Global data */ 43bitmap_element bitmap_zero; /* An element of all zero bits. */ 44bitmap_element *bitmap_free; /* Freelist of bitmap elements. */ 45 46static void bitmap_element_free PROTO((bitmap, bitmap_element *)); 47static bitmap_element *bitmap_element_allocate PROTO((void)); 48static int bitmap_element_zerop PROTO((bitmap_element *)); 49static void bitmap_element_link PROTO((bitmap, bitmap_element *)); 50static bitmap_element *bitmap_find_bit PROTO((bitmap, unsigned int)); 51 52/* Free a bitmap element */ 53 54static INLINE void 55bitmap_element_free (head, elt) 56 bitmap head; 57 bitmap_element *elt; 58{ 59 bitmap_element *next = elt->next; 60 bitmap_element *prev = elt->prev; 61 62 if (prev) 63 prev->next = next; 64 65 if (next) 66 next->prev = prev; 67 68 if (head->first == elt) 69 head->first = next; 70 71 /* Since the first thing we try is to insert before current, 72 make current the next entry in preference to the previous. */ 73 if (head->current == elt) 74 head->current = next != 0 ? next : prev; 75 76 elt->next = bitmap_free; 77 bitmap_free = elt; 78} 79 80/* Allocate a bitmap element. The bits are cleared, but nothing else is. */ 81 82static INLINE bitmap_element * 83bitmap_element_allocate () 84{ 85 bitmap_element *element; 86#if BITMAP_ELEMENT_WORDS != 2 87 int i; 88#endif 89 90 if (bitmap_free != 0) 91 { 92 element = bitmap_free; 93 bitmap_free = element->next; 94 } 95 else 96 { 97 /* We can't use gcc_obstack_init to initialize the obstack since 98 print-rtl.c now calls bitmap functions, and bitmap is linked 99 into the gen* functions. */ 100 if (!bitmap_obstack_init) 101 { 102 bitmap_obstack_init = TRUE; 103 104 /* Let particular systems override the size of a chunk. */ 105#ifndef OBSTACK_CHUNK_SIZE 106#define OBSTACK_CHUNK_SIZE 0 107#endif 108 /* Let them override the alloc and free routines too. */ 109#ifndef OBSTACK_CHUNK_ALLOC 110#define OBSTACK_CHUNK_ALLOC xmalloc 111#endif 112#ifndef OBSTACK_CHUNK_FREE 113#define OBSTACK_CHUNK_FREE free 114#endif 115 116#if !defined(__GNUC__) || (__GNUC__ < 2) 117#define __alignof__(type) 0 118#endif 119 120 obstack_specify_allocation (&bitmap_obstack, OBSTACK_CHUNK_SIZE, 121 __alignof__ (bitmap_element), 122 (void *(*) ()) OBSTACK_CHUNK_ALLOC, 123 (void (*) ()) OBSTACK_CHUNK_FREE); 124 } 125 126 element = (bitmap_element *) obstack_alloc (&bitmap_obstack, 127 sizeof (bitmap_element)); 128 } 129 130#if BITMAP_ELEMENT_WORDS == 2 131 element->bits[0] = element->bits[1] = 0; 132#else 133 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) 134 element->bits[i] = 0; 135#endif 136 137 return element; 138} 139 140/* Return nonzero if all bits in an element are zero. */ 141 142static INLINE int 143bitmap_element_zerop (element) 144 bitmap_element *element; 145{ 146#if BITMAP_ELEMENT_WORDS == 2 147 return (element->bits[0] | element->bits[1]) == 0; 148#else 149 int i; 150 151 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) 152 if (element->bits[i] != 0) 153 return 0; 154 155 return 1; 156#endif 157} 158 159/* Link the bitmap element into the current bitmap linked list. */ 160 161static INLINE void 162bitmap_element_link (head, element) 163 bitmap head; 164 bitmap_element *element; 165{ 166 unsigned int indx = element->indx; 167 bitmap_element *ptr; 168 169 /* If this is the first and only element, set it in. */ 170 if (head->first == 0) 171 { 172 element->next = element->prev = 0; 173 head->first = element; 174 } 175 176 /* If this index is less than that of the current element, it goes someplace 177 before the current element. */ 178 else if (indx < head->indx) 179 { 180 for (ptr = head->current; 181 ptr->prev != 0 && ptr->prev->indx > indx; 182 ptr = ptr->prev) 183 ; 184 185 if (ptr->prev) 186 ptr->prev->next = element; 187 else 188 head->first = element; 189 190 element->prev = ptr->prev; 191 element->next = ptr; 192 ptr->prev = element; 193 } 194 195 /* Otherwise, it must go someplace after the current element. */ 196 else 197 { 198 for (ptr = head->current; 199 ptr->next != 0 && ptr->next->indx < indx; 200 ptr = ptr->next) 201 ; 202 203 if (ptr->next) 204 ptr->next->prev = element; 205 206 element->next = ptr->next; 207 element->prev = ptr; 208 ptr->next = element; 209 } 210 211 /* Set up so this is the first element searched. */ 212 head->current = element; 213 head->indx = indx; 214} 215 216/* Clear a bitmap by freeing the linked list. */ 217 218INLINE void 219bitmap_clear (head) 220 bitmap head; 221{ 222 bitmap_element *element, *next; 223 224 for (element = head->first; element != 0; element = next) 225 { 226 next = element->next; 227 element->next = bitmap_free; 228 bitmap_free = element; 229 } 230 231 head->first = head->current = 0; 232} 233 234/* Copy a bitmap to another bitmap */ 235 236void 237bitmap_copy (to, from) 238 bitmap to; 239 bitmap from; 240{ 241 bitmap_element *from_ptr, *to_ptr = 0; 242#if BITMAP_ELEMENT_WORDS != 2 243 int i; 244#endif 245 246 bitmap_clear (to); 247 248 /* Copy elements in forward direction one at a time */ 249 for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next) 250 { 251 bitmap_element *to_elt = bitmap_element_allocate (); 252 253 to_elt->indx = from_ptr->indx; 254 255#if BITMAP_ELEMENT_WORDS == 2 256 to_elt->bits[0] = from_ptr->bits[0]; 257 to_elt->bits[1] = from_ptr->bits[1]; 258#else 259 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) 260 to_elt->bits[i] = from_ptr->bits[i]; 261#endif 262 263 /* Here we have a special case of bitmap_element_link, for the case 264 where we know the links are being entered in sequence. */ 265 if (to_ptr == 0) 266 { 267 to->first = to->current = to_elt; 268 to->indx = from_ptr->indx; 269 to_elt->next = to_elt->prev = 0; 270 } 271 else 272 { 273 to_elt->prev = to_ptr; 274 to_elt->next = 0; 275 to_ptr->next = to_elt; 276 } 277 278 to_ptr = to_elt; 279 } 280} 281 282/* Find a bitmap element that would hold a bitmap's bit. 283 Update the `current' field even if we can't find an element that 284 would hold the bitmap's bit to make eventual allocation 285 faster. */ 286 287static INLINE bitmap_element * 288bitmap_find_bit (head, bit) 289 bitmap head; 290 unsigned int bit; 291{ 292 bitmap_element *element; 293 unsigned HOST_WIDE_INT indx = bit / BITMAP_ELEMENT_ALL_BITS; 294 295 if (head->current == 0) 296 return 0; 297 298 if (head->indx > indx) 299 for (element = head->current; 300 element->prev != 0 && element->indx > indx; 301 element = element->prev) 302 ; 303 304 else 305 for (element = head->current; 306 element->next != 0 && element->indx < indx; 307 element = element->next) 308 ; 309 310 /* `element' is the nearest to the one we want. If it's not the one we 311 want, the one we want doesn't exist. */ 312 head->current = element; 313 head->indx = element->indx; 314 if (element != 0 && element->indx != indx) 315 element = 0; 316 317 return element; 318} 319 320/* Clear a single bit in a bitmap. */ 321 322void 323bitmap_clear_bit (head, bit) 324 bitmap head; 325 int bit; 326{ 327 bitmap_element *ptr = bitmap_find_bit (head, bit); 328 329 if (ptr != 0) 330 { 331 unsigned bit_num = bit % (unsigned) HOST_BITS_PER_WIDE_INT; 332 unsigned word_num = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) 333 % BITMAP_ELEMENT_WORDS); 334 ptr->bits[word_num] &= ~ (((unsigned HOST_WIDE_INT) 1) << bit_num); 335 336 /* If we cleared the entire word, free up the element */ 337 if (bitmap_element_zerop (ptr)) 338 bitmap_element_free (head, ptr); 339 } 340} 341 342 343/* Set a single bit in a bitmap. */ 344 345void 346bitmap_set_bit (head, bit) 347 bitmap head; 348 int bit; 349{ 350 bitmap_element *ptr = bitmap_find_bit (head, bit); 351 unsigned word_num 352 = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) % BITMAP_ELEMENT_WORDS); 353 unsigned bit_num = bit % (unsigned) HOST_BITS_PER_WIDE_INT; 354 unsigned HOST_WIDE_INT bit_val = ((unsigned HOST_WIDE_INT) 1) << bit_num; 355 356 if (ptr == 0) 357 { 358 ptr = bitmap_element_allocate (); 359 ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS; 360 ptr->bits[word_num] = bit_val; 361 bitmap_element_link (head, ptr); 362 } 363 else 364 ptr->bits[word_num] |= bit_val; 365} 366 367/* Return whether a bit is set within a bitmap. */ 368 369int 370bitmap_bit_p (head, bit) 371 bitmap head; 372 int bit; 373{ 374 bitmap_element *ptr; 375 unsigned bit_num; 376 unsigned word_num; 377 378 ptr = bitmap_find_bit (head, bit); 379 if (ptr == 0) 380 return 0; 381 382 bit_num = bit % (unsigned) HOST_BITS_PER_WIDE_INT; 383 word_num 384 = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) % BITMAP_ELEMENT_WORDS); 385 386 return 387 (ptr->bits[word_num] & (((unsigned HOST_WIDE_INT) 1) << bit_num)) != 0; 388} 389 390/* Store in bitmap TO the result of combining bitmap FROM1 and 391 FROM2 using a specific bit manipulation. */ 392 393void 394bitmap_operation (to, from1, from2, operation) 395 bitmap to; 396 bitmap from1; 397 bitmap from2; 398 enum bitmap_bits operation; 399{ 400 bitmap_element *delete_list = 0; 401 bitmap_element *from1_ptr = from1->first; 402 bitmap_element *from2_ptr = from2->first; 403 unsigned int indx1 404 = (from1_ptr) ? from1_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0; 405 unsigned int indx2 406 = (from2_ptr) ? from2_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0; 407 bitmap_element *to_ptr = 0; 408 bitmap_element *from1_tmp; 409 bitmap_element *from2_tmp; 410 unsigned int indx; 411#if BITMAP_ELEMENT_WORDS != 2 412 int i; 413#endif 414 415 /* To simplify things, always create a new list. If the old list was one 416 of the inputs, free it later. Otherwise, free it now. */ 417 if (to == from1 || to == from2) 418 { 419 delete_list = to->first; 420 to->first = to->current = 0; 421 } 422 else 423 bitmap_clear (to); 424 425 while (from1_ptr != 0 || from2_ptr != 0) 426 { 427 /* Figure out whether we need to substitute zero elements for 428 missing links. */ 429 if (indx1 == indx2) 430 { 431 indx = indx1; 432 from1_tmp = from1_ptr; 433 from2_tmp = from2_ptr; 434 from1_ptr = from1_ptr->next; 435 indx1 = (from1_ptr) ? from1_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0; 436 from2_ptr = from2_ptr->next; 437 indx2 = (from2_ptr) ? from2_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0; 438 } 439 else if (indx1 < indx2) 440 { 441 indx = indx1; 442 from1_tmp = from1_ptr; 443 from2_tmp = &bitmap_zero; 444 from1_ptr = from1_ptr->next; 445 indx1 = (from1_ptr) ? from1_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0; 446 } 447 else 448 { 449 indx = indx2; 450 from1_tmp = &bitmap_zero; 451 from2_tmp = from2_ptr; 452 from2_ptr = from2_ptr->next; 453 indx2 = (from2_ptr) ? from2_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0; 454 } 455 456 if (to_ptr == 0) 457 to_ptr = bitmap_element_allocate (); 458 459 /* Do the operation, and if any bits are set, link it into the 460 linked list. */ 461 switch (operation) 462 { 463 default: 464 abort (); 465 466 case BITMAP_AND: 467#if BITMAP_ELEMENT_WORDS == 2 468 to_ptr->bits[0] = from1_tmp->bits[0] & from2_tmp->bits[0]; 469 to_ptr->bits[1] = from1_tmp->bits[1] & from2_tmp->bits[1]; 470#else 471 for (i = BITMAP_ELEMENT_WORDS - 1; i >= 0; i--) 472 to_ptr->bits[i] = from1_tmp->bits[i] & from2_tmp->bits[i]; 473#endif 474 break; 475 476 case BITMAP_AND_COMPL: 477#if BITMAP_ELEMENT_WORDS == 2 478 to_ptr->bits[0] = from1_tmp->bits[0] & ~ from2_tmp->bits[0]; 479 to_ptr->bits[1] = from1_tmp->bits[1] & ~ from2_tmp->bits[1]; 480#else 481 for (i = BITMAP_ELEMENT_WORDS - 1; i >= 0; i--) 482 to_ptr->bits[i] = from1_tmp->bits[i] & ~ from2_tmp->bits[i]; 483#endif 484 break; 485 486 case BITMAP_IOR: 487#if BITMAP_ELEMENT_WORDS == 2 488 to_ptr->bits[0] = from1_tmp->bits[0] | from2_tmp->bits[0]; 489 to_ptr->bits[1] = from1_tmp->bits[1] | from2_tmp->bits[1]; 490#else 491 for (i = BITMAP_ELEMENT_WORDS - 1; i >= 0; i--) 492 to_ptr->bits[i] = from1_tmp->bits[i] | from2_tmp->bits[i]; 493#endif 494 break; 495 } 496 497 if (! bitmap_element_zerop (to_ptr)) 498 { 499 to_ptr->indx = indx; 500 bitmap_element_link (to, to_ptr); 501 to_ptr = 0; 502 } 503 } 504 505 /* If we have an unallocated element due to the last element being 0, 506 release it back to the free pool. Don't bother calling 507 bitmap_element_free since it was never linked into a bitmap. */ 508 if (to_ptr != 0) 509 { 510 to_ptr->next = bitmap_free; 511 bitmap_free = to_ptr; 512 } 513 514 /* If the output bitmap was one of the inputs, free up its 515 elements now that we're done. */ 516 for (; delete_list != 0; delete_list = to_ptr) 517 { 518 to_ptr = delete_list->next; 519 delete_list->next = bitmap_free; 520 bitmap_free = delete_list; 521 } 522} 523 524/* Or into bitmap TO bitmap FROM1 and'ed with the complement of 525 bitmap FROM2. */ 526 527void 528bitmap_ior_and_compl (to, from1, from2) 529 bitmap to; 530 bitmap from1; 531 bitmap from2; 532{ 533 bitmap_head tmp; 534 535 tmp.first = tmp.current = 0; 536 537 bitmap_operation (&tmp, from1, from2, BITMAP_AND_COMPL); 538 bitmap_operation (to, to, &tmp, BITMAP_IOR); 539 bitmap_clear (&tmp); 540} 541 542/* Initialize a bitmap header. */ 543 544bitmap 545bitmap_initialize (head) 546 bitmap head; 547{ 548 head->first = head->current = 0; 549 550 return head; 551} 552 553/* Debugging function to print out the contents of a bitmap. */ 554 555void 556bitmap_debug_file (file, head) 557 FILE *file; 558 bitmap head; 559{ 560 bitmap_element *ptr; 561 562 fprintf (file, "\nfirst = "); 563 fprintf (file, HOST_PTR_PRINTF, head->first); 564 fprintf (file, " current = "); 565 fprintf (file, HOST_PTR_PRINTF, head->current); 566 fprintf (file, " indx = %u\n", head->indx); 567 568 for (ptr = head->first; ptr; ptr = ptr->next) 569 { 570 int i, j, col = 26; 571 572 fprintf (file, "\t"); 573 fprintf (file, HOST_PTR_PRINTF, ptr); 574 fprintf (file, " next = "); 575 fprintf (file, HOST_PTR_PRINTF, ptr->next); 576 fprintf (file, " prev = "); 577 fprintf (file, HOST_PTR_PRINTF, ptr->prev); 578 fprintf (file, " indx = %u\n\t\tbits = {", ptr->indx); 579 580 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) 581 for (j = 0; j < HOST_BITS_PER_WIDE_INT; j++) 582 if ((ptr->bits[i] & (((unsigned HOST_WIDE_INT) 1) << j)) != 0) 583 { 584 if (col > 70) 585 { 586 fprintf (file, "\n\t\t\t"); 587 col = 24; 588 } 589 590 fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS 591 + i * HOST_BITS_PER_WIDE_INT + j)); 592 col += 4; 593 } 594 595 fprintf (file, " }\n"); 596 } 597} 598 599/* Function to be called from the debugger to print the contents 600 of a bitmap. */ 601 602void 603debug_bitmap (head) 604 bitmap head; 605{ 606 bitmap_debug_file (stdout, head); 607} 608 609/* Function to print out the contents of a bitmap. Unlike bitmap_debug_file, 610 it does not print anything but the bits. */ 611 612void 613bitmap_print (file, head, prefix, suffix) 614 FILE *file; 615 bitmap head; 616 const char *prefix; 617 const char *suffix; 618{ 619 const char *comma = ""; 620 int i; 621 622 fputs (prefix, file); 623 EXECUTE_IF_SET_IN_BITMAP (head, 0, i, 624 { 625 fprintf (file, "%s%d", comma, i); 626 comma = ", "; 627 }); 628 fputs (suffix, file); 629} 630 631/* Release any memory allocated by bitmaps. */ 632 633void 634bitmap_release_memory () 635{ 636 bitmap_free = 0; 637 if (bitmap_obstack_init) 638 { 639 bitmap_obstack_init = FALSE; 640 obstack_free (&bitmap_obstack, NULL_PTR); 641 } 642} 643