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