gcc/bitmap.h

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