gcc/bitmap.h

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