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