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