gcc/bitmap.c

   1 /* Functions to support general ended bitmaps.
   2    Copyright (C) 1997, 1998, 1999, 2000 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 "bitmap.h"
  27
  28 /* Obstack to allocate bitmap elements from.  */
  29 static struct obstack bitmap_obstack;
  30 static int bitmap_obstack_init = FALSE;
  31 \f
  32 #ifndef INLINE
  33 #ifndef __GNUC__
  34 #define INLINE
  35 #else
  36 #define INLINE __inline__
  37 #endif
  38 #endif
  39
  40 /* Global data */
  41 bitmap_element bitmap_zero;             /* An element of all zero bits. */
  42 bitmap_element *bitmap_free;            /* Freelist of bitmap elements. */
  43
  44 static void bitmap_element_free         PARAMS ((bitmap, bitmap_element *));
  45 static bitmap_element *bitmap_element_allocate PARAMS ((void));
  46 static int bitmap_element_zerop         PARAMS ((bitmap_element *));
  47 static void bitmap_element_link         PARAMS ((bitmap, bitmap_element *));
  48 static bitmap_element *bitmap_find_bit  PARAMS ((bitmap, unsigned int));
  49 \f
  50 /* Free a bitmap element */
  51
  52 static INLINE void
  53 bitmap_element_free (head, elt)
  54      bitmap head;
  55      bitmap_element *elt;
  56 {
  57   bitmap_element *next = elt->next;
  58   bitmap_element *prev = elt->prev;
  59
  60   if (prev)
  61     prev->next = next;
  62
  63   if (next)
  64     next->prev = prev;
  65
  66   if (head->first == elt)
  67     head->first = next;
  68
  69   /* Since the first thing we try is to insert before current,
  70      make current the next entry in preference to the previous.  */
  71   if (head->current == elt)
  72     head->current = next != 0 ? next : prev;
  73
  74   elt->next = bitmap_free;
  75   bitmap_free = elt;
  76 }
  77 \f
  78 /* Allocate a bitmap element.  The bits are cleared, but nothing else is.  */
  79
  80 static INLINE bitmap_element *
  81 bitmap_element_allocate ()
  82 {
  83   bitmap_element *element;
  84 #if BITMAP_ELEMENT_WORDS != 2
  85   int i;
  86 #endif
  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 *(*) PARAMS ((long))) OBSTACK_CHUNK_ALLOC,
 121                                       (void (*) PARAMS ((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 INLINE void
 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 #if BITMAP_ELEMENT_WORDS != 2
 241   int i;
 242 #endif
 243
 244   bitmap_clear (to);
 245
 246   /* Copy elements in forward direction one at a time */
 247   for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
 248     {
 249       bitmap_element *to_elt = bitmap_element_allocate ();
 250
 251       to_elt->indx = from_ptr->indx;
 252
 253 #if BITMAP_ELEMENT_WORDS == 2
 254       to_elt->bits[0] = from_ptr->bits[0];
 255       to_elt->bits[1] = from_ptr->bits[1];
 256 #else
 257       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
 258         to_elt->bits[i] = from_ptr->bits[i];
 259 #endif
 260
 261       /* Here we have a special case of bitmap_element_link, for the case
 262          where we know the links are being entered in sequence.  */
 263       if (to_ptr == 0)
 264         {
 265           to->first = to->current = to_elt;
 266           to->indx = from_ptr->indx;
 267           to_elt->next = to_elt->prev = 0;
 268         }
 269       else
 270         {
 271           to_elt->prev = to_ptr;
 272           to_elt->next = 0;
 273           to_ptr->next = to_elt;
 274         }
 275
 276       to_ptr = to_elt;
 277     }
 278 }
 279 \f
 280 /* Find a bitmap element that would hold a bitmap's bit.
 281    Update the `current' field even if we can't find an element that
 282    would hold the bitmap's bit to make eventual allocation
 283    faster.  */
 284
 285 static INLINE bitmap_element *
 286 bitmap_find_bit (head, bit)
 287      bitmap head;
 288      unsigned int bit;
 289 {
 290   bitmap_element *element;
 291   unsigned HOST_WIDE_INT indx = bit / BITMAP_ELEMENT_ALL_BITS;
 292
 293   if (head->current == 0)
 294     return 0;
 295
 296   if (head->indx > indx)
 297     for (element = head->current;
 298          element->prev != 0 && element->indx > indx;
 299          element = element->prev)
 300       ;
 301
 302   else
 303     for (element = head->current;
 304          element->next != 0 && element->indx < indx;
 305          element = element->next)
 306       ;
 307
 308   /* `element' is the nearest to the one we want.  If it's not the one we
 309      want, the one we want doesn't exist.  */
 310   head->current = element;
 311   head->indx = element->indx;
 312   if (element != 0 && element->indx != indx)
 313     element = 0;
 314
 315   return element;
 316 }
 317 \f
 318 /* Clear a single bit in a bitmap.  */
 319
 320 void
 321 bitmap_clear_bit (head, bit)
 322      bitmap head;
 323      int bit;
 324 {
 325   bitmap_element *ptr = bitmap_find_bit (head, bit);
 326
 327   if (ptr != 0)
 328     {
 329       unsigned bit_num  = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
 330       unsigned word_num = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT)
 331                            % BITMAP_ELEMENT_WORDS);
 332       ptr->bits[word_num] &= ~ (((unsigned HOST_WIDE_INT) 1) << bit_num);
 333
 334       /* If we cleared the entire word, free up the element */
 335       if (bitmap_element_zerop (ptr))
 336         bitmap_element_free (head, ptr);
 337     }
 338 }
 339
 340 \f
 341 /* Set a single bit in a bitmap.  */
 342
 343 void
 344 bitmap_set_bit (head, bit)
 345      bitmap head;
 346      int bit;
 347 {
 348   bitmap_element *ptr = bitmap_find_bit (head, bit);
 349   unsigned word_num
 350     = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) % BITMAP_ELEMENT_WORDS);
 351   unsigned bit_num  = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
 352   unsigned HOST_WIDE_INT bit_val = ((unsigned HOST_WIDE_INT) 1) << bit_num;
 353
 354   if (ptr == 0)
 355     {
 356       ptr = bitmap_element_allocate ();
 357       ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
 358       ptr->bits[word_num] = bit_val;
 359       bitmap_element_link (head, ptr);
 360     }
 361   else
 362     ptr->bits[word_num] |= bit_val;
 363 }
 364 \f
 365 /* Return whether a bit is set within a bitmap.  */
 366
 367 int
 368 bitmap_bit_p (head, bit)
 369      bitmap head;
 370      int bit;
 371 {
 372   bitmap_element *ptr;
 373   unsigned bit_num;
 374   unsigned word_num;
 375
 376   ptr = bitmap_find_bit (head, bit);
 377   if (ptr == 0)
 378     return 0;
 379
 380   bit_num = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
 381   word_num
 382     = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) % BITMAP_ELEMENT_WORDS);
 383
 384   return (ptr->bits[word_num] >> bit_num) & 1;
 385 }
 386 \f
 387 /* Store in bitmap TO the result of combining bitmap FROM1 and FROM2 using
 388    a specific bit manipulation.  Return true if TO changes.  */
 389
 390 int
 391 bitmap_operation (to, from1, from2, operation)
 392      bitmap to;
 393      bitmap from1;
 394      bitmap from2;
 395      enum bitmap_bits operation;
 396 {
 397 #define HIGHEST_INDEX (unsigned int) ~0
 398
 399   bitmap_element *from1_ptr = from1->first;
 400   bitmap_element *from2_ptr = from2->first;
 401   unsigned int indx1 = (from1_ptr) ? from1_ptr->indx : HIGHEST_INDEX;
 402   unsigned int indx2 = (from2_ptr) ? from2_ptr->indx : HIGHEST_INDEX;
 403   bitmap_element *to_ptr = to->first;
 404   bitmap_element *from1_tmp;
 405   bitmap_element *from2_tmp;
 406   bitmap_element *to_tmp;
 407   unsigned int indx;
 408   int changed = 0;
 409
 410 #if BITMAP_ELEMENT_WORDS == 2
 411 #define DOIT(OP)                                        \
 412   do {                                                  \
 413     unsigned HOST_WIDE_INT t0, t1, f10, f11, f20, f21;  \
 414     f10 = from1_tmp->bits[0];                           \
 415     f20 = from2_tmp->bits[0];                           \
 416     t0 = f10 OP f20;                                    \
 417     changed |= (t0 != to_tmp->bits[0]);                 \
 418     f11 = from1_tmp->bits[1];                           \
 419     f21 = from2_tmp->bits[1];                           \
 420     t1 = f11 OP f21;                                    \
 421     changed |= (t1 != to_tmp->bits[1]);                 \
 422     to_tmp->bits[0] = t0;                               \
 423     to_tmp->bits[1] = t1;                               \
 424   } while (0)
 425 #else
 426 #define DOIT(OP)                                        \
 427   do {                                                  \
 428     unsigned HOST_WIDE_INT t, f1, f2;                   \
 429     int i;                                              \
 430     for (i = 0; i < BITMAP_ELEMENT_WORDS; ++i)          \
 431       {                                                 \
 432         f1 = from1_tmp->bits[i];                        \
 433         f2 = from2_tmp->bits[i];                        \
 434         t = f1 OP f2;                                   \
 435         changed |= (t != to_tmp->bits[i]);              \
 436         to_tmp->bits[i] = t;                            \
 437       }                                                 \
 438   } while (0)
 439 #endif
 440
 441   to->first = to->current = 0;
 442
 443   while (from1_ptr != 0 || from2_ptr != 0)
 444     {
 445       /* Figure out whether we need to substitute zero elements for
 446          missing links.  */
 447       if (indx1 == indx2)
 448         {
 449           indx = indx1;
 450           from1_tmp = from1_ptr;
 451           from2_tmp = from2_ptr;
 452           from1_ptr = from1_ptr->next;
 453           indx1 = (from1_ptr) ? from1_ptr->indx : HIGHEST_INDEX;
 454           from2_ptr = from2_ptr->next;
 455           indx2 = (from2_ptr) ? from2_ptr->indx : HIGHEST_INDEX;
 456         }
 457       else if (indx1 < indx2)
 458         {
 459           indx = indx1;
 460           from1_tmp = from1_ptr;
 461           from2_tmp = &bitmap_zero;
 462           from1_ptr = from1_ptr->next;
 463           indx1 = (from1_ptr) ? from1_ptr->indx : HIGHEST_INDEX;
 464         }
 465       else
 466         {
 467           indx = indx2;
 468           from1_tmp = &bitmap_zero;
 469           from2_tmp = from2_ptr;
 470           from2_ptr = from2_ptr->next;
 471           indx2 = (from2_ptr) ? from2_ptr->indx : HIGHEST_INDEX;
 472         }
 473
 474       /* Find the appropriate element from TO.  Begin by discarding
 475          elements that we've skipped. */
 476       while (to_ptr && to_ptr->indx < indx)
 477         {
 478           changed = 1;
 479           to_tmp = to_ptr;
 480           to_ptr = to_ptr->next;
 481           to_tmp->next = bitmap_free;
 482           bitmap_free = to_tmp;
 483         }
 484       if (to_ptr && to_ptr->indx == indx)
 485         {
 486           to_tmp = to_ptr;
 487           to_ptr = to_ptr->next;
 488         }
 489       else
 490         to_tmp = bitmap_element_allocate ();
 491
 492       /* Do the operation, and if any bits are set, link it into the
 493          linked list.  */
 494       switch (operation)
 495         {
 496         default:
 497           abort ();
 498
 499         case BITMAP_AND:
 500           DOIT (&);
 501           break;
 502
 503         case BITMAP_AND_COMPL:
 504           DOIT (&~);
 505           break;
 506
 507         case BITMAP_IOR:
 508           DOIT (|);
 509           break;
 510
 511         case BITMAP_XOR:
 512           DOIT (^);
 513           break;
 514         }
 515
 516       if (! bitmap_element_zerop (to_tmp))
 517         {
 518           to_tmp->indx = indx;
 519           bitmap_element_link (to, to_tmp);
 520         }
 521       else
 522         {
 523           to_tmp->next = bitmap_free;
 524           bitmap_free = to_tmp;
 525         }
 526     }
 527
 528   /* If we have elements of TO left over, free the lot.  */
 529   if (to_ptr)
 530     {
 531       changed = 1;
 532       for (to_tmp = to_ptr; to_tmp->next ; to_tmp = to_tmp->next)
 533         continue;
 534       to_tmp->next = bitmap_free;
 535       bitmap_free = to_ptr;
 536     }
 537
 538 #undef DOIT
 539
 540   return changed;
 541 }
 542
 543 /* Return true if two bitmaps are identical.  */
 544
 545 int
 546 bitmap_equal_p (a, b)
 547      bitmap a;
 548      bitmap b;
 549 {
 550   bitmap_head c;
 551   int ret;
 552
 553   c.first = c.current = 0;
 554   ret = ! bitmap_operation (&c, a, b, BITMAP_XOR);
 555   bitmap_clear (&c);
 556
 557   return ret;
 558 }
 559 \f
 560 /* Or into bitmap TO bitmap FROM1 and'ed with the complement of
 561    bitmap FROM2. */
 562
 563 void
 564 bitmap_ior_and_compl (to, from1, from2)
 565      bitmap to;
 566      bitmap from1;
 567      bitmap from2;
 568 {
 569   bitmap_head tmp;
 570
 571   tmp.first = tmp.current = 0;
 572
 573   bitmap_operation (&tmp, from1, from2, BITMAP_AND_COMPL);
 574   bitmap_operation (to, to, &tmp, BITMAP_IOR);
 575   bitmap_clear (&tmp);
 576 }
 577 \f
 578 /* Initialize a bitmap header.  */
 579
 580 bitmap
 581 bitmap_initialize (head)
 582      bitmap head;
 583 {
 584   head->first = head->current = 0;
 585
 586   return head;
 587 }
 588 \f
 589 /* Debugging function to print out the contents of a bitmap.  */
 590
 591 void
 592 debug_bitmap_file (file, head)
 593      FILE *file;
 594      bitmap head;
 595 {
 596   bitmap_element *ptr;
 597
 598   fprintf (file, "\nfirst = ");
 599   fprintf (file, HOST_PTR_PRINTF, (PTR) head->first);
 600   fprintf (file, " current = ");
 601   fprintf (file, HOST_PTR_PRINTF, (PTR) head->current);
 602   fprintf (file, " indx = %u\n", head->indx);
 603
 604   for (ptr = head->first; ptr; ptr = ptr->next)
 605     {
 606       int i, j, col = 26;
 607
 608       fprintf (file, "\t");
 609       fprintf (file, HOST_PTR_PRINTF, (PTR) ptr);
 610       fprintf (file, " next = ");
 611       fprintf (file, HOST_PTR_PRINTF, (PTR) ptr->next);
 612       fprintf (file, " prev = ");
 613       fprintf (file, HOST_PTR_PRINTF, (PTR) ptr->prev);
 614       fprintf (file, " indx = %u\n\t\tbits = {", ptr->indx);
 615
 616       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
 617         for (j = 0; j < HOST_BITS_PER_WIDE_INT; j++)
 618           if ((ptr->bits[i] >> j) & 1)
 619             {
 620               if (col > 70)
 621                 {
 622                   fprintf (file, "\n\t\t\t");
 623                   col = 24;
 624                 }
 625
 626               fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
 627                                      + i * HOST_BITS_PER_WIDE_INT + j));
 628               col += 4;
 629             }
 630
 631       fprintf (file, " }\n");
 632     }
 633 }
 634 \f
 635 /* Function to be called from the debugger to print the contents
 636    of a bitmap.  */
 637
 638 void
 639 debug_bitmap (head)
 640      bitmap head;
 641 {
 642   debug_bitmap_file (stdout, head);
 643 }
 644 \f
 645 /* Function to print out the contents of a bitmap.  Unlike debug_bitmap_file,
 646    it does not print anything but the bits.  */
 647
 648 void
 649 bitmap_print (file, head, prefix, suffix)
 650      FILE *file;
 651      bitmap head;
 652      const char *prefix;
 653      const char *suffix;
 654 {
 655   const char *comma = "";
 656   int i;
 657
 658   fputs (prefix, file);
 659   EXECUTE_IF_SET_IN_BITMAP (head, 0, i,
 660                             {
 661                               fprintf (file, "%s%d", comma, i);
 662                               comma = ", ";
 663                             });
 664   fputs (suffix, file);
 665 }
 666 \f
 667 /* Release any memory allocated by bitmaps.  */
 668
 669 void
 670 bitmap_release_memory ()
 671 {
 672   bitmap_free = 0;
 673   if (bitmap_obstack_init)
 674     {
 675       bitmap_obstack_init = FALSE;
 676       obstack_free (&bitmap_obstack, NULL_PTR);
 677     }
 678 }