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