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