gcc/bitmap.h

   1 /* Functions to support general ended bitmaps.
   2    Copyright (C) 1997-2015 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #ifndef GCC_BITMAP_H
  21 #define GCC_BITMAP_H
  22
  23 /* Implementation of sparse integer sets as a linked list.
  24
  25    This sparse set representation is suitable for sparse sets with an
  26    unknown (a priori) universe.  The set is represented as a double-linked
  27    list of container nodes (struct bitmap_element).  Each node consists
  28    of an index for the first member that could be held in the container,
  29    a small array of integers that represent the members in the container,
  30    and pointers to the next and previous element in the linked list.  The
  31    elements in the list are sorted in ascending order, i.e. the head of
  32    the list holds the element with the smallest member of the set.
  33
  34    For a given member I in the set:
  35      - the element for I will have index is I / (bits per element)
  36      - the position for I within element is I % (bits per element)
  37
  38    This representation is very space-efficient for large sparse sets, and
  39    the size of the set can be changed dynamically without much overhead.
  40    An important parameter is the number of bits per element.  In this
  41    implementation, there are 128 bits per element.  This results in a
  42    high storage overhead *per element*, but a small overall overhead if
  43    the set is very sparse.
  44
  45    The downside is that many operations are relatively slow because the
  46    linked list has to be traversed to test membership (i.e. member_p/
  47    add_member/remove_member).  To improve the performance of this set
  48    representation, the last accessed element and its index are cached.
  49    For membership tests on members close to recently accessed members,
  50    the cached last element improves membership test to a constant-time
  51    operation.
  52
  53    The following operations can always be performed in O(1) time:
  54
  55      * clear                    : bitmap_clear
  56      * choose_one               : (not implemented, but could be
  57                                    implemented in constant time)
  58
  59    The following operations can be performed in O(E) time worst-case (with
  60    E the number of elements in the linked list), but in O(1) time with a
  61    suitable access patterns:
  62
  63      * member_p                 : bitmap_bit_p
  64      * add_member               : bitmap_set_bit
  65      * remove_member            : bitmap_clear_bit
  66
  67    The following operations can be performed in O(E) time:
  68
  69      * cardinality              : bitmap_count_bits
  70      * set_size                 : bitmap_last_set_bit (but this could
  71                                   in constant time with a pointer to
  72                                   the last element in the chain)
  73
  74    Additionally, the linked-list sparse set representation supports
  75    enumeration of the members in O(E) time:
  76
  77      * forall                   : EXECUTE_IF_SET_IN_BITMAP
  78      * set_copy                 : bitmap_copy
  79      * set_intersection         : bitmap_intersect_p /
  80                                   bitmap_and / bitmap_and_into /
  81                                   EXECUTE_IF_AND_IN_BITMAP
  82      * set_union                : bitmap_ior / bitmap_ior_into
  83      * set_difference           : bitmap_intersect_compl_p /
  84                                   bitmap_and_comp / bitmap_and_comp_into /
  85                                   EXECUTE_IF_AND_COMPL_IN_BITMAP
  86      * set_disjuction           : bitmap_xor_comp / bitmap_xor_comp_into
  87      * set_compare              : bitmap_equal_p
  88
  89    Some operations on 3 sets that occur frequently in data flow problems
  90    are also implemented:
  91
  92      * A | (B & C)              : bitmap_ior_and_into
  93      * A | (B & ~C)             : bitmap_ior_and_compl /
  94                                   bitmap_ior_and_compl_into
  95
  96    The storage requirements for linked-list sparse sets are O(E), with E->N
  97    in the worst case (a sparse set with large distances between the values
  98    of the set members).
  99
 100    The linked-list set representation works well for problems involving very
 101    sparse sets.  The canonical example in GCC is, of course, the "set of
 102    sets" for some CFG-based data flow problems (liveness analysis, dominance
 103    frontiers, etc.).
 104
 105    This representation also works well for data flow problems where the size
 106    of the set may grow dynamically, but care must be taken that the member_p,
 107    add_member, and remove_member operations occur with a suitable access
 108    pattern.
 109
 110    For random-access sets with a known, relatively small universe size, the
 111    SparseSet or simple bitmap representations may be more efficient than a
 112    linked-list set.  For random-access sets of unknown universe, a hash table
 113    or a balanced binary tree representation is likely to be a more suitable
 114    choice.
 115
 116    Traversing linked lists is usually cache-unfriendly, even with the last
 117    accessed element cached.
 118
 119    Cache performance can be improved by keeping the elements in the set
 120    grouped together in memory, using a dedicated obstack for a set (or group
 121    of related sets).  Elements allocated on obstacks are released to a
 122    free-list and taken off the free list.  If multiple sets are allocated on
 123    the same obstack, elements freed from one set may be re-used for one of
 124    the other sets.  This usually helps avoid cache misses.
 125
 126    A single free-list is used for all sets allocated in GGC space.  This is
 127    bad for persistent sets, so persistent sets should be allocated on an
 128    obstack whenever possible.  */
 129
 130 #include "obstack.h"
 131
 132 /* Bitmap memory usage.  */
 133 struct bitmap_usage: public mem_usage
 134 {
 135   /* Default contructor.  */
 136   bitmap_usage (): m_nsearches (0), m_search_iter (0) {}
 137   /* Constructor.  */
 138   bitmap_usage (size_t allocated, size_t times, size_t peak,
 139              uint64_t nsearches, uint64_t search_iter)
 140     : mem_usage (allocated, times, peak),
 141     m_nsearches (nsearches), m_search_iter (search_iter) {}
 142
 143   /* Sum the usage with SECOND usage.  */
 144   bitmap_usage
 145   operator+ (const bitmap_usage &second)
 146   {
 147     return bitmap_usage (m_allocated + second.m_allocated,
 148                              m_times + second.m_times,
 149                              m_peak + second.m_peak,
 150                              m_nsearches + second.m_nsearches,
 151                              m_search_iter + second.m_search_iter);
 152   }
 153
 154   /* Dump usage coupled to LOC location, where TOTAL is sum of all rows.  */
 155   inline void
 156   dump (mem_location *loc, mem_usage &total) const
 157   {
 158     char *location_string = loc->to_string ();
 159
 160     fprintf (stderr, "%-48s %10li:%5.1f%%%10li%10li:%5.1f%%%12li%12li%10s\n",
 161              location_string,
 162              (long)m_allocated, get_percent (m_allocated, total.m_allocated),
 163              (long)m_peak, (long)m_times,
 164              get_percent (m_times, total.m_times),
 165              (long)m_nsearches, (long)m_search_iter,
 166              loc->m_ggc ? "ggc" : "heap");
 167
 168     free (location_string);
 169   }
 170
 171   /* Dump header with NAME.  */
 172   static inline void
 173   dump_header (const char *name)
 174   {
 175     fprintf (stderr, "%-48s %11s%16s%17s%12s%12s%10s\n", name, "Leak", "Peak",
 176              "Times", "N searches", "Search iter", "Type");
 177     print_dash_line ();
 178   }
 179
 180   /* Number search operations.  */
 181   uint64_t m_nsearches;
 182   /* Number of search iterations.  */
 183   uint64_t m_search_iter;
 184 };
 185
 186 /* Bitmap memory description.  */
 187 extern mem_alloc_description<bitmap_usage> bitmap_mem_desc;
 188
 189 /* Fundamental storage type for bitmap.  */
 190
 191 typedef unsigned long BITMAP_WORD;
 192 /* BITMAP_WORD_BITS needs to be unsigned, but cannot contain casts as
 193    it is used in preprocessor directives -- hence the 1u.  */
 194 #define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u)
 195
 196 /* Number of words to use for each element in the linked list.  */
 197
 198 #ifndef BITMAP_ELEMENT_WORDS
 199 #define BITMAP_ELEMENT_WORDS ((128 + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
 200 #endif
 201
 202 /* Number of bits in each actual element of a bitmap.  */
 203
 204 #define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)
 205
 206 /* Obstack for allocating bitmaps and elements from.  */
 207 struct GTY (()) bitmap_obstack {
 208   struct bitmap_element *elements;
 209   struct bitmap_head *heads;
 210   struct obstack GTY ((skip)) obstack;
 211 };
 212
 213 /* Bitmap set element.  We use a linked list to hold only the bits that
 214    are set.  This allows for use to grow the bitset dynamically without
 215    having to realloc and copy a giant bit array.
 216
 217    The free list is implemented as a list of lists.  There is one
 218    outer list connected together by prev fields.  Each element of that
 219    outer is an inner list (that may consist only of the outer list
 220    element) that are connected by the next fields.  The prev pointer
 221    is undefined for interior elements.  This allows
 222    bitmap_elt_clear_from to be implemented in unit time rather than
 223    linear in the number of elements to be freed.  */
 224
 225 struct GTY((chain_next ("%h.next"), chain_prev ("%h.prev"))) bitmap_element {
 226   struct bitmap_element *next;  /* Next element.  */
 227   struct bitmap_element *prev;  /* Previous element.  */
 228   unsigned int indx;                    /* regno/BITMAP_ELEMENT_ALL_BITS.  */
 229   BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set.  */
 230 };
 231
 232 /* Head of bitmap linked list.  The 'current' member points to something
 233    already pointed to by the chain started by first, so GTY((skip)) it.  */
 234
 235 struct GTY(()) bitmap_head {
 236   unsigned int indx;                    /* Index of last element looked at.  */
 237   unsigned int descriptor_id;           /* Unique identifier for the allocation
 238                                            site of this bitmap, for detailed
 239                                            statistics gathering.  */
 240   bitmap_element *first;                /* First element in linked list.  */
 241   bitmap_element * GTY((skip(""))) current; /* Last element looked at.  */
 242   bitmap_obstack *obstack;              /* Obstack to allocate elements from.
 243                                            If NULL, then use GGC allocation.  */
 244 };
 245
 246 /* Global data */
 247 extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */
 248 extern bitmap_obstack bitmap_default_obstack;   /* Default bitmap obstack */
 249
 250 /* Clear a bitmap by freeing up the linked list.  */
 251 extern void bitmap_clear (bitmap);
 252
 253 /* Copy a bitmap to another bitmap.  */
 254 extern void bitmap_copy (bitmap, const_bitmap);
 255
 256 /* True if two bitmaps are identical.  */
 257 extern bool bitmap_equal_p (const_bitmap, const_bitmap);
 258
 259 /* True if the bitmaps intersect (their AND is non-empty).  */
 260 extern bool bitmap_intersect_p (const_bitmap, const_bitmap);
 261
 262 /* True if the complement of the second intersects the first (their
 263    AND_COMPL is non-empty).  */
 264 extern bool bitmap_intersect_compl_p (const_bitmap, const_bitmap);
 265
 266 /* True if MAP is an empty bitmap.  */
 267 inline bool bitmap_empty_p (const_bitmap map)
 268 {
 269   return !map->first;
 270 }
 271
 272 /* True if the bitmap has only a single bit set.  */
 273 extern bool bitmap_single_bit_set_p (const_bitmap);
 274
 275 /* Count the number of bits set in the bitmap.  */
 276 extern unsigned long bitmap_count_bits (const_bitmap);
 277
 278 /* Boolean operations on bitmaps.  The _into variants are two operand
 279    versions that modify the first source operand.  The other variants
 280    are three operand versions that to not destroy the source bitmaps.
 281    The operations supported are &, & ~, |, ^.  */
 282 extern void bitmap_and (bitmap, const_bitmap, const_bitmap);
 283 extern bool bitmap_and_into (bitmap, const_bitmap);
 284 extern bool bitmap_and_compl (bitmap, const_bitmap, const_bitmap);
 285 extern bool bitmap_and_compl_into (bitmap, const_bitmap);
 286 #define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A)
 287 extern void bitmap_compl_and_into (bitmap, const_bitmap);
 288 extern void bitmap_clear_range (bitmap, unsigned int, unsigned int);
 289 extern void bitmap_set_range (bitmap, unsigned int, unsigned int);
 290 extern bool bitmap_ior (bitmap, const_bitmap, const_bitmap);
 291 extern bool bitmap_ior_into (bitmap, const_bitmap);
 292 extern void bitmap_xor (bitmap, const_bitmap, const_bitmap);
 293 extern void bitmap_xor_into (bitmap, const_bitmap);
 294
 295 /* DST = A | (B & C).  Return true if DST changes.  */
 296 extern bool bitmap_ior_and_into (bitmap DST, const_bitmap B, const_bitmap C);
 297 /* DST = A | (B & ~C).  Return true if DST changes.  */
 298 extern bool bitmap_ior_and_compl (bitmap DST, const_bitmap A,
 299                                   const_bitmap B, const_bitmap C);
 300 /* A |= (B & ~C).  Return true if A changes.  */
 301 extern bool bitmap_ior_and_compl_into (bitmap A,
 302                                        const_bitmap B, const_bitmap C);
 303
 304 /* Clear a single bit in a bitmap.  Return true if the bit changed.  */
 305 extern bool bitmap_clear_bit (bitmap, int);
 306
 307 /* Set a single bit in a bitmap.  Return true if the bit changed.  */
 308 extern bool bitmap_set_bit (bitmap, int);
 309
 310 /* Return true if a register is set in a register set.  */
 311 extern int bitmap_bit_p (bitmap, int);
 312
 313 /* Debug functions to print a bitmap linked list.  */
 314 extern void debug_bitmap (const_bitmap);
 315 extern void debug_bitmap_file (FILE *, const_bitmap);
 316
 317 /* Print a bitmap.  */
 318 extern void bitmap_print (FILE *, const_bitmap, const char *, const char *);
 319
 320 /* Initialize and release a bitmap obstack.  */
 321 extern void bitmap_obstack_initialize (bitmap_obstack *);
 322 extern void bitmap_obstack_release (bitmap_obstack *);
 323 extern void bitmap_register (bitmap MEM_STAT_DECL);
 324 extern void dump_bitmap_statistics (void);
 325
 326 /* Initialize a bitmap header.  OBSTACK indicates the bitmap obstack
 327    to allocate from, NULL for GC'd bitmap.  */
 328
 329 static inline void
 330 bitmap_initialize_stat (bitmap head, bitmap_obstack *obstack MEM_STAT_DECL)
 331 {
 332   head->first = head->current = NULL;
 333   head->obstack = obstack;
 334   if (GATHER_STATISTICS)
 335     bitmap_register (head PASS_MEM_STAT);
 336 }
 337 #define bitmap_initialize(h,o) bitmap_initialize_stat (h,o MEM_STAT_INFO)
 338
 339 /* Allocate and free bitmaps from obstack, malloc and gc'd memory.  */
 340 extern bitmap bitmap_obstack_alloc_stat (bitmap_obstack *obstack MEM_STAT_DECL);
 341 #define bitmap_obstack_alloc(t) bitmap_obstack_alloc_stat (t MEM_STAT_INFO)
 342 extern bitmap bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL);
 343 #define bitmap_gc_alloc() bitmap_gc_alloc_stat (ALONE_MEM_STAT_INFO)
 344 extern void bitmap_obstack_free (bitmap);
 345
 346 /* A few compatibility/functions macros for compatibility with sbitmaps */
 347 inline void dump_bitmap (FILE *file, const_bitmap map)
 348 {
 349   bitmap_print (file, map, "", "\n");
 350 }
 351 extern void debug (const bitmap_head &ref);
 352 extern void debug (const bitmap_head *ptr);
 353
 354 extern unsigned bitmap_first_set_bit (const_bitmap);
 355 extern unsigned bitmap_last_set_bit (const_bitmap);
 356
 357 /* Compute bitmap hash (for purposes of hashing etc.)  */
 358 extern hashval_t bitmap_hash (const_bitmap);
 359
 360 /* Allocate a bitmap from a bit obstack.  */
 361 #define BITMAP_ALLOC(OBSTACK) bitmap_obstack_alloc (OBSTACK)
 362
 363 /* Allocate a gc'd bitmap.  */
 364 #define BITMAP_GGC_ALLOC() bitmap_gc_alloc ()
 365
 366 /* Do any cleanup needed on a bitmap when it is no longer used.  */
 367 #define BITMAP_FREE(BITMAP) \
 368        ((void) (bitmap_obstack_free ((bitmap) BITMAP), (BITMAP) = (bitmap) NULL))
 369
 370 /* Iterator for bitmaps.  */
 371
 372 struct bitmap_iterator
 373 {
 374   /* Pointer to the current bitmap element.  */
 375   bitmap_element *elt1;
 376
 377   /* Pointer to 2nd bitmap element when two are involved.  */
 378   bitmap_element *elt2;
 379
 380   /* Word within the current element.  */
 381   unsigned word_no;
 382
 383   /* Contents of the actually processed word.  When finding next bit
 384      it is shifted right, so that the actual bit is always the least
 385      significant bit of ACTUAL.  */
 386   BITMAP_WORD bits;
 387 };
 388
 389 /* Initialize a single bitmap iterator.  START_BIT is the first bit to
 390    iterate from.  */
 391
 392 static inline void
 393 bmp_iter_set_init (bitmap_iterator *bi, const_bitmap map,
 394                    unsigned start_bit, unsigned *bit_no)
 395 {
 396   bi->elt1 = map->first;
 397   bi->elt2 = NULL;
 398
 399   /* Advance elt1 until it is not before the block containing start_bit.  */
 400   while (1)
 401     {
 402       if (!bi->elt1)
 403         {
 404           bi->elt1 = &bitmap_zero_bits;
 405           break;
 406         }
 407
 408       if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
 409         break;
 410       bi->elt1 = bi->elt1->next;
 411     }
 412
 413   /* We might have gone past the start bit, so reinitialize it.  */
 414   if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
 415     start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 416
 417   /* Initialize for what is now start_bit.  */
 418   bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 419   bi->bits = bi->elt1->bits[bi->word_no];
 420   bi->bits >>= start_bit % BITMAP_WORD_BITS;
 421
 422   /* If this word is zero, we must make sure we're not pointing at the
 423      first bit, otherwise our incrementing to the next word boundary
 424      will fail.  It won't matter if this increment moves us into the
 425      next word.  */
 426   start_bit += !bi->bits;
 427
 428   *bit_no = start_bit;
 429 }
 430
 431 /* Initialize an iterator to iterate over the intersection of two
 432    bitmaps.  START_BIT is the bit to commence from.  */
 433
 434 static inline void
 435 bmp_iter_and_init (bitmap_iterator *bi, const_bitmap map1, const_bitmap map2,
 436                    unsigned start_bit, unsigned *bit_no)
 437 {
 438   bi->elt1 = map1->first;
 439   bi->elt2 = map2->first;
 440
 441   /* Advance elt1 until it is not before the block containing
 442      start_bit.  */
 443   while (1)
 444     {
 445       if (!bi->elt1)
 446         {
 447           bi->elt2 = NULL;
 448           break;
 449         }
 450
 451       if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
 452         break;
 453       bi->elt1 = bi->elt1->next;
 454     }
 455
 456   /* Advance elt2 until it is not before elt1.  */
 457   while (1)
 458     {
 459       if (!bi->elt2)
 460         {
 461           bi->elt1 = bi->elt2 = &bitmap_zero_bits;
 462           break;
 463         }
 464
 465       if (bi->elt2->indx >= bi->elt1->indx)
 466         break;
 467       bi->elt2 = bi->elt2->next;
 468     }
 469
 470   /* If we're at the same index, then we have some intersecting bits.  */
 471   if (bi->elt1->indx == bi->elt2->indx)
 472     {
 473       /* We might have advanced beyond the start_bit, so reinitialize
 474          for that.  */
 475       if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
 476         start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 477
 478       bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 479       bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
 480       bi->bits >>= start_bit % BITMAP_WORD_BITS;
 481     }
 482   else
 483     {
 484       /* Otherwise we must immediately advance elt1, so initialize for
 485          that.  */
 486       bi->word_no = BITMAP_ELEMENT_WORDS - 1;
 487       bi->bits = 0;
 488     }
 489
 490   /* If this word is zero, we must make sure we're not pointing at the
 491      first bit, otherwise our incrementing to the next word boundary
 492      will fail.  It won't matter if this increment moves us into the
 493      next word.  */
 494   start_bit += !bi->bits;
 495
 496   *bit_no = start_bit;
 497 }
 498
 499 /* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2.
 500    */
 501
 502 static inline void
 503 bmp_iter_and_compl_init (bitmap_iterator *bi,
 504                          const_bitmap map1, const_bitmap map2,
 505                          unsigned start_bit, unsigned *bit_no)
 506 {
 507   bi->elt1 = map1->first;
 508   bi->elt2 = map2->first;
 509
 510   /* Advance elt1 until it is not before the block containing start_bit.  */
 511   while (1)
 512     {
 513       if (!bi->elt1)
 514         {
 515           bi->elt1 = &bitmap_zero_bits;
 516           break;
 517         }
 518
 519       if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
 520         break;
 521       bi->elt1 = bi->elt1->next;
 522     }
 523
 524   /* Advance elt2 until it is not before elt1.  */
 525   while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
 526     bi->elt2 = bi->elt2->next;
 527
 528   /* We might have advanced beyond the start_bit, so reinitialize for
 529      that.  */
 530   if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
 531     start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 532
 533   bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 534   bi->bits = bi->elt1->bits[bi->word_no];
 535   if (bi->elt2 && bi->elt1->indx == bi->elt2->indx)
 536     bi->bits &= ~bi->elt2->bits[bi->word_no];
 537   bi->bits >>= start_bit % BITMAP_WORD_BITS;
 538
 539   /* If this word is zero, we must make sure we're not pointing at the
 540      first bit, otherwise our incrementing to the next word boundary
 541      will fail.  It won't matter if this increment moves us into the
 542      next word.  */
 543   start_bit += !bi->bits;
 544
 545   *bit_no = start_bit;
 546 }
 547
 548 /* Advance to the next bit in BI.  We don't advance to the next
 549    nonzero bit yet.  */
 550
 551 static inline void
 552 bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no)
 553 {
 554   bi->bits >>= 1;
 555   *bit_no += 1;
 556 }
 557
 558 /* Advance to first set bit in BI.  */
 559
 560 static inline void
 561 bmp_iter_next_bit (bitmap_iterator * bi, unsigned *bit_no)
 562 {
 563 #if (GCC_VERSION >= 3004)
 564   {
 565     unsigned int n = __builtin_ctzl (bi->bits);
 566     gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD));
 567     bi->bits >>= n;
 568     *bit_no += n;
 569   }
 570 #else
 571   while (!(bi->bits & 1))
 572     {
 573       bi->bits >>= 1;
 574       *bit_no += 1;
 575     }
 576 #endif
 577 }
 578
 579 /* Advance to the next nonzero bit of a single bitmap, we will have
 580    already advanced past the just iterated bit.  Return true if there
 581    is a bit to iterate.  */
 582
 583 static inline bool
 584 bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no)
 585 {
 586   /* If our current word is nonzero, it contains the bit we want.  */
 587   if (bi->bits)
 588     {
 589     next_bit:
 590       bmp_iter_next_bit (bi, bit_no);
 591       return true;
 592     }
 593
 594   /* Round up to the word boundary.  We might have just iterated past
 595      the end of the last word, hence the -1.  It is not possible for
 596      bit_no to point at the beginning of the now last word.  */
 597   *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
 598              / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
 599   bi->word_no++;
 600
 601   while (1)
 602     {
 603       /* Find the next nonzero word in this elt.  */
 604       while (bi->word_no != BITMAP_ELEMENT_WORDS)
 605         {
 606           bi->bits = bi->elt1->bits[bi->word_no];
 607           if (bi->bits)
 608             goto next_bit;
 609           *bit_no += BITMAP_WORD_BITS;
 610           bi->word_no++;
 611         }
 612
 613       /* Advance to the next element.  */
 614       bi->elt1 = bi->elt1->next;
 615       if (!bi->elt1)
 616         return false;
 617       *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 618       bi->word_no = 0;
 619     }
 620 }
 621
 622 /* Advance to the next nonzero bit of an intersecting pair of
 623    bitmaps.  We will have already advanced past the just iterated bit.
 624    Return true if there is a bit to iterate.  */
 625
 626 static inline bool
 627 bmp_iter_and (bitmap_iterator *bi, unsigned *bit_no)
 628 {
 629   /* If our current word is nonzero, it contains the bit we want.  */
 630   if (bi->bits)
 631     {
 632     next_bit:
 633       bmp_iter_next_bit (bi, bit_no);
 634       return true;
 635     }
 636
 637   /* Round up to the word boundary.  We might have just iterated past
 638      the end of the last word, hence the -1.  It is not possible for
 639      bit_no to point at the beginning of the now last word.  */
 640   *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
 641              / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
 642   bi->word_no++;
 643
 644   while (1)
 645     {
 646       /* Find the next nonzero word in this elt.  */
 647       while (bi->word_no != BITMAP_ELEMENT_WORDS)
 648         {
 649           bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
 650           if (bi->bits)
 651             goto next_bit;
 652           *bit_no += BITMAP_WORD_BITS;
 653           bi->word_no++;
 654         }
 655
 656       /* Advance to the next identical element.  */
 657       do
 658         {
 659           /* Advance elt1 while it is less than elt2.  We always want
 660              to advance one elt.  */
 661           do
 662             {
 663               bi->elt1 = bi->elt1->next;
 664               if (!bi->elt1)
 665                 return false;
 666             }
 667           while (bi->elt1->indx < bi->elt2->indx);
 668
 669           /* Advance elt2 to be no less than elt1.  This might not
 670              advance.  */
 671           while (bi->elt2->indx < bi->elt1->indx)
 672             {
 673               bi->elt2 = bi->elt2->next;
 674               if (!bi->elt2)
 675                 return false;
 676             }
 677         }
 678       while (bi->elt1->indx != bi->elt2->indx);
 679
 680       *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 681       bi->word_no = 0;
 682     }
 683 }
 684
 685 /* Advance to the next nonzero bit in the intersection of
 686    complemented bitmaps.  We will have already advanced past the just
 687    iterated bit.  */
 688
 689 static inline bool
 690 bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no)
 691 {
 692   /* If our current word is nonzero, it contains the bit we want.  */
 693   if (bi->bits)
 694     {
 695     next_bit:
 696       bmp_iter_next_bit (bi, bit_no);
 697       return true;
 698     }
 699
 700   /* Round up to the word boundary.  We might have just iterated past
 701      the end of the last word, hence the -1.  It is not possible for
 702      bit_no to point at the beginning of the now last word.  */
 703   *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
 704              / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
 705   bi->word_no++;
 706
 707   while (1)
 708     {
 709       /* Find the next nonzero word in this elt.  */
 710       while (bi->word_no != BITMAP_ELEMENT_WORDS)
 711         {
 712           bi->bits = bi->elt1->bits[bi->word_no];
 713           if (bi->elt2 && bi->elt2->indx == bi->elt1->indx)
 714             bi->bits &= ~bi->elt2->bits[bi->word_no];
 715           if (bi->bits)
 716             goto next_bit;
 717           *bit_no += BITMAP_WORD_BITS;
 718           bi->word_no++;
 719         }
 720
 721       /* Advance to the next element of elt1.  */
 722       bi->elt1 = bi->elt1->next;
 723       if (!bi->elt1)
 724         return false;
 725
 726       /* Advance elt2 until it is no less than elt1.  */
 727       while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
 728         bi->elt2 = bi->elt2->next;
 729
 730       *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
 731       bi->word_no = 0;
 732     }
 733 }
 734
 735 /* Loop over all bits set in BITMAP, starting with MIN and setting
 736    BITNUM to the bit number.  ITER is a bitmap iterator.  BITNUM
 737    should be treated as a read-only variable as it contains loop
 738    state.  */
 739
 740 #ifndef EXECUTE_IF_SET_IN_BITMAP
 741 /* See sbitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP.  */
 742 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER)             \
 743   for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM));         \
 744        bmp_iter_set (&(ITER), &(BITNUM));                               \
 745        bmp_iter_next (&(ITER), &(BITNUM)))
 746 #endif
 747
 748 /* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN
 749    and setting BITNUM to the bit number.  ITER is a bitmap iterator.
 750    BITNUM should be treated as a read-only variable as it contains
 751    loop state.  */
 752
 753 #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER)   \
 754   for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN),         \
 755                           &(BITNUM));                                   \
 756        bmp_iter_and (&(ITER), &(BITNUM));                               \
 757        bmp_iter_next (&(ITER), &(BITNUM)))
 758
 759 /* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN
 760    and setting BITNUM to the bit number.  ITER is a bitmap iterator.
 761    BITNUM should be treated as a read-only variable as it contains
 762    loop state.  */
 763
 764 #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
 765   for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN),   \
 766                                 &(BITNUM));                             \
 767        bmp_iter_and_compl (&(ITER), &(BITNUM));                         \
 768        bmp_iter_next (&(ITER), &(BITNUM)))
 769
 770 #endif /* GCC_BITMAP_H */