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
  33 \f
  34 #ifndef INLINE
  35 #ifndef __GNUC__
  36 #define INLINE
  37 #else
  38 #define INLINE __inline__
  39 #endif
  40 #endif
  41
  42 /* Global data */
  43 bitmap_element bitmap_zero;             /* An element of all zero bits. */
  44 bitmap_element *bitmap_free;            /* Freelist of bitmap elements. */
  45
  46 static void bitmap_element_free         PROTO((bitmap, bitmap_element *));
  47 static bitmap_element *bitmap_element_allocate PROTO((void));
  48 static int bitmap_element_zerop         PROTO((bitmap_element *));
  49 static void bitmap_element_link         PROTO((bitmap, bitmap_element *));
  50 static bitmap_element *bitmap_find_bit  PROTO((bitmap, unsigned int));
  51 \f
  52 /* Free a bitmap element */
  53
  54 static INLINE void
  55 bitmap_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 \f
  80 /* Allocate a bitmap element.  The bits are cleared, but nothing else is.  */
  81
  82 static INLINE bitmap_element *
  83 bitmap_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
 142 static INLINE int
 143 bitmap_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 \f
 159 /* Link the bitmap element into the current bitmap linked list.  */
 160
 161 static INLINE void
 162 bitmap_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 \f
 216 /* Clear a bitmap by freeing the linked list.  */
 217
 218 INLINE void
 219 bitmap_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 \f
 234 /* Copy a bitmap to another bitmap */
 235
 236 void
 237 bitmap_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 \f
 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
 287 static INLINE bitmap_element *
 288 bitmap_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 \f
 320 /* Clear a single bit in a bitmap.  */
 321
 322 void
 323 bitmap_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 \f
 343 /* Set a single bit in a bitmap.  */
 344
 345 void
 346 bitmap_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 \f
 367 /* Return whether a bit is set within a bitmap.  */
 368
 369 int
 370 bitmap_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 \f
 390 /* Store in bitmap TO the result of combining bitmap FROM1 and
 391    FROM2 using a specific bit manipulation.  */
 392
 393 void
 394 bitmap_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 \f
 524 /* Or into bitmap TO bitmap FROM1 and'ed with the complement of
 525    bitmap FROM2. */
 526
 527 void
 528 bitmap_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 \f
 542 /* Initialize a bitmap header.  */
 543
 544 bitmap
 545 bitmap_initialize (head)
 546      bitmap head;
 547 {
 548   head->first = head->current = 0;
 549
 550   return head;
 551 }
 552 \f
 553 /* Debugging function to print out the contents of a bitmap.  */
 554
 555 void
 556 bitmap_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 \f
 599 /* Function to be called from the debugger to print the contents
 600    of a bitmap.  */
 601
 602 void
 603 debug_bitmap (head)
 604      bitmap head;
 605 {
 606   bitmap_debug_file (stdout, head);
 607 }
 608 \f
 609 /* Function to print out the contents of a bitmap.  Unlike bitmap_debug_file,
 610    it does not print anything but the bits.  */
 611
 612 void
 613 bitmap_print (file, head, prefix, suffix)
 614      FILE *file;
 615      bitmap head;
 616      char *prefix;
 617      char *suffix;
 618 {
 619   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 \f
 631 /* Release any memory allocated by bitmaps.  */
 632
 633 void
 634 bitmap_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 }