gcc/bitmap.h

   1 /* Functions to support general ended bitmaps.
   2    Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  21
  22 #ifndef GCC_BITMAP_H
  23 #define GCC_BITMAP_H
  24 #include "hashtab.h"
  25
  26 /* Fundamental storage type for bitmap.  */
  27
  28 typedef unsigned long BITMAP_WORD;
  29 /* BITMAP_WORD_BITS needs to be unsigned, but cannot contain casts as
  30    it is used in preprocessor directives -- hence the 1u.  */
  31 #define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u)
  32
  33 /* Number of words to use for each element in the linked list.  */
  34
  35 #ifndef BITMAP_ELEMENT_WORDS
  36 #define BITMAP_ELEMENT_WORDS ((128 + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
  37 #endif
  38
  39 /* Number of bits in each actual element of a bitmap.  */
  40
  41 #define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)
  42
  43 /* Obstack for allocating bitmaps and elements from.  */
  44 typedef struct bitmap_obstack GTY (())
  45 {
  46   struct bitmap_element_def *elements;
  47   struct bitmap_head_def *heads;
  48   struct obstack GTY ((skip)) obstack;
  49 } bitmap_obstack;
  50
  51 /* Bitmap set element.  We use a linked list to hold only the bits that
  52    are set.  This allows for use to grow the bitset dynamically without
  53    having to realloc and copy a giant bit array.
  54
  55    The free list is implemented as a list of lists.  There is one
  56    outer list connected together by prev fields.  Each element of that
  57    outer is an inner list (that may consist only of the outer list
  58    element) that are connected by the next fields.  The prev pointer
  59    is undefined for interior elements.  This allows
  60    bitmap_elt_clear_from to be implemented in unit time rather than
  61    linear in the number of elements to be freed.  */
  62
  63 typedef struct bitmap_element_def GTY(())
  64 {
  65   struct bitmap_element_def *next;              /* Next element.  */
  66   struct bitmap_element_def *prev;              /* Previous element.  */
  67   unsigned int indx;                    /* regno/BITMAP_ELEMENT_ALL_BITS.  */
  68   BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set.  */
  69 } bitmap_element;
  70
  71 /* Head of bitmap linked list.  */
  72 typedef struct bitmap_head_def GTY(()) {
  73   bitmap_element *first;        /* First element in linked list.  */
  74   bitmap_element *current;      /* Last element looked at.  */
  75   unsigned int indx;            /* Index of last element looked at.  */
  76   bitmap_obstack *obstack;      /* Obstack to allocate elements from.
  77                                    If NULL, then use ggc_alloc.  */
  78 } bitmap_head;
  79
  80
  81 /* Global data */
  82 extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */
  83 extern bitmap_obstack bitmap_default_obstack;   /* Default bitmap obstack */
  84
  85 /* Clear a bitmap by freeing up the linked list.  */
  86 extern void bitmap_clear (bitmap);
  87
  88 /* Copy a bitmap to another bitmap.  */
  89 extern void bitmap_copy (bitmap, bitmap);
  90
  91 /* True if two bitmaps are identical.  */
  92 extern bool bitmap_equal_p (bitmap, bitmap);
  93
  94 /* True if the bitmaps intersect (their AND is non-empty).  */
  95 extern bool bitmap_intersect_p (bitmap, bitmap);
  96
  97 /* True if the complement of the second intersects the first (their
  98    AND_COMPL is non-empty).  */
  99 extern bool bitmap_intersect_compl_p (bitmap, bitmap);
 100
 101 /* True if MAP is an empty bitmap.  */
 102 #define bitmap_empty_p(MAP) (!(MAP)->first)
 103
 104 /* Count the number of bits set in the bitmap.  */
 105 extern unsigned long bitmap_count_bits (bitmap);
 106
 107 /* Boolean operations on bitmaps.  The _into variants are two operand
 108    versions that modify the first source operand.  The other variants
 109    are three operand versions that to not destroy the source bitmaps.
 110    The operations supported are &, & ~, |, ^.  */
 111 extern void bitmap_and (bitmap, bitmap, bitmap);
 112 extern void bitmap_and_into (bitmap, bitmap);
 113 extern void bitmap_and_compl (bitmap, bitmap, bitmap);
 114 extern bool bitmap_and_compl_into (bitmap, bitmap);
 115 #define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A)
 116 extern void bitmap_compl_and_into (bitmap, bitmap);
 117 extern void bitmap_clear_range (bitmap, unsigned int, unsigned int);
 118 extern bool bitmap_ior (bitmap, bitmap, bitmap);
 119 extern bool bitmap_ior_into (bitmap, bitmap);
 120 extern void bitmap_xor (bitmap, bitmap, bitmap);
 121 extern void bitmap_xor_into (bitmap, bitmap);
 122
 123 /* DST = A | (B & ~C).  Return true if DST changes.  */
 124 extern bool bitmap_ior_and_compl (bitmap DST, bitmap A, bitmap B, bitmap C);
 125 /* A |= (B & ~C).  Return true if A changes.  */
 126 extern bool bitmap_ior_and_compl_into (bitmap DST, bitmap B, bitmap C);
 127
 128 /* Clear a single register in a register set.  */
 129 extern void bitmap_clear_bit (bitmap, int);
 130
 131 /* Set a single register in a register set.  */
 132 extern void bitmap_set_bit (bitmap, int);
 133
 134 /* Return true if a register is set in a register set.  */
 135 extern int bitmap_bit_p (bitmap, int);
 136
 137 /* Debug functions to print a bitmap linked list.  */
 138 extern void debug_bitmap (bitmap);
 139 extern void debug_bitmap_file (FILE *, bitmap);
 140
 141 /* Print a bitmap.  */
 142 extern void bitmap_print (FILE *, bitmap, const char *, const char *);
 143
 144 /* Initialize and release a bitmap obstack.  */
 145 extern void bitmap_obstack_initialize (bitmap_obstack *);
 146 extern void bitmap_obstack_release (bitmap_obstack *);
 147
 148 /* Initialize a bitmap header.  OBSTACK indicates the bitmap obstack
 149    to allocate from, NULL for GC'd bitmap.  */
 150
 151 static inline void
 152 bitmap_initialize (bitmap head, bitmap_obstack *obstack)
 153 {
 154   head->first = head->current = NULL;
 155   head->obstack = obstack;
 156 }
 157
 158 /* Allocate and free bitmaps from obstack, malloc and gc'd memory.  */
 159 extern bitmap bitmap_obstack_alloc (bitmap_obstack *obstack);
 160 extern bitmap bitmap_gc_alloc (void);
 161 extern void bitmap_obstack_free (bitmap);
 162
 163 /* A few compatibility/functions macros for compatibility with sbitmaps */
 164 #define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n")
 165 #define bitmap_zero(a) bitmap_clear (a)
 166 extern unsigned bitmap_first_set_bit (bitmap);
 167
 168 /* Compute bitmap hash (for purposes of hashing etc.)  */
 169 extern hashval_t bitmap_hash(bitmap);
 170
 171 /* Allocate a bitmap from a bit obstack.  */
 172 #define BITMAP_ALLOC(OBSTACK) bitmap_obstack_alloc (OBSTACK)
 173
 174 /* Allocate a gc'd bitmap.  */
 175 #define BITMAP_GGC_ALLOC() bitmap_gc_alloc ()
 176
 177 /* Do any cleanup needed on a bitmap when it is no longer used.  */
 178 #define BITMAP_FREE(BITMAP)                     \
 179         ((void)(bitmap_obstack_free (BITMAP), (BITMAP) = NULL))
 180
 181 /* Iterator for bitmaps.  */
 182
 183 typedef struct
 184 {
 185   /* Pointer to the current bitmap element.  */
 186   bitmap_element *elt1;
 187
 188   /* Pointer to 2nd bitmap element when two are involved.  */
 189   bitmap_element *elt2;
 190
 191   /* Word within the current element.  */
 192   unsigned word_no;
 193
 194   /* Contents of the actually processed word.  When finding next bit
 195      it is shifted right, so that the actual bit is always the least
 196      significant bit of ACTUAL.  */
 197   BITMAP_WORD bits;
 198 } bitmap_iterator;
 199
 200 /* Initialize a single bitmap iterator.  START_BIT is the first bit to
 201    iterate from.  */
 202
 203 static inline void
 204 bmp_iter_set_init (bitmap_iterator *bi, bitmap map,
 205                    unsigned start_bit, unsigned *bit_no)
 206 {
 207   bi->elt1 = map->first;
 208   bi->elt2 = NULL;
 209
 210   /* Advance elt1 until it is not before the block containing start_bit.  */
 211   while (1)
 212     {
 213       if (!bi->elt1)
 214         {
 215           bi->elt1 = &bitmap_zero_bits;
 216           break;
 217         }
 218
 219       if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
 220         break;
 221       bi->elt1 = bi->elt1->next;
 222     }
 223
 224   /* We might have gone past the start bit, so reinitialize it.  */
 225   if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
 226     start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 227
 228   /* Initialize for what is now start_bit.  */
 229   bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 230   bi->bits = bi->elt1->bits[bi->word_no];
 231   bi->bits >>= start_bit % BITMAP_WORD_BITS;
 232
 233   /* If this word is zero, we must make sure we're not pointing at the
 234      first bit, otherwise our incrementing to the next word boundary
 235      will fail.  It won't matter if this increment moves us into the
 236      next word.  */
 237   start_bit += !bi->bits;
 238
 239   *bit_no = start_bit;
 240 }
 241
 242 /* Initialize an iterator to iterate over the intersection of two
 243    bitmaps.  START_BIT is the bit to commence from.  */
 244
 245 static inline void
 246 bmp_iter_and_init (bitmap_iterator *bi, bitmap map1, bitmap map2,
 247                    unsigned start_bit, unsigned *bit_no)
 248 {
 249   bi->elt1 = map1->first;
 250   bi->elt2 = map2->first;
 251
 252   /* Advance elt1 until it is not before the block containing
 253      start_bit.  */
 254   while (1)
 255     {
 256       if (!bi->elt1)
 257         {
 258           bi->elt2 = NULL;
 259           break;
 260         }
 261
 262       if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
 263         break;
 264       bi->elt1 = bi->elt1->next;
 265     }
 266
 267   /* Advance elt2 until it is not before elt1.  */
 268   while (1)
 269     {
 270       if (!bi->elt2)
 271         {
 272           bi->elt1 = bi->elt2 = &bitmap_zero_bits;
 273           break;
 274         }
 275
 276       if (bi->elt2->indx >= bi->elt1->indx)
 277         break;
 278       bi->elt2 = bi->elt2->next;
 279     }
 280
 281   /* If we're at the same index, then we have some intersecting bits.  */
 282   if (bi->elt1->indx == bi->elt2->indx)
 283     {
 284       /* We might have advanced beyond the start_bit, so reinitialize
 285          for that.  */
 286       if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
 287         start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 288
 289       bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 290       bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
 291       bi->bits >>= start_bit % BITMAP_WORD_BITS;
 292     }
 293   else
 294     {
 295       /* Otherwise we must immediately advance elt1, so initialize for
 296          that.  */
 297       bi->word_no = BITMAP_ELEMENT_WORDS - 1;
 298       bi->bits = 0;
 299     }
 300
 301   /* If this word is zero, we must make sure we're not pointing at the
 302      first bit, otherwise our incrementing to the next word boundary
 303      will fail.  It won't matter if this increment moves us into the
 304      next word.  */
 305   start_bit += !bi->bits;
 306
 307   *bit_no = start_bit;
 308 }
 309
 310 /* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2.
 311    */
 312
 313 static inline void
 314 bmp_iter_and_compl_init (bitmap_iterator *bi, bitmap map1, bitmap map2,
 315                          unsigned start_bit, unsigned *bit_no)
 316 {
 317   bi->elt1 = map1->first;
 318   bi->elt2 = map2->first;
 319
 320   /* Advance elt1 until it is not before the block containing start_bit.  */
 321   while (1)
 322     {
 323       if (!bi->elt1)
 324         {
 325           bi->elt1 = &bitmap_zero_bits;
 326           break;
 327         }
 328
 329       if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
 330         break;
 331       bi->elt1 = bi->elt1->next;
 332     }
 333
 334   /* Advance elt2 until it is not before elt1.  */
 335   while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
 336     bi->elt2 = bi->elt2->next;
 337
 338   /* We might have advanced beyond the start_bit, so reinitialize for
 339      that.  */
 340   if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
 341     start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 342
 343   bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 344   bi->bits = bi->elt1->bits[bi->word_no];
 345   if (bi->elt2 && bi->elt1->indx == bi->elt2->indx)
 346     bi->bits &= ~bi->elt2->bits[bi->word_no];
 347   bi->bits >>= start_bit % BITMAP_WORD_BITS;
 348
 349   /* If this word is zero, we must make sure we're not pointing at the
 350      first bit, otherwise our incrementing to the next word boundary
 351      will fail.  It won't matter if this increment moves us into the
 352      next word.  */
 353   start_bit += !bi->bits;
 354
 355   *bit_no = start_bit;
 356 }
 357
 358 /* Advance to the next bit in BI.  We don't advance to the next
 359    nonzero bit yet.  */
 360
 361 static inline void
 362 bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no)
 363 {
 364   bi->bits >>= 1;
 365   *bit_no += 1;
 366 }
 367
 368 /* Advance to the next nonzero bit of a single bitmap, we will have
 369    already advanced past the just iterated bit.  Return true if there
 370    is a bit to iterate.  */
 371
 372 static inline bool
 373 bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no)
 374 {
 375   /* If our current word is nonzero, it contains the bit we want.  */
 376   if (bi->bits)
 377     {
 378     next_bit:
 379       while (!(bi->bits & 1))
 380         {
 381           bi->bits >>= 1;
 382           *bit_no += 1;
 383         }
 384       return true;
 385     }
 386
 387   /* Round up to the word boundary.  We might have just iterated past
 388      the end of the last word, hence the -1.  It is not possible for
 389      bit_no to point at the beginning of the now last word.  */
 390   *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
 391              / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
 392   bi->word_no++;
 393
 394   while (1)
 395     {
 396       /* Find the next nonzero word in this elt.  */
 397       while (bi->word_no != BITMAP_ELEMENT_WORDS)
 398         {
 399           bi->bits = bi->elt1->bits[bi->word_no];
 400           if (bi->bits)
 401             goto next_bit;
 402           *bit_no += BITMAP_WORD_BITS;
 403           bi->word_no++;
 404         }
 405
 406       /* Advance to the next element.  */
 407       bi->elt1 = bi->elt1->next;
 408       if (!bi->elt1)
 409         return false;
 410       *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 411       bi->word_no = 0;
 412     }
 413 }
 414
 415 /* Advance to the next nonzero bit of an intersecting pair of
 416    bitmaps.  We will have already advanced past the just iterated bit.
 417    Return true if there is a bit to iterate.  */
 418
 419 static inline bool
 420 bmp_iter_and (bitmap_iterator *bi, unsigned *bit_no)
 421 {
 422   /* If our current word is nonzero, it contains the bit we want.  */
 423   if (bi->bits)
 424     {
 425     next_bit:
 426       while (!(bi->bits & 1))
 427         {
 428           bi->bits >>= 1;
 429           *bit_no += 1;
 430         }
 431       return true;
 432     }
 433
 434   /* Round up to the word boundary.  We might have just iterated past
 435      the end of the last word, hence the -1.  It is not possible for
 436      bit_no to point at the beginning of the now last word.  */
 437   *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
 438              / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
 439   bi->word_no++;
 440
 441   while (1)
 442     {
 443       /* Find the next nonzero word in this elt.  */
 444       while (bi->word_no != BITMAP_ELEMENT_WORDS)
 445         {
 446           bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
 447           if (bi->bits)
 448             goto next_bit;
 449           *bit_no += BITMAP_WORD_BITS;
 450           bi->word_no++;
 451         }
 452
 453       /* Advance to the next identical element.  */
 454       do
 455         {
 456           /* Advance elt1 while it is less than elt2.  We always want
 457              to advance one elt.  */
 458           do
 459             {
 460               bi->elt1 = bi->elt1->next;
 461               if (!bi->elt1)
 462                 return false;
 463             }
 464           while (bi->elt1->indx < bi->elt2->indx);
 465
 466           /* Advance elt2 to be no less than elt1.  This might not
 467              advance.  */
 468           while (bi->elt2->indx < bi->elt1->indx)
 469             {
 470               bi->elt2 = bi->elt2->next;
 471               if (!bi->elt2)
 472                 return false;
 473             }
 474         }
 475       while (bi->elt1->indx != bi->elt2->indx);
 476
 477       *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 478       bi->word_no = 0;
 479     }
 480 }
 481
 482 /* Advance to the next nonzero bit in the intersection of
 483    complemented bitmaps.  We will have already advanced past the just
 484    iterated bit.  */
 485
 486 static inline bool
 487 bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no)
 488 {
 489   /* If our current word is nonzero, it contains the bit we want.  */
 490   if (bi->bits)
 491     {
 492     next_bit:
 493       while (!(bi->bits & 1))
 494         {
 495           bi->bits >>= 1;
 496           *bit_no += 1;
 497         }
 498       return true;
 499     }
 500
 501   /* Round up to the word boundary.  We might have just iterated past
 502      the end of the last word, hence the -1.  It is not possible for
 503      bit_no to point at the beginning of the now last word.  */
 504   *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
 505              / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
 506   bi->word_no++;
 507
 508   while (1)
 509     {
 510       /* Find the next nonzero word in this elt.  */
 511       while (bi->word_no != BITMAP_ELEMENT_WORDS)
 512         {
 513           bi->bits = bi->elt1->bits[bi->word_no];
 514           if (bi->elt2 && bi->elt2->indx == bi->elt1->indx)
 515             bi->bits &= ~bi->elt2->bits[bi->word_no];
 516           if (bi->bits)
 517             goto next_bit;
 518           *bit_no += BITMAP_WORD_BITS;
 519           bi->word_no++;
 520         }
 521
 522       /* Advance to the next element of elt1.  */
 523       bi->elt1 = bi->elt1->next;
 524       if (!bi->elt1)
 525         return false;
 526
 527       /* Advance elt2 until it is no less than elt1.  */
 528       while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
 529         bi->elt2 = bi->elt2->next;
 530
 531       *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 532       bi->word_no = 0;
 533     }
 534 }
 535
 536 /* Loop over all bits set in BITMAP, starting with MIN and setting
 537    BITNUM to the bit number.  ITER is a bitmap iterator.  BITNUM
 538    should be treated as a read-only variable as it contains loop
 539    state.  */
 540
 541 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER)             \
 542   for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM));         \
 543        bmp_iter_set (&(ITER), &(BITNUM));                               \
 544        bmp_iter_next (&(ITER), &(BITNUM)))
 545
 546 /* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN
 547    and setting BITNUM to the bit number.  ITER is a bitmap iterator.
 548    BITNUM should be treated as a read-only variable as it contains
 549    loop state.  */
 550
 551 #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER)   \
 552   for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN),         \
 553                           &(BITNUM));                                   \
 554        bmp_iter_and (&(ITER), &(BITNUM));                               \
 555        bmp_iter_next (&(ITER), &(BITNUM)))
 556
 557 /* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN
 558    and setting BITNUM to the bit number.  ITER is a bitmap iterator.
 559    BITNUM should be treated as a read-only variable as it contains
 560    loop state.  */
 561
 562 #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
 563   for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN),   \
 564                                 &(BITNUM));                             \
 565        bmp_iter_and_compl (&(ITER), &(BITNUM));                         \
 566        bmp_iter_next (&(ITER), &(BITNUM)))
 567
 568 #endif /* GCC_BITMAP_H */