gcc/bitmap.c

   1 /* Functions to support general ended bitmaps.
   2    Copyright (C) 1997 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 <stdio.h>
  22 #include "config.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((bitmap));
  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 (head)
  84      bitmap head;
  85 {
  86   bitmap_element *element;
  87   int i;
  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 *(*) ()) OBSTACK_CHUNK_ALLOC,
 122                                       (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 void INLINE
 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   int i;
 242
 243   bitmap_clear (to);
 244
 245   /* Copy elements in forward direction one at a time */
 246   for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
 247     {
 248       bitmap_element *to_elt = bitmap_element_allocate (to);
 249
 250       to_elt->indx = from_ptr->indx;
 251
 252 #if BITMAP_ELEMENT_WORDS == 2
 253       to_elt->bits[0] = from_ptr->bits[0];
 254       to_elt->bits[1] = from_ptr->bits[1];
 255 #else
 256       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
 257         to_elt->bits[i] = from_ptr->bits[i];
 258 #endif
 259
 260       /* Here we have a special case of bitmap_element_link, for the case
 261          where we know the links are being entered in sequence.  */
 262       if (to_ptr == 0)
 263         {
 264           to->first = to->current = to_elt;
 265           to->indx = from_ptr->indx;
 266           to_elt->next = to_elt->prev = 0;
 267         }
 268       else
 269         {
 270           to_elt->prev = to_ptr;
 271           to_elt->next = 0;
 272           to_ptr->next = to_elt;
 273         }
 274
 275       to_ptr = to_elt;
 276     }
 277 }
 278 \f
 279 /* Find a bitmap element that would hold a bitmap's bit.
 280    Update the `current' field even if we can't find an element that
 281    would hold the bitmap's bit to make eventual allocation
 282    faster.  */
 283
 284 static INLINE bitmap_element *
 285 bitmap_find_bit (head, bit)
 286      bitmap head;
 287      unsigned int bit;
 288 {
 289   bitmap_element *element;
 290   unsigned HOST_WIDE_INT indx = bit / BITMAP_ELEMENT_ALL_BITS;
 291
 292   if (head->current == 0)
 293     return 0;
 294
 295   if (head->indx > indx)
 296     for (element = head->current;
 297          element->prev != 0 && element->indx > indx;
 298          element = element->prev)
 299       ;
 300
 301   else
 302     for (element = head->current;
 303          element->next != 0 && element->indx < indx;
 304          element = element->next)
 305       ;
 306
 307   /* `element' is the nearest to the one we want.  If it's not the one we
 308      want, the one we want doesn't exist.  */
 309   head->current = element;
 310   head->indx = element->indx;
 311   if (element != 0 && element->indx != indx)
 312     element = 0;
 313
 314   return element;
 315 }
 316 \f
 317 /* Clear a single bit in a bitmap.  */
 318
 319 void
 320 bitmap_clear_bit (head, bit)
 321      bitmap head;
 322      int bit;
 323 {
 324   bitmap_element *ptr = bitmap_find_bit (head, bit);
 325
 326   if (ptr != 0)
 327     {
 328       unsigned bit_num  = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
 329       unsigned word_num = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT)
 330                            % BITMAP_ELEMENT_WORDS);
 331       ptr->bits[word_num] &= ~ (((unsigned HOST_WIDE_INT) 1) << bit_num);
 332
 333       /* If we cleared the entire word, free up the element */
 334       if (bitmap_element_zerop (ptr))
 335         bitmap_element_free (head, ptr);
 336     }
 337 }
 338
 339 \f
 340 /* Set a single bit in a bitmap.  */
 341
 342 void
 343 bitmap_set_bit (head, bit)
 344      bitmap head;
 345      int bit;
 346 {
 347   bitmap_element *ptr = bitmap_find_bit (head, bit);
 348   unsigned word_num
 349     = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) % BITMAP_ELEMENT_WORDS);
 350   unsigned bit_num  = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
 351   unsigned HOST_WIDE_INT bit_val = ((unsigned HOST_WIDE_INT) 1) << bit_num;
 352
 353   if (ptr == 0)
 354     {
 355       ptr = bitmap_element_allocate (head);
 356       ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
 357       ptr->bits[word_num] = bit_val;
 358       bitmap_element_link (head, ptr);
 359     }
 360   else
 361     ptr->bits[word_num] |= bit_val;
 362 }
 363 \f
 364 /* Return whether a bit is set within a bitmap.  */
 365
 366 int
 367 bitmap_bit_p (head, bit)
 368      bitmap head;
 369      int bit;
 370 {
 371   bitmap_element *ptr;
 372   unsigned bit_num;
 373   unsigned word_num;
 374
 375   ptr = bitmap_find_bit (head, bit);
 376   if (ptr == 0)
 377     return 0;
 378
 379   bit_num = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
 380   word_num
 381     = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) % BITMAP_ELEMENT_WORDS);
 382
 383   return
 384     (ptr->bits[word_num] & (((unsigned HOST_WIDE_INT) 1) << bit_num)) != 0;
 385 }
 386 \f
 387 /* Store in bitmap TO the result of combining bitmap FROM1 and
 388    FROM2 using a specific bit manipulation.  */
 389
 390 void
 391 bitmap_operation (to, from1, from2, operation)
 392      bitmap to;
 393      bitmap from1;
 394      bitmap from2;
 395      enum bitmap_bits operation;
 396 {
 397   bitmap_element *delete_list = 0;
 398   bitmap_element *from1_ptr = from1->first;
 399   bitmap_element *from2_ptr = from2->first;
 400   unsigned int indx1
 401     = (from1_ptr) ? from1_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
 402   unsigned int indx2
 403     = (from2_ptr) ? from2_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
 404   bitmap_element *to_ptr = 0;
 405   bitmap_element *from1_tmp;
 406   bitmap_element *from2_tmp;
 407   unsigned int indx;
 408   int i;
 409
 410   /* To simplify things, always create a new list.  If the old list was one
 411      of the inputs, free it later.  Otherwise, free it now.  */
 412   if (to == from1 || to == from2)
 413     {
 414       delete_list = to->first;
 415       to->first = to->current = 0;
 416     }
 417   else
 418     bitmap_clear (to);
 419
 420   while (from1_ptr != 0 || from2_ptr != 0)
 421     {
 422       /* Figure out whether we need to substitute zero elements for
 423          missing links.  */
 424       if (indx1 == indx2)
 425         {
 426           indx = indx1;
 427           from1_tmp = from1_ptr;
 428           from2_tmp = from2_ptr;
 429           from1_ptr = from1_ptr->next;
 430           indx1 = (from1_ptr) ? from1_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
 431           from2_ptr = from2_ptr->next;
 432           indx2 = (from2_ptr) ? from2_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
 433         }
 434       else if (indx1 < indx2)
 435         {
 436           indx = indx1;
 437           from1_tmp = from1_ptr;
 438           from2_tmp = &bitmap_zero;
 439           from1_ptr = from1_ptr->next;
 440           indx1 = (from1_ptr) ? from1_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
 441         }
 442       else
 443         {
 444           indx = indx2;
 445           from1_tmp = &bitmap_zero;
 446           from2_tmp = from2_ptr;
 447           from2_ptr = from2_ptr->next;
 448           indx2 = (from2_ptr) ? from2_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
 449         }
 450
 451       if (to_ptr == 0)
 452         to_ptr = bitmap_element_allocate (to);
 453
 454       /* Do the operation, and if any bits are set, link it into the
 455          linked list.  */
 456       switch (operation)
 457         {
 458         default:
 459           abort ();
 460
 461         case BITMAP_AND:
 462 #if BITMAP_ELEMENT_WORDS == 2
 463           to_ptr->bits[0] = from1_tmp->bits[0] & from2_tmp->bits[0];
 464           to_ptr->bits[1] = from1_tmp->bits[1] & from2_tmp->bits[1];
 465 #else
 466           for (i = BITMAP_ELEMENT_WORDS - 1; i >= 0; i--)
 467             to_ptr->bits[i] = from1_tmp->bits[i] & from2_tmp->bits[i];
 468 #endif
 469           break;
 470
 471         case BITMAP_AND_COMPL:
 472 #if BITMAP_ELEMENT_WORDS == 2
 473           to_ptr->bits[0] = from1_tmp->bits[0] & ~ from2_tmp->bits[0];
 474           to_ptr->bits[1] = from1_tmp->bits[1] & ~ from2_tmp->bits[1];
 475 #else
 476           for (i = BITMAP_ELEMENT_WORDS - 1; i >= 0; i--)
 477             to_ptr->bits[i] = from1_tmp->bits[i] & ~ from2_tmp->bits[i];
 478 #endif
 479           break;
 480
 481         case BITMAP_IOR:
 482 #if BITMAP_ELEMENT_WORDS == 2
 483           to_ptr->bits[0] = from1_tmp->bits[0] | from2_tmp->bits[0];
 484           to_ptr->bits[1] = from1_tmp->bits[1] | from2_tmp->bits[1];
 485 #else
 486           for (i = BITMAP_ELEMENT_WORDS - 1; i >= 0; i--)
 487             to_ptr->bits[i] = from1_tmp->bits[i] | from2_tmp->bits[i];
 488 #endif
 489           break;
 490         }
 491
 492       if (! bitmap_element_zerop (to_ptr))
 493         {
 494           to_ptr->indx = indx;
 495           bitmap_element_link (to, to_ptr);
 496           to_ptr = 0;
 497         }
 498     }
 499
 500   /* If we have an unallocated element due to the last element being 0,
 501      release it back to the free pool.  Don't bother calling
 502      bitmap_element_free since it was never linked into a bitmap.  */
 503   if (to_ptr != 0)
 504     {
 505       to_ptr->next = bitmap_free;
 506       bitmap_free = to_ptr;
 507     }
 508
 509   /* If the output bitmap was one of the inputs, free up its
 510      elements now that we're done.  */
 511   for (; delete_list != 0; delete_list = to_ptr)
 512     {
 513       to_ptr = delete_list->next;
 514       delete_list->next = bitmap_free;
 515       bitmap_free = delete_list;
 516     }
 517 }
 518 \f
 519 /* Or into bitmap TO bitmap FROM1 and'ed with the complement of
 520    bitmap FROM2. */
 521
 522 void
 523 bitmap_ior_and_compl (to, from1, from2)
 524      bitmap to;
 525      bitmap from1;
 526      bitmap from2;
 527 {
 528   bitmap_head tmp;
 529
 530   tmp.first = tmp.current = 0;
 531
 532   bitmap_operation (&tmp, from1, from2, BITMAP_AND_COMPL);
 533   bitmap_operation (to, to, &tmp, BITMAP_IOR);
 534   bitmap_clear (&tmp);
 535 }
 536 \f
 537 /* Initialize a bitmap header.  */
 538
 539 bitmap
 540 bitmap_initialize (head)
 541      bitmap head;
 542 {
 543   head->first = head->current = 0;
 544
 545   return head;
 546 }
 547 \f
 548 /* Debugging function to print out the contents of a bitmap.  */
 549
 550 void
 551 bitmap_debug_file (file, head)
 552      FILE *file;
 553      bitmap head;
 554 {
 555   bitmap_element *ptr;
 556
 557   fprintf (file, "\nfirst = ");
 558   fprintf (file, HOST_PTR_PRINTF, (HOST_WIDE_INT) head->first);
 559   fprintf (file, " current = ");
 560   fprintf (file, HOST_PTR_PRINTF, (HOST_WIDE_INT) head->current);
 561   fprintf (file, " indx = %u\n", head->indx);
 562
 563   for (ptr = head->first; ptr; ptr = ptr->next)
 564     {
 565       int i, j, col = 26;
 566
 567       fprintf (file, "\t");
 568       fprintf (file, HOST_PTR_PRINTF, (HOST_WIDE_INT) ptr);
 569       fprintf (file, " next = ");
 570       fprintf (file, HOST_PTR_PRINTF, (HOST_WIDE_INT) ptr->next);
 571       fprintf (file, " prev = ");
 572       fprintf (file, HOST_PTR_PRINTF, (HOST_WIDE_INT) ptr->prev);
 573       fprintf (file, " indx = %u\n\t\tbits = {", ptr->indx);
 574
 575       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
 576         for (j = 0; j < HOST_BITS_PER_WIDE_INT; j++)
 577           if ((ptr->bits[i] & (((unsigned HOST_WIDE_INT) 1) << j)) != 0)
 578             {
 579               if (col > 70)
 580                 {
 581                   fprintf (file, "\n\t\t\t");
 582                   col = 24;
 583                 }
 584
 585               fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
 586                                      + i * HOST_BITS_PER_WIDE_INT + j));
 587               col += 4;
 588             }
 589
 590       fprintf (file, " }\n");
 591     }
 592 }
 593 \f
 594 /* Function to be called from the debugger to print the contents
 595    of a bitmap.  */
 596
 597 void
 598 debug_bitmap (head)
 599      bitmap head;
 600 {
 601   bitmap_debug_file (stdout, head);
 602 }
 603 \f
 604 /* Function to print out the contents of a bitmap.  Unlike bitmap_debug_file,
 605    it does not print anything but the bits.  */
 606
 607 void
 608 bitmap_print (file, head, prefix, suffix)
 609      FILE *file;
 610      bitmap head;
 611      char *prefix;
 612      char *suffix;
 613 {
 614   char *comma = "";
 615   int i;
 616
 617   fputs (prefix, file);
 618   EXECUTE_IF_SET_IN_BITMAP (head, 0, i,
 619                             {
 620                               fprintf (file, "%s%d", comma, i);
 621                               comma = ", ";
 622                             });
 623   fputs (suffix, file);
 624 }
 625 \f
 626 /* Release any memory allocated by bitmaps.  */
 627
 628 void
 629 bitmap_release_memory ()
 630 {
 631   bitmap_free = 0;
 632   if (bitmap_obstack_init)
 633     {
 634       bitmap_obstack_init = FALSE;
 635       obstack_free (&bitmap_obstack, NULL_PTR);
 636     }
 637 }