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