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