gcc/bitmap.c

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