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