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
  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 /* Allocate a bitmap from a bit obstack.  */
 168 #define BITMAP_ALLOC(OBSTACK) bitmap_obstack_alloc (OBSTACK)
 169
 170 /* Allocate a gc'd bitmap.  */
 171 #define BITMAP_GGC_ALLOC() bitmap_gc_alloc ()
 172
 173 /* Do any cleanup needed on a bitmap when it is no longer used.  */
 174 #define BITMAP_FREE(BITMAP)                     \
 175         ((void)(bitmap_obstack_free (BITMAP), (BITMAP) = NULL))
 176
 177 /* Iterator for bitmaps.  */
 178
 179 typedef struct
 180 {
 181   /* Pointer to the current bitmap element.  */
 182   bitmap_element *elt1;
 183
 184   /* Pointer to 2nd bitmap element when two are involved.  */
 185   bitmap_element *elt2;
 186
 187   /* Word within the current element.  */
 188   unsigned word_no;
 189
 190   /* Contents of the actually processed word.  When finding next bit
 191      it is shifted right, so that the actual bit is always the least
 192      significant bit of ACTUAL.  */
 193   BITMAP_WORD bits;
 194 } bitmap_iterator;
 195
 196 /* Initialize a single bitmap iterator.  START_BIT is the first bit to
 197    iterate from.  */
 198
 199 static inline void
 200 bmp_iter_set_init (bitmap_iterator *bi, bitmap map,
 201                    unsigned start_bit, unsigned *bit_no)
 202 {
 203   bi->elt1 = map->first;
 204   bi->elt2 = NULL;
 205
 206   /* Advance elt1 until it is not before the block containing start_bit.  */
 207   while (1)
 208     {
 209       if (!bi->elt1)
 210         {
 211           bi->elt1 = &bitmap_zero_bits;
 212           break;
 213         }
 214
 215       if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
 216         break;
 217       bi->elt1 = bi->elt1->next;
 218     }
 219
 220   /* We might have gone past the start bit, so reinitialize it.  */
 221   if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
 222     start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 223
 224   /* Initialize for what is now start_bit.  */
 225   bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 226   bi->bits = bi->elt1->bits[bi->word_no];
 227   bi->bits >>= start_bit % BITMAP_WORD_BITS;
 228
 229   /* If this word is zero, we must make sure we're not pointing at the
 230      first bit, otherwise our incrementing to the next word boundary
 231      will fail.  It won't matter if this increment moves us into the
 232      next word.  */
 233   start_bit += !bi->bits;
 234
 235   *bit_no = start_bit;
 236 }
 237
 238 /* Initialize an iterator to iterate over the intersection of two
 239    bitmaps.  START_BIT is the bit to commence from.  */
 240
 241 static inline void
 242 bmp_iter_and_init (bitmap_iterator *bi, bitmap map1, bitmap map2,
 243                    unsigned start_bit, unsigned *bit_no)
 244 {
 245   bi->elt1 = map1->first;
 246   bi->elt2 = map2->first;
 247
 248   /* Advance elt1 until it is not before the block containing
 249      start_bit.  */
 250   while (1)
 251     {
 252       if (!bi->elt1)
 253         {
 254           bi->elt2 = NULL;
 255           break;
 256         }
 257
 258       if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
 259         break;
 260       bi->elt1 = bi->elt1->next;
 261     }
 262
 263   /* Advance elt2 until it is not before elt1.  */
 264   while (1)
 265     {
 266       if (!bi->elt2)
 267         {
 268           bi->elt1 = bi->elt2 = &bitmap_zero_bits;
 269           break;
 270         }
 271
 272       if (bi->elt2->indx >= bi->elt1->indx)
 273         break;
 274       bi->elt2 = bi->elt2->next;
 275     }
 276
 277   /* If we're at the same index, then we have some intersecting bits.  */
 278   if (bi->elt1->indx == bi->elt2->indx)
 279     {
 280       /* We might have advanced beyond the start_bit, so reinitialize
 281          for that.  */
 282       if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
 283         start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 284
 285       bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 286       bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
 287       bi->bits >>= start_bit % BITMAP_WORD_BITS;
 288     }
 289   else
 290     {
 291       /* Otherwise we must immediately advance elt1, so initialize for
 292          that.  */
 293       bi->word_no = BITMAP_ELEMENT_WORDS - 1;
 294       bi->bits = 0;
 295     }
 296
 297   /* If this word is zero, we must make sure we're not pointing at the
 298      first bit, otherwise our incrementing to the next word boundary
 299      will fail.  It won't matter if this increment moves us into the
 300      next word.  */
 301   start_bit += !bi->bits;
 302
 303   *bit_no = start_bit;
 304 }
 305
 306 /* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2.
 307    */
 308
 309 static inline void
 310 bmp_iter_and_compl_init (bitmap_iterator *bi, bitmap map1, bitmap map2,
 311                          unsigned start_bit, unsigned *bit_no)
 312 {
 313   bi->elt1 = map1->first;
 314   bi->elt2 = map2->first;
 315
 316   /* Advance elt1 until it is not before the block containing start_bit.  */
 317   while (1)
 318     {
 319       if (!bi->elt1)
 320         {
 321           bi->elt1 = &bitmap_zero_bits;
 322           break;
 323         }
 324
 325       if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
 326         break;
 327       bi->elt1 = bi->elt1->next;
 328     }
 329
 330   /* Advance elt2 until it is not before elt1.  */
 331   while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
 332     bi->elt2 = bi->elt2->next;
 333
 334   /* We might have advanced beyond the start_bit, so reinitialize for
 335      that.  */
 336   if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
 337     start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 338
 339   bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 340   bi->bits = bi->elt1->bits[bi->word_no];
 341   if (bi->elt2 && bi->elt1->indx == bi->elt2->indx)
 342     bi->bits &= ~bi->elt2->bits[bi->word_no];
 343   bi->bits >>= start_bit % BITMAP_WORD_BITS;
 344
 345   /* If this word is zero, we must make sure we're not pointing at the
 346      first bit, otherwise our incrementing to the next word boundary
 347      will fail.  It won't matter if this increment moves us into the
 348      next word.  */
 349   start_bit += !bi->bits;
 350
 351   *bit_no = start_bit;
 352 }
 353
 354 /* Advance to the next bit in BI.  We don't advance to the next
 355    nonzero bit yet.  */
 356
 357 static inline void
 358 bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no)
 359 {
 360   bi->bits >>= 1;
 361   *bit_no += 1;
 362 }
 363
 364 /* Advance to the next nonzero bit of a single bitmap, we will have
 365    already advanced past the just iterated bit.  Return true if there
 366    is a bit to iterate.  */
 367
 368 static inline bool
 369 bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no)
 370 {
 371   /* If our current word is nonzero, it contains the bit we want.  */
 372   if (bi->bits)
 373     {
 374     next_bit:
 375       while (!(bi->bits & 1))
 376         {
 377           bi->bits >>= 1;
 378           *bit_no += 1;
 379         }
 380       return true;
 381     }
 382
 383   /* Round up to the word boundary.  We might have just iterated past
 384      the end of the last word, hence the -1.  It is not possible for
 385      bit_no to point at the beginning of the now last word.  */
 386   *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
 387              / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
 388   bi->word_no++;
 389
 390   while (1)
 391     {
 392       /* Find the next nonzero word in this elt.  */
 393       while (bi->word_no != BITMAP_ELEMENT_WORDS)
 394         {
 395           bi->bits = bi->elt1->bits[bi->word_no];
 396           if (bi->bits)
 397             goto next_bit;
 398           *bit_no += BITMAP_WORD_BITS;
 399           bi->word_no++;
 400         }
 401
 402       /* Advance to the next element.  */
 403       bi->elt1 = bi->elt1->next;
 404       if (!bi->elt1)
 405         return false;
 406       *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 407       bi->word_no = 0;
 408     }
 409 }
 410
 411 /* Advance to the next nonzero bit of an intersecting pair of
 412    bitmaps.  We will have already advanced past the just iterated bit.
 413    Return true if there is a bit to iterate.  */
 414
 415 static inline bool
 416 bmp_iter_and (bitmap_iterator *bi, unsigned *bit_no)
 417 {
 418   /* If our current word is nonzero, it contains the bit we want.  */
 419   if (bi->bits)
 420     {
 421     next_bit:
 422       while (!(bi->bits & 1))
 423         {
 424           bi->bits >>= 1;
 425           *bit_no += 1;
 426         }
 427       return true;
 428     }
 429
 430   /* Round up to the word boundary.  We might have just iterated past
 431      the end of the last word, hence the -1.  It is not possible for
 432      bit_no to point at the beginning of the now last word.  */
 433   *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
 434              / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
 435   bi->word_no++;
 436
 437   while (1)
 438     {
 439       /* Find the next nonzero word in this elt.  */
 440       while (bi->word_no != BITMAP_ELEMENT_WORDS)
 441         {
 442           bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
 443           if (bi->bits)
 444             goto next_bit;
 445           *bit_no += BITMAP_WORD_BITS;
 446           bi->word_no++;
 447         }
 448
 449       /* Advance to the next identical element.  */
 450       do
 451         {
 452           /* Advance elt1 while it is less than elt2.  We always want
 453              to advance one elt.  */
 454           do
 455             {
 456               bi->elt1 = bi->elt1->next;
 457               if (!bi->elt1)
 458                 return false;
 459             }
 460           while (bi->elt1->indx < bi->elt2->indx);
 461
 462           /* Advance elt2 to be no less than elt1.  This might not
 463              advance.  */
 464           while (bi->elt2->indx < bi->elt1->indx)
 465             {
 466               bi->elt2 = bi->elt2->next;
 467               if (!bi->elt2)
 468                 return false;
 469             }
 470         }
 471       while (bi->elt1->indx != bi->elt2->indx);
 472
 473       *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 474       bi->word_no = 0;
 475     }
 476 }
 477
 478 /* Advance to the next nonzero bit in the intersection of
 479    complemented bitmaps.  We will have already advanced past the just
 480    iterated bit.  */
 481
 482 static inline bool
 483 bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no)
 484 {
 485   /* If our current word is nonzero, it contains the bit we want.  */
 486   if (bi->bits)
 487     {
 488     next_bit:
 489       while (!(bi->bits & 1))
 490         {
 491           bi->bits >>= 1;
 492           *bit_no += 1;
 493         }
 494       return true;
 495     }
 496
 497   /* Round up to the word boundary.  We might have just iterated past
 498      the end of the last word, hence the -1.  It is not possible for
 499      bit_no to point at the beginning of the now last word.  */
 500   *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
 501              / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
 502   bi->word_no++;
 503
 504   while (1)
 505     {
 506       /* Find the next nonzero word in this elt.  */
 507       while (bi->word_no != BITMAP_ELEMENT_WORDS)
 508         {
 509           bi->bits = bi->elt1->bits[bi->word_no];
 510           if (bi->elt2 && bi->elt2->indx == bi->elt1->indx)
 511             bi->bits &= ~bi->elt2->bits[bi->word_no];
 512           if (bi->bits)
 513             goto next_bit;
 514           *bit_no += BITMAP_WORD_BITS;
 515           bi->word_no++;
 516         }
 517
 518       /* Advance to the next element of elt1.  */
 519       bi->elt1 = bi->elt1->next;
 520       if (!bi->elt1)
 521         return false;
 522
 523       /* Advance elt2 until it is no less than elt1.  */
 524       while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
 525         bi->elt2 = bi->elt2->next;
 526
 527       *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 528       bi->word_no = 0;
 529     }
 530 }
 531
 532 /* Loop over all bits set in BITMAP, starting with MIN and setting
 533    BITNUM to the bit number.  ITER is a bitmap iterator.  BITNUM
 534    should be treated as a read-only variable as it contains loop
 535    state.  */
 536
 537 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER)             \
 538   for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM));         \
 539        bmp_iter_set (&(ITER), &(BITNUM));                               \
 540        bmp_iter_next (&(ITER), &(BITNUM)))
 541
 542 /* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN
 543    and setting BITNUM to the bit number.  ITER is a bitmap iterator.
 544    BITNUM should be treated as a read-only variable as it contains
 545    loop state.  */
 546
 547 #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER)   \
 548   for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN),         \
 549                           &(BITNUM));                                   \
 550        bmp_iter_and (&(ITER), &(BITNUM));                               \
 551        bmp_iter_next (&(ITER), &(BITNUM)))
 552
 553 /* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN
 554    and setting BITNUM to the bit number.  ITER is a bitmap iterator.
 555    BITNUM should be treated as a read-only variable as it contains
 556    loop state.  */
 557
 558 #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
 559   for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN),   \
 560                                 &(BITNUM));                             \
 561        bmp_iter_and_compl (&(ITER), &(BITNUM));                         \
 562        bmp_iter_next (&(ITER), &(BITNUM)))
 563
 564 #endif /* GCC_BITMAP_H */