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