LCOV - code coverage report
Current view: top level - gcc - bitmap.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 206 213 96.7 %
Date: 2020-03-28 11:57:23 Functions: 7 7 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Functions to support general ended bitmaps.
       2                 :            :    Copyright (C) 1997-2020 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 or tree.
      24                 :            : 
      25                 :            :    This sparse set representation is suitable for sparse sets with an
      26                 :            :    unknown (a priori) universe.
      27                 :            : 
      28                 :            :    Sets are represented as double-linked lists of container nodes of
      29                 :            :    type "struct bitmap_element" or as a binary trees of the same
      30                 :            :    container nodes.  Each container node consists of an index for the
      31                 :            :    first member that could be held in the container, a small array of
      32                 :            :    integers that represent the members in the container, and pointers
      33                 :            :    to the next and previous element in the linked list, or left and
      34                 :            :    right children in the tree.  In linked-list form, the container
      35                 :            :    nodes in the list are sorted in ascending order, i.e. the head of
      36                 :            :    the list holds the element with the smallest member of the set.
      37                 :            :    In tree form, nodes to the left have a smaller container index.
      38                 :            : 
      39                 :            :    For a given member I in the set:
      40                 :            :      - the element for I will have index is I / (bits per element)
      41                 :            :      - the position for I within element is I % (bits per element)
      42                 :            : 
      43                 :            :    This representation is very space-efficient for large sparse sets, and
      44                 :            :    the size of the set can be changed dynamically without much overhead.
      45                 :            :    An important parameter is the number of bits per element.  In this
      46                 :            :    implementation, there are 128 bits per element.  This results in a
      47                 :            :    high storage overhead *per element*, but a small overall overhead if
      48                 :            :    the set is very sparse.
      49                 :            : 
      50                 :            :    The storage requirements for linked-list sparse sets are O(E), with E->N
      51                 :            :    in the worst case (a sparse set with large distances between the values
      52                 :            :    of the set members).
      53                 :            : 
      54                 :            :    This representation also works well for data flow problems where the size
      55                 :            :    of the set may grow dynamically, but care must be taken that the member_p,
      56                 :            :    add_member, and remove_member operations occur with a suitable access
      57                 :            :    pattern.
      58                 :            : 
      59                 :            :    The linked-list set representation works well for problems involving very
      60                 :            :    sparse sets.  The canonical example in GCC is, of course, the "set of
      61                 :            :    sets" for some CFG-based data flow problems (liveness analysis, dominance
      62                 :            :    frontiers, etc.).
      63                 :            :    
      64                 :            :    For random-access sparse sets of unknown universe, the binary tree
      65                 :            :    representation is likely to be a more suitable choice.  Theoretical
      66                 :            :    access times for the binary tree representation are better than those
      67                 :            :    for the linked-list, but in practice this is only true for truely
      68                 :            :    random access.
      69                 :            : 
      70                 :            :    Often the most suitable representation during construction of the set
      71                 :            :    is not the best choice for the usage of the set.  For such cases, the
      72                 :            :    "view" of the set can be changed from one representation to the other.
      73                 :            :    This is an O(E) operation:
      74                 :            : 
      75                 :            :      * from list to tree view   : bitmap_tree_view
      76                 :            :      * from tree to list view   : bitmap_list_view
      77                 :            : 
      78                 :            :    Traversing linked lists or trees can be cache-unfriendly.  Performance
      79                 :            :    can be improved by keeping container nodes in the set grouped together
      80                 :            :    in  memory, using a dedicated obstack for a set (or group of related
      81                 :            :    sets).  Elements allocated on obstacks are released to a free-list and
      82                 :            :    taken off the free list.  If multiple sets are allocated on the same
      83                 :            :    obstack, elements freed from one set may be re-used for one of the other
      84                 :            :    sets.  This usually helps avoid cache misses.
      85                 :            : 
      86                 :            :    A single free-list is used for all sets allocated in GGC space.  This is
      87                 :            :    bad for persistent sets, so persistent sets should be allocated on an
      88                 :            :    obstack whenever possible.
      89                 :            : 
      90                 :            :    For random-access sets with a known, relatively small universe size, the
      91                 :            :    SparseSet or simple bitmap representations may be more efficient than a
      92                 :            :    linked-list set.
      93                 :            : 
      94                 :            : 
      95                 :            :    LINKED LIST FORM
      96                 :            :    ================
      97                 :            : 
      98                 :            :    In linked-list form, in-order iterations of the set can be executed
      99                 :            :    efficiently.  The downside is that many random-access operations are
     100                 :            :    relatively slow, because the linked list has to be traversed to test
     101                 :            :    membership (i.e. member_p/ add_member/remove_member).
     102                 :            :    
     103                 :            :    To improve the performance of this set representation, the last
     104                 :            :    accessed element and its index are cached.  For membership tests on
     105                 :            :    members close to recently accessed members, the cached last element
     106                 :            :    improves membership test to a constant-time operation.
     107                 :            : 
     108                 :            :    The following operations can always be performed in O(1) time in
     109                 :            :    list view:
     110                 :            : 
     111                 :            :      * clear                    : bitmap_clear
     112                 :            :      * smallest_member          : bitmap_first_set_bit
     113                 :            :      * choose_one               : (not implemented, but could be
     114                 :            :                                    in constant time)
     115                 :            : 
     116                 :            :    The following operations can be performed in O(E) time worst-case in
     117                 :            :    list view (with E the number of elements in the linked list), but in
     118                 :            :    O(1) time with a suitable access patterns:
     119                 :            : 
     120                 :            :      * member_p                 : bitmap_bit_p
     121                 :            :      * add_member               : bitmap_set_bit / bitmap_set_range
     122                 :            :      * remove_member            : bitmap_clear_bit / bitmap_clear_range
     123                 :            : 
     124                 :            :    The following operations can be performed in O(E) time in list view:
     125                 :            : 
     126                 :            :      * cardinality              : bitmap_count_bits
     127                 :            :      * largest_member           : bitmap_last_set_bit (but this could
     128                 :            :                                   in constant time with a pointer to
     129                 :            :                                   the last element in the chain)
     130                 :            :      * set_size                 : bitmap_last_set_bit
     131                 :            : 
     132                 :            :    In tree view the following operations can all be performed in O(log E)
     133                 :            :    amortized time with O(E) worst-case behavior.
     134                 :            : 
     135                 :            :      * smallest_member
     136                 :            :      * largest_member
     137                 :            :      * set_size
     138                 :            :      * member_p
     139                 :            :      * add_member
     140                 :            :      * remove_member
     141                 :            : 
     142                 :            :    Additionally, the linked-list sparse set representation supports
     143                 :            :    enumeration of the members in O(E) time:
     144                 :            : 
     145                 :            :      * forall                   : EXECUTE_IF_SET_IN_BITMAP
     146                 :            :      * set_copy                 : bitmap_copy
     147                 :            :      * set_intersection         : bitmap_intersect_p /
     148                 :            :                                   bitmap_and / bitmap_and_into /
     149                 :            :                                   EXECUTE_IF_AND_IN_BITMAP
     150                 :            :      * set_union                : bitmap_ior / bitmap_ior_into
     151                 :            :      * set_difference           : bitmap_intersect_compl_p /
     152                 :            :                                   bitmap_and_comp / bitmap_and_comp_into /
     153                 :            :                                   EXECUTE_IF_AND_COMPL_IN_BITMAP
     154                 :            :      * set_disjuction           : bitmap_xor_comp / bitmap_xor_comp_into
     155                 :            :      * set_compare              : bitmap_equal_p
     156                 :            : 
     157                 :            :    Some operations on 3 sets that occur frequently in data flow problems
     158                 :            :    are also implemented:
     159                 :            : 
     160                 :            :      * A | (B & C)          : bitmap_ior_and_into
     161                 :            :      * A | (B & ~C)         : bitmap_ior_and_compl /
     162                 :            :                                   bitmap_ior_and_compl_into
     163                 :            : 
     164                 :            : 
     165                 :            :    BINARY TREE FORM
     166                 :            :    ================
     167                 :            :    An alternate "view" of a bitmap is its binary tree representation.
     168                 :            :    For this representation, splay trees are used because they can be
     169                 :            :    implemented using the same data structures as the linked list, with
     170                 :            :    no overhead for meta-data (like color, or rank) on the tree nodes.
     171                 :            : 
     172                 :            :    In binary tree form, random-access to the set is much more efficient
     173                 :            :    than for the linked-list representation.  Downsides are the high cost
     174                 :            :    of clearing the set, and the relatively large number of operations
     175                 :            :    necessary to balance the tree.  Also, iterating the set members is
     176                 :            :    not supported.
     177                 :            :    
     178                 :            :    As for the linked-list representation, the last accessed element and
     179                 :            :    its index are cached, so that membership tests on the latest accessed
     180                 :            :    members is a constant-time operation.  Other lookups take O(logE)
     181                 :            :    time amortized (but O(E) time worst-case).
     182                 :            : 
     183                 :            :    The following operations can always be performed in O(1) time:
     184                 :            : 
     185                 :            :      * choose_one               : (not implemented, but could be
     186                 :            :                                    implemented in constant time)
     187                 :            : 
     188                 :            :    The following operations can be performed in O(logE) time amortized
     189                 :            :    but O(E) time worst-case, but in O(1) time if the same element is
     190                 :            :    accessed.
     191                 :            : 
     192                 :            :      * member_p                 : bitmap_bit_p
     193                 :            :      * add_member               : bitmap_set_bit
     194                 :            :      * remove_member            : bitmap_clear_bit
     195                 :            : 
     196                 :            :    The following operations can be performed in O(logE) time amortized
     197                 :            :    but O(E) time worst-case:
     198                 :            : 
     199                 :            :      * smallest_member          : bitmap_first_set_bit
     200                 :            :      * largest_member           : bitmap_last_set_bit
     201                 :            :      * set_size                 : bitmap_last_set_bit
     202                 :            : 
     203                 :            :    The following operations can be performed in O(E) time:
     204                 :            : 
     205                 :            :      * clear                    : bitmap_clear
     206                 :            : 
     207                 :            :    The binary tree sparse set representation does *not* support any form
     208                 :            :    of enumeration, and does also *not* support logical operations on sets.
     209                 :            :    The binary tree representation is only supposed to be used for sets
     210                 :            :    on which many random-access membership tests will happen.  */
     211                 :            : 
     212                 :            : #include "obstack.h"
     213                 :            : #include "array-traits.h"
     214                 :            : 
     215                 :            : /* Bitmap memory usage.  */
     216                 :            : class bitmap_usage: public mem_usage
     217                 :            : {
     218                 :            : public:
     219                 :            :   /* Default contructor.  */
     220                 :          0 :   bitmap_usage (): m_nsearches (0), m_search_iter (0) {}
     221                 :            :   /* Constructor.  */
     222                 :            :   bitmap_usage (size_t allocated, size_t times, size_t peak,
     223                 :            :              uint64_t nsearches, uint64_t search_iter)
     224                 :            :     : mem_usage (allocated, times, peak),
     225                 :            :     m_nsearches (nsearches), m_search_iter (search_iter) {}
     226                 :            : 
     227                 :            :   /* Sum the usage with SECOND usage.  */
     228                 :            :   bitmap_usage
     229                 :            :   operator+ (const bitmap_usage &second)
     230                 :            :   {
     231                 :            :     return bitmap_usage (m_allocated + second.m_allocated,
     232                 :            :                              m_times + second.m_times,
     233                 :            :                              m_peak + second.m_peak,
     234                 :            :                              m_nsearches + second.m_nsearches,
     235                 :            :                              m_search_iter + second.m_search_iter);
     236                 :            :   }
     237                 :            : 
     238                 :            :   /* Dump usage coupled to LOC location, where TOTAL is sum of all rows.  */
     239                 :            :   inline void
     240                 :            :   dump (mem_location *loc, mem_usage &total) const
     241                 :            :   {
     242                 :            :     char *location_string = loc->to_string ();
     243                 :            : 
     244                 :            :     fprintf (stderr, "%-48s " PRsa (9) ":%5.1f%%"
     245                 :            :              PRsa (9) PRsa (9) ":%5.1f%%"
     246                 :            :              PRsa (11) PRsa (11) "%10s\n",
     247                 :            :              location_string, SIZE_AMOUNT (m_allocated),
     248                 :            :              get_percent (m_allocated, total.m_allocated),
     249                 :            :              SIZE_AMOUNT (m_peak), SIZE_AMOUNT (m_times),
     250                 :            :              get_percent (m_times, total.m_times),
     251                 :            :              SIZE_AMOUNT (m_nsearches), SIZE_AMOUNT (m_search_iter),
     252                 :            :              loc->m_ggc ? "ggc" : "heap");
     253                 :            : 
     254                 :            :     free (location_string);
     255                 :            :   }
     256                 :            : 
     257                 :            :   /* Dump header with NAME.  */
     258                 :            :   static inline void
     259                 :            :   dump_header (const char *name)
     260                 :            :   {
     261                 :            :     fprintf (stderr, "%-48s %11s%16s%17s%12s%12s%10s\n", name, "Leak", "Peak",
     262                 :            :              "Times", "N searches", "Search iter", "Type");
     263                 :            :   }
     264                 :            : 
     265                 :            :   /* Number search operations.  */
     266                 :            :   uint64_t m_nsearches;
     267                 :            :   /* Number of search iterations.  */
     268                 :            :   uint64_t m_search_iter;
     269                 :            : };
     270                 :            : 
     271                 :            : /* Bitmap memory description.  */
     272                 :            : extern mem_alloc_description<bitmap_usage> bitmap_mem_desc;
     273                 :            : 
     274                 :            : /* Fundamental storage type for bitmap.  */
     275                 :            : 
     276                 :            : typedef unsigned long BITMAP_WORD;
     277                 :            : /* BITMAP_WORD_BITS needs to be unsigned, but cannot contain casts as
     278                 :            :    it is used in preprocessor directives -- hence the 1u.  */
     279                 :            : #define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u)
     280                 :            : 
     281                 :            : /* Number of words to use for each element in the linked list.  */
     282                 :            : 
     283                 :            : #ifndef BITMAP_ELEMENT_WORDS
     284                 :            : #define BITMAP_ELEMENT_WORDS ((128 + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
     285                 :            : #endif
     286                 :            : 
     287                 :            : /* Number of bits in each actual element of a bitmap.  */
     288                 :            : 
     289                 :            : #define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)
     290                 :            : 
     291                 :            : /* Obstack for allocating bitmaps and elements from.  */
     292                 :            : struct bitmap_obstack {
     293                 :            :   struct bitmap_element *elements;
     294                 :            :   bitmap_head *heads;
     295                 :            :   struct obstack obstack;
     296                 :            : };
     297                 :            : 
     298                 :            : /* Bitmap set element.  We use a linked list to hold only the bits that
     299                 :            :    are set.  This allows for use to grow the bitset dynamically without
     300                 :            :    having to realloc and copy a giant bit array.
     301                 :            : 
     302                 :            :    The free list is implemented as a list of lists.  There is one
     303                 :            :    outer list connected together by prev fields.  Each element of that
     304                 :            :    outer is an inner list (that may consist only of the outer list
     305                 :            :    element) that are connected by the next fields.  The prev pointer
     306                 :            :    is undefined for interior elements.  This allows
     307                 :            :    bitmap_elt_clear_from to be implemented in unit time rather than
     308                 :            :    linear in the number of elements to be freed.  */
     309                 :            : 
     310                 :            : struct GTY((chain_next ("%h.next"))) bitmap_element {
     311                 :            :   /* In list form, the next element in the linked list;
     312                 :            :      in tree form, the left child node in the tree.  */
     313                 :            :   struct bitmap_element *next;
     314                 :            :   /* In list form, the previous element in the linked list;
     315                 :            :      in tree form, the right child node in the tree.  */
     316                 :            :   struct bitmap_element *prev;
     317                 :            :   /* regno/BITMAP_ELEMENT_ALL_BITS.  */
     318                 :            :   unsigned int indx;
     319                 :            :   /* Bits that are set, counting from INDX, inclusive  */
     320                 :            :   BITMAP_WORD bits[BITMAP_ELEMENT_WORDS];
     321                 :            : };
     322                 :            : 
     323                 :            : /* Head of bitmap linked list.  The 'current' member points to something
     324                 :            :    already pointed to by the chain started by first, so GTY((skip)) it.  */
     325                 :            : 
     326                 :            : class GTY(()) bitmap_head {
     327                 :            : public:
     328                 :            :   static bitmap_obstack crashme;
     329                 :            :   /* Poison obstack to not make it not a valid initialized GC bitmap.  */
     330                 :  528528404 :   CONSTEXPR bitmap_head()
     331                 :  528528404 :     : indx (0), tree_form (false), padding (0), alloc_descriptor (0), first (NULL),
     332                 :  528528404 :       current (NULL), obstack (&crashme)
     333                 :            :   {}
     334                 :            :   /* Index of last element looked at.  */
     335                 :            :   unsigned int indx;
     336                 :            :   /* False if the bitmap is in list form; true if the bitmap is in tree form.
     337                 :            :      Bitmap iterators only work on bitmaps in list form.  */
     338                 :            :   unsigned tree_form: 1;
     339                 :            :   /* Next integer is shifted, so padding is needed.  */
     340                 :            :   unsigned padding: 2;
     341                 :            :   /* Bitmap UID used for memory allocation statistics.  */
     342                 :            :   unsigned alloc_descriptor: 29;
     343                 :            :   /* In list form, the first element in the linked list;
     344                 :            :      in tree form, the root of the tree.   */
     345                 :            :   bitmap_element *first;
     346                 :            :   /* Last element looked at.  */
     347                 :            :   bitmap_element * GTY((skip(""))) current;
     348                 :            :   /* Obstack to allocate elements from.  If NULL, then use GGC allocation.  */
     349                 :            :   bitmap_obstack * GTY((skip(""))) obstack;
     350                 :            : 
     351                 :            :   /* Dump bitmap.  */
     352                 :            :   void dump ();
     353                 :            : 
     354                 :            :   /* Get bitmap descriptor UID casted to an unsigned integer pointer.
     355                 :            :      Shift the descriptor because pointer_hash<Type>::hash is
     356                 :            :      doing >> 3 shift operation.  */
     357                 :          0 :   unsigned *get_descriptor ()
     358                 :            :   {
     359                 :          0 :     return (unsigned *)(ptrdiff_t)(alloc_descriptor << 3);
     360                 :            :   }
     361                 :            : };
     362                 :            : 
     363                 :            : /* Global data */
     364                 :            : extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */
     365                 :            : extern bitmap_obstack bitmap_default_obstack;   /* Default bitmap obstack */
     366                 :            : 
     367                 :            : /* Change the view of the bitmap to list, or tree.  */
     368                 :            : void bitmap_list_view (bitmap);
     369                 :            : void bitmap_tree_view (bitmap);
     370                 :            : 
     371                 :            : /* Clear a bitmap by freeing up the linked list.  */
     372                 :            : extern void bitmap_clear (bitmap);
     373                 :            : 
     374                 :            : /* Copy a bitmap to another bitmap.  */
     375                 :            : extern void bitmap_copy (bitmap, const_bitmap);
     376                 :            : 
     377                 :            : /* Move a bitmap to another bitmap.  */
     378                 :            : extern void bitmap_move (bitmap, bitmap);
     379                 :            : 
     380                 :            : /* True if two bitmaps are identical.  */
     381                 :            : extern bool bitmap_equal_p (const_bitmap, const_bitmap);
     382                 :            : 
     383                 :            : /* True if the bitmaps intersect (their AND is non-empty).  */
     384                 :            : extern bool bitmap_intersect_p (const_bitmap, const_bitmap);
     385                 :            : 
     386                 :            : /* True if the complement of the second intersects the first (their
     387                 :            :    AND_COMPL is non-empty).  */
     388                 :            : extern bool bitmap_intersect_compl_p (const_bitmap, const_bitmap);
     389                 :            : 
     390                 :            : /* True if MAP is an empty bitmap.  */
     391                 : 2401441183 : inline bool bitmap_empty_p (const_bitmap map)
     392                 :            : {
     393                 : 1504635604 :   return !map->first;
     394                 :            : }
     395                 :            : 
     396                 :            : /* True if the bitmap has only a single bit set.  */
     397                 :            : extern bool bitmap_single_bit_set_p (const_bitmap);
     398                 :            : 
     399                 :            : /* Count the number of bits set in the bitmap.  */
     400                 :            : extern unsigned long bitmap_count_bits (const_bitmap);
     401                 :            : 
     402                 :            : /* Count the number of unique bits set across the two bitmaps.  */
     403                 :            : extern unsigned long bitmap_count_unique_bits (const_bitmap, const_bitmap);
     404                 :            : 
     405                 :            : /* Boolean operations on bitmaps.  The _into variants are two operand
     406                 :            :    versions that modify the first source operand.  The other variants
     407                 :            :    are three operand versions that to not destroy the source bitmaps.
     408                 :            :    The operations supported are &, & ~, |, ^.  */
     409                 :            : extern void bitmap_and (bitmap, const_bitmap, const_bitmap);
     410                 :            : extern bool bitmap_and_into (bitmap, const_bitmap);
     411                 :            : extern bool bitmap_and_compl (bitmap, const_bitmap, const_bitmap);
     412                 :            : extern bool bitmap_and_compl_into (bitmap, const_bitmap);
     413                 :            : #define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A)
     414                 :            : extern void bitmap_compl_and_into (bitmap, const_bitmap);
     415                 :            : extern void bitmap_clear_range (bitmap, unsigned int, unsigned int);
     416                 :            : extern void bitmap_set_range (bitmap, unsigned int, unsigned int);
     417                 :            : extern bool bitmap_ior (bitmap, const_bitmap, const_bitmap);
     418                 :            : extern bool bitmap_ior_into (bitmap, const_bitmap);
     419                 :            : extern bool bitmap_ior_into_and_free (bitmap, bitmap *);
     420                 :            : extern void bitmap_xor (bitmap, const_bitmap, const_bitmap);
     421                 :            : extern void bitmap_xor_into (bitmap, const_bitmap);
     422                 :            : 
     423                 :            : /* DST = A | (B & C).  Return true if DST changes.  */
     424                 :            : extern bool bitmap_ior_and_into (bitmap DST, const_bitmap B, const_bitmap C);
     425                 :            : /* DST = A | (B & ~C).  Return true if DST changes.  */
     426                 :            : extern bool bitmap_ior_and_compl (bitmap DST, const_bitmap A,
     427                 :            :                                   const_bitmap B, const_bitmap C);
     428                 :            : /* A |= (B & ~C).  Return true if A changes.  */
     429                 :            : extern bool bitmap_ior_and_compl_into (bitmap A,
     430                 :            :                                        const_bitmap B, const_bitmap C);
     431                 :            : 
     432                 :            : /* Clear a single bit in a bitmap.  Return true if the bit changed.  */
     433                 :            : extern bool bitmap_clear_bit (bitmap, int);
     434                 :            : 
     435                 :            : /* Set a single bit in a bitmap.  Return true if the bit changed.  */
     436                 :            : extern bool bitmap_set_bit (bitmap, int);
     437                 :            : 
     438                 :            : /* Return true if a bit is set in a bitmap.  */
     439                 :            : extern int bitmap_bit_p (const_bitmap, int);
     440                 :            : 
     441                 :            : /* Debug functions to print a bitmap.  */
     442                 :            : extern void debug_bitmap (const_bitmap);
     443                 :            : extern void debug_bitmap_file (FILE *, const_bitmap);
     444                 :            : 
     445                 :            : /* Print a bitmap.  */
     446                 :            : extern void bitmap_print (FILE *, const_bitmap, const char *, const char *);
     447                 :            : 
     448                 :            : /* Initialize and release a bitmap obstack.  */
     449                 :            : extern void bitmap_obstack_initialize (bitmap_obstack *);
     450                 :            : extern void bitmap_obstack_release (bitmap_obstack *);
     451                 :            : extern void bitmap_register (bitmap MEM_STAT_DECL);
     452                 :            : extern void dump_bitmap_statistics (void);
     453                 :            : 
     454                 :            : /* Initialize a bitmap header.  OBSTACK indicates the bitmap obstack
     455                 :            :    to allocate from, NULL for GC'd bitmap.  */
     456                 :            : 
     457                 :            : static inline void
     458                 : 2413979364 : bitmap_initialize (bitmap head, bitmap_obstack *obstack CXX_MEM_STAT_INFO)
     459                 :            : {
     460                 : 2413979364 :   head->first = head->current = NULL;
     461                 : 2413979364 :   head->indx = head->tree_form = 0;
     462                 : 2413979364 :   head->padding = 0;
     463                 : 2413979364 :   head->alloc_descriptor = 0;
     464                 : 2413979364 :   head->obstack = obstack;
     465                 : 2215885744 :   if (GATHER_STATISTICS)
     466                 :            :     bitmap_register (head PASS_MEM_STAT);
     467                 :   89383421 : }
     468                 :            : 
     469                 :            : /* Release a bitmap (but not its head).  This is suitable for pairing with
     470                 :            :    bitmap_initialize.  */
     471                 :            : 
     472                 :            : static inline void
     473                 :   19068236 : bitmap_release (bitmap head)
     474                 :            : {
     475                 :   12265792 :   bitmap_clear (head);
     476                 :            :   /* Poison the obstack pointer so the obstack can be safely released.
     477                 :            :      Do not zero it as the bitmap then becomes initialized GC.  */
     478                 :   12265792 :   head->obstack = &bitmap_head::crashme;
     479                 :            : }
     480                 :            : 
     481                 :            : /* Allocate and free bitmaps from obstack, malloc and gc'd memory.  */
     482                 :            : extern bitmap bitmap_alloc (bitmap_obstack *obstack CXX_MEM_STAT_INFO);
     483                 :            : #define BITMAP_ALLOC bitmap_alloc
     484                 :            : extern bitmap bitmap_gc_alloc (ALONE_CXX_MEM_STAT_INFO);
     485                 :            : #define BITMAP_GGC_ALLOC bitmap_gc_alloc
     486                 :            : extern void bitmap_obstack_free (bitmap);
     487                 :            : 
     488                 :            : /* A few compatibility/functions macros for compatibility with sbitmaps */
     489                 :        984 : inline void dump_bitmap (FILE *file, const_bitmap map)
     490                 :            : {
     491                 :        984 :   bitmap_print (file, map, "", "\n");
     492                 :        340 : }
     493                 :            : extern void debug (const bitmap_head &ref);
     494                 :            : extern void debug (const bitmap_head *ptr);
     495                 :            : 
     496                 :            : extern unsigned bitmap_first_set_bit (const_bitmap);
     497                 :            : extern unsigned bitmap_last_set_bit (const_bitmap);
     498                 :            : 
     499                 :            : /* Compute bitmap hash (for purposes of hashing etc.)  */
     500                 :            : extern hashval_t bitmap_hash (const_bitmap);
     501                 :            : 
     502                 :            : /* Do any cleanup needed on a bitmap when it is no longer used.  */
     503                 :            : #define BITMAP_FREE(BITMAP) \
     504                 :            :        ((void) (bitmap_obstack_free ((bitmap) BITMAP), (BITMAP) = (bitmap) NULL))
     505                 :            : 
     506                 :            : /* Iterator for bitmaps.  */
     507                 :            : 
     508                 :            : struct bitmap_iterator
     509                 :            : {
     510                 :            :   /* Pointer to the current bitmap element.  */
     511                 :            :   bitmap_element *elt1;
     512                 :            : 
     513                 :            :   /* Pointer to 2nd bitmap element when two are involved.  */
     514                 :            :   bitmap_element *elt2;
     515                 :            : 
     516                 :            :   /* Word within the current element.  */
     517                 :            :   unsigned word_no;
     518                 :            : 
     519                 :            :   /* Contents of the actually processed word.  When finding next bit
     520                 :            :      it is shifted right, so that the actual bit is always the least
     521                 :            :      significant bit of ACTUAL.  */
     522                 :            :   BITMAP_WORD bits;
     523                 :            : };
     524                 :            : 
     525                 :            : /* Initialize a single bitmap iterator.  START_BIT is the first bit to
     526                 :            :    iterate from.  */
     527                 :            : 
     528                 :            : static inline void
     529                 : 2166917172 : bmp_iter_set_init (bitmap_iterator *bi, const_bitmap map,
     530                 :            :                    unsigned start_bit, unsigned *bit_no)
     531                 :            : {
     532                 : 2166917172 :   bi->elt1 = map->first;
     533                 : 2166917172 :   bi->elt2 = NULL;
     534                 :            : 
     535                 : 2166917172 :   gcc_checking_assert (!map->tree_form);
     536                 :            : 
     537                 :            :   /* Advance elt1 until it is not before the block containing start_bit.  */
     538                 : 3336624772 :   while (1)
     539                 :            :     {
     540                 : 2751768972 :       if (!bi->elt1)
     541                 :            :         {
     542                 :  555777442 :           bi->elt1 = &bitmap_zero_bits;
     543                 :  555777442 :           break;
     544                 :            :         }
     545                 :            : 
     546                 : 2195996021 :       if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
     547                 :            :         break;
     548                 :  584854820 :       bi->elt1 = bi->elt1->next;
     549                 :            :     }
     550                 :            : 
     551                 :            :   /* We might have gone past the start bit, so reinitialize it.  */
     552                 : 2166917172 :   if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
     553                 :  179356588 :     start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
     554                 :            : 
     555                 :            :   /* Initialize for what is now start_bit.  */
     556                 : 2166917172 :   bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
     557                 : 2166917172 :   bi->bits = bi->elt1->bits[bi->word_no];
     558                 : 2166917172 :   bi->bits >>= start_bit % BITMAP_WORD_BITS;
     559                 :            : 
     560                 :            :   /* If this word is zero, we must make sure we're not pointing at the
     561                 :            :      first bit, otherwise our incrementing to the next word boundary
     562                 :            :      will fail.  It won't matter if this increment moves us into the
     563                 :            :      next word.  */
     564                 : 2166917172 :   start_bit += !bi->bits;
     565                 :            : 
     566                 : 2166917172 :   *bit_no = start_bit;
     567                 : 2166917172 : }
     568                 :            : 
     569                 :            : /* Initialize an iterator to iterate over the intersection of two
     570                 :            :    bitmaps.  START_BIT is the bit to commence from.  */
     571                 :            : 
     572                 :            : static inline void
     573                 :   20543277 : bmp_iter_and_init (bitmap_iterator *bi, const_bitmap map1, const_bitmap map2,
     574                 :            :                    unsigned start_bit, unsigned *bit_no)
     575                 :            : {
     576                 :   20543277 :   bi->elt1 = map1->first;
     577                 :   20543277 :   bi->elt2 = map2->first;
     578                 :            : 
     579                 :   20543277 :   gcc_checking_assert (!map1->tree_form && !map2->tree_form);
     580                 :            : 
     581                 :            :   /* Advance elt1 until it is not before the block containing
     582                 :            :      start_bit.  */
     583                 :   20543277 :   while (1)
     584                 :            :     {
     585                 :   20543277 :       if (!bi->elt1)
     586                 :            :         {
     587                 :    1905555 :           bi->elt2 = NULL;
     588                 :    1905555 :           break;
     589                 :            :         }
     590                 :            : 
     591                 :   18637716 :       if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
     592                 :            :         break;
     593                 :          0 :       bi->elt1 = bi->elt1->next;
     594                 :            :     }
     595                 :            : 
     596                 :            :   /* Advance elt2 until it is not before elt1.  */
     597                 :   79884157 :   while (1)
     598                 :            :     {
     599                 :   50213717 :       if (!bi->elt2)
     600                 :            :         {
     601                 :    2229221 :           bi->elt1 = bi->elt2 = &bitmap_zero_bits;
     602                 :    2229221 :           break;
     603                 :            :         }
     604                 :            : 
     605                 :   47984522 :       if (bi->elt2->indx >= bi->elt1->indx)
     606                 :            :         break;
     607                 :   29670440 :       bi->elt2 = bi->elt2->next;
     608                 :            :     }
     609                 :            : 
     610                 :            :   /* If we're at the same index, then we have some intersecting bits.  */
     611                 :   20543277 :   if (bi->elt1->indx == bi->elt2->indx)
     612                 :            :     {
     613                 :            :       /* We might have advanced beyond the start_bit, so reinitialize
     614                 :            :          for that.  */
     615                 :   19994877 :       if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
     616                 :    7998566 :         start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
     617                 :            : 
     618                 :   19994877 :       bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
     619                 :   19994877 :       bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
     620                 :   19994877 :       bi->bits >>= start_bit % BITMAP_WORD_BITS;
     621                 :            :     }
     622                 :            :   else
     623                 :            :     {
     624                 :            :       /* Otherwise we must immediately advance elt1, so initialize for
     625                 :            :          that.  */
     626                 :     548455 :       bi->word_no = BITMAP_ELEMENT_WORDS - 1;
     627                 :     548455 :       bi->bits = 0;
     628                 :            :     }
     629                 :            : 
     630                 :            :   /* If this word is zero, we must make sure we're not pointing at the
     631                 :            :      first bit, otherwise our incrementing to the next word boundary
     632                 :            :      will fail.  It won't matter if this increment moves us into the
     633                 :            :      next word.  */
     634                 :   20543277 :   start_bit += !bi->bits;
     635                 :            : 
     636                 :   20543277 :   *bit_no = start_bit;
     637                 :   20543277 : }
     638                 :            : 
     639                 :            : /* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2.  */
     640                 :            : 
     641                 :            : static inline void
     642                 :   71062714 : bmp_iter_and_compl_init (bitmap_iterator *bi,
     643                 :            :                          const_bitmap map1, const_bitmap map2,
     644                 :            :                          unsigned start_bit, unsigned *bit_no)
     645                 :            : {
     646                 :   71062714 :   bi->elt1 = map1->first;
     647                 :   71062714 :   bi->elt2 = map2->first;
     648                 :            : 
     649                 :   71062714 :   gcc_checking_assert (!map1->tree_form && !map2->tree_form);
     650                 :            : 
     651                 :            :   /* Advance elt1 until it is not before the block containing start_bit.  */
     652                 :   71062714 :   while (1)
     653                 :            :     {
     654                 :   71062714 :       if (!bi->elt1)
     655                 :            :         {
     656                 :   20528589 :           bi->elt1 = &bitmap_zero_bits;
     657                 :   20528589 :           break;
     658                 :            :         }
     659                 :            : 
     660                 :   50534127 :       if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
     661                 :            :         break;
     662                 :          0 :       bi->elt1 = bi->elt1->next;
     663                 :            :     }
     664                 :            : 
     665                 :            :   /* Advance elt2 until it is not before elt1.  */
     666                 :   78929547 :   while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
     667                 :    7866777 :     bi->elt2 = bi->elt2->next;
     668                 :            : 
     669                 :            :   /* We might have advanced beyond the start_bit, so reinitialize for
     670                 :            :      that.  */
     671                 :   71062714 :   if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
     672                 :    8221632 :     start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
     673                 :            : 
     674                 :   71062714 :   bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
     675                 :   71062714 :   bi->bits = bi->elt1->bits[bi->word_no];
     676                 :   71062714 :   if (bi->elt2 && bi->elt1->indx == bi->elt2->indx)
     677                 :   51355229 :     bi->bits &= ~bi->elt2->bits[bi->word_no];
     678                 :   71062714 :   bi->bits >>= start_bit % BITMAP_WORD_BITS;
     679                 :            : 
     680                 :            :   /* If this word is zero, we must make sure we're not pointing at the
     681                 :            :      first bit, otherwise our incrementing to the next word boundary
     682                 :            :      will fail.  It won't matter if this increment moves us into the
     683                 :            :      next word.  */
     684                 :   71062714 :   start_bit += !bi->bits;
     685                 :            : 
     686                 :   71062714 :   *bit_no = start_bit;
     687                 :   71062714 : }
     688                 :            : 
     689                 :            : /* Advance to the next bit in BI.  We don't advance to the next
     690                 :            :    nonzero bit yet.  */
     691                 :            : 
     692                 :            : static inline void
     693                 : 9352214520 : bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no)
     694                 :            : {
     695                 : 9352214520 :   bi->bits >>= 1;
     696                 : 9352214520 :   *bit_no += 1;
     697                 : 9352214520 : }
     698                 :            : 
     699                 :            : /* Advance to first set bit in BI.  */
     700                 :            : 
     701                 :            : static inline void
     702                 : 9709531075 : bmp_iter_next_bit (bitmap_iterator * bi, unsigned *bit_no)
     703                 :            : {
     704                 :            : #if (GCC_VERSION >= 3004)
     705                 : 9709531075 :   {
     706                 : 9709531075 :     unsigned int n = __builtin_ctzl (bi->bits);
     707                 : 9709531075 :     gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD));
     708                 : 9709531075 :     bi->bits >>= n;
     709                 : 9709531075 :     *bit_no += n;
     710                 :            :   }
     711                 :            : #else
     712                 :            :   while (!(bi->bits & 1))
     713                 :            :     {
     714                 :            :       bi->bits >>= 1;
     715                 :            :       *bit_no += 1;
     716                 :            :     }
     717                 :            : #endif
     718                 :            : }
     719                 :            : 
     720                 :            : /* Advance to the next nonzero bit of a single bitmap, we will have
     721                 :            :    already advanced past the just iterated bit.  Return true if there
     722                 :            :    is a bit to iterate.  */
     723                 :            : 
     724                 :            : static inline bool
     725                 :11413086294 : bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no)
     726                 :            : {
     727                 :            :   /* If our current word is nonzero, it contains the bit we want.  */
     728                 :11413086294 :   if (bi->bits)
     729                 :            :     {
     730                 : 8788902684 :     next_bit:
     731                 : 9586733480 :       bmp_iter_next_bit (bi, bit_no);
     732                 : 9586733480 :       return true;
     733                 :            :     }
     734                 :            : 
     735                 :            :   /* Round up to the word boundary.  We might have just iterated past
     736                 :            :      the end of the last word, hence the -1.  It is not possible for
     737                 :            :      bit_no to point at the beginning of the now last word.  */
     738                 : 2624172914 :   *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
     739                 : 2624172914 :              / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
     740                 : 2624172914 :   bi->word_no++;
     741                 :            : 
     742                 : 5300635066 :   while (1)
     743                 :            :     {
     744                 :            :       /* Find the next nonzero word in this elt.  */
     745                 : 4878381927 :       while (bi->word_no != BITMAP_ELEMENT_WORDS)
     746                 :            :         {
     747                 : 2629777039 :           bi->bits = bi->elt1->bits[bi->word_no];
     748                 : 2629777039 :           if (bi->bits)
     749                 :  797821137 :             goto next_bit;
     750                 : 1831957051 :           *bit_no += BITMAP_WORD_BITS;
     751                 : 1831957051 :           bi->word_no++;
     752                 :            :         }
     753                 :            : 
     754                 :            :       /* Make sure we didn't remove the element while iterating.  */
     755                 : 2248605040 :       gcc_checking_assert (bi->elt1->indx != -1U);
     756                 :            : 
     757                 :            :       /* Advance to the next element.  */
     758                 : 2248605040 :       bi->elt1 = bi->elt1->next;
     759                 : 2248605040 :       if (!bi->elt1)
     760                 :            :         return false;
     761                 :  422252719 :       *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
     762                 :  422252719 :       bi->word_no = 0;
     763                 :            :     }
     764                 :            : }
     765                 :            : 
     766                 :            : /* Advance to the next nonzero bit of an intersecting pair of
     767                 :            :    bitmaps.  We will have already advanced past the just iterated bit.
     768                 :            :    Return true if there is a bit to iterate.  */
     769                 :            : 
     770                 :            : static inline bool
     771                 :   22348485 : bmp_iter_and (bitmap_iterator *bi, unsigned *bit_no)
     772                 :            : {
     773                 :            :   /* If our current word is nonzero, it contains the bit we want.  */
     774                 :   22348485 :   if (bi->bits)
     775                 :            :     {
     776                 :   12033585 :     next_bit:
     777                 :   18545219 :       bmp_iter_next_bit (bi, bit_no);
     778                 :   18545219 :       return true;
     779                 :            :     }
     780                 :            : 
     781                 :            :   /* Round up to the word boundary.  We might have just iterated past
     782                 :            :      the end of the last word, hence the -1.  It is not possible for
     783                 :            :      bit_no to point at the beginning of the now last word.  */
     784                 :   10314945 :   *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
     785                 :   10314945 :              / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
     786                 :   10314945 :   bi->word_no++;
     787                 :            : 
     788                 :   14890478 :   while (1)
     789                 :            :     {
     790                 :            :       /* Find the next nonzero word in this elt.  */
     791                 :   13902414 :       while (bi->word_no != BITMAP_ELEMENT_WORDS)
     792                 :            :         {
     793                 :    9111007 :           bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
     794                 :    9111007 :           if (bi->bits)
     795                 :    6511644 :             goto next_bit;
     796                 :    2599373 :           *bit_no += BITMAP_WORD_BITS;
     797                 :    2599373 :           bi->word_no++;
     798                 :            :         }
     799                 :            : 
     800                 :            :       /* Advance to the next identical element.  */
     801                 :    4848227 :       do
     802                 :            :         {
     803                 :            :           /* Make sure we didn't remove the element while iterating.  */
     804                 :    4848227 :           gcc_checking_assert (bi->elt1->indx != -1U);
     805                 :            : 
     806                 :            :           /* Advance elt1 while it is less than elt2.  We always want
     807                 :            :              to advance one elt.  */
     808                 :    4895617 :           do
     809                 :            :             {
     810                 :    4895617 :               bi->elt1 = bi->elt1->next;
     811                 :    4895617 :               if (!bi->elt1)
     812                 :            :                 return false;
     813                 :            :             }
     814                 :    1103305 :           while (bi->elt1->indx < bi->elt2->indx);
     815                 :            : 
     816                 :            :           /* Make sure we didn't remove the element while iterating.  */
     817                 :    1055910 :           gcc_checking_assert (bi->elt2->indx != -1U);
     818                 :            : 
     819                 :            :           /* Advance elt2 to be no less than elt1.  This might not
     820                 :            :              advance.  */
     821                 :    2269952 :           while (bi->elt2->indx < bi->elt1->indx)
     822                 :            :             {
     823                 :    1225031 :               bi->elt2 = bi->elt2->next;
     824                 :    1225031 :               if (!bi->elt2)
     825                 :            :                 return false;
     826                 :            :             }
     827                 :            :         }
     828                 :    1044924 :       while (bi->elt1->indx != bi->elt2->indx);
     829                 :            : 
     830                 :     988062 :       *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
     831                 :     988062 :       bi->word_no = 0;
     832                 :            :     }
     833                 :            : }
     834                 :            : 
     835                 :            : /* Advance to the next nonzero bit in the intersection of
     836                 :            :    complemented bitmaps.  We will have already advanced past the just
     837                 :            :    iterated bit.  */
     838                 :            : 
     839                 :            : static inline bool
     840                 :  175311368 : bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no)
     841                 :            : {
     842                 :            :   /* If our current word is nonzero, it contains the bit we want.  */
     843                 :  175311368 :   if (bi->bits)
     844                 :            :     {
     845                 :   94085542 :     next_bit:
     846                 :  104252632 :       bmp_iter_next_bit (bi, bit_no);
     847                 :  104252632 :       return true;
     848                 :            :     }
     849                 :            : 
     850                 :            :   /* Round up to the word boundary.  We might have just iterated past
     851                 :            :      the end of the last word, hence the -1.  It is not possible for
     852                 :            :      bit_no to point at the beginning of the now last word.  */
     853                 :   81225839 :   *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
     854                 :   81225839 :              / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
     855                 :   81225839 :   bi->word_no++;
     856                 :            : 
     857                 :  160663982 :   while (1)
     858                 :            :     {
     859                 :            :       /* Find the next nonzero word in this elt.  */
     860                 :  156027572 :       while (bi->word_no != BITMAP_ELEMENT_WORDS)
     861                 :            :         {
     862                 :   80332212 :           bi->bits = bi->elt1->bits[bi->word_no];
     863                 :   80332212 :           if (bi->elt2 && bi->elt2->indx == bi->elt1->indx)
     864                 :   59130727 :             bi->bits &= ~bi->elt2->bits[bi->word_no];
     865                 :   80332212 :           if (bi->bits)
     866                 :   10167137 :             goto next_bit;
     867                 :   70165035 :           *bit_no += BITMAP_WORD_BITS;
     868                 :   70165035 :           bi->word_no++;
     869                 :            :         }
     870                 :            : 
     871                 :            :       /* Make sure we didn't remove the element while iterating.  */
     872                 :   75695492 :       gcc_checking_assert (bi->elt1->indx != -1U);
     873                 :            : 
     874                 :            :       /* Advance to the next element of elt1.  */
     875                 :   75695492 :       bi->elt1 = bi->elt1->next;
     876                 :   75695492 :       if (!bi->elt1)
     877                 :            :         return false;
     878                 :            : 
     879                 :            :       /* Make sure we didn't remove the element while iterating.  */
     880                 :    4636743 :       gcc_checking_assert (! bi->elt2 || bi->elt2->indx != -1U);
     881                 :            : 
     882                 :            :       /* Advance elt2 until it is no less than elt1.  */
     883                 :    9188103 :       while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
     884                 :    4551360 :         bi->elt2 = bi->elt2->next;
     885                 :            : 
     886                 :    4636743 :       *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
     887                 :    4636743 :       bi->word_no = 0;
     888                 :            :     }
     889                 :            : }
     890                 :            : 
     891                 :            : /* If you are modifying a bitmap you are currently iterating over you
     892                 :            :    have to ensure to
     893                 :            :      - never remove the current bit;
     894                 :            :      - if you set or clear a bit before the current bit this operation
     895                 :            :        will not affect the set of bits you are visiting during the iteration;
     896                 :            :      - if you set or clear a bit after the current bit it is unspecified
     897                 :            :        whether that affects the set of bits you are visiting during the
     898                 :            :        iteration.
     899                 :            :    If you want to remove the current bit you can delay this to the next
     900                 :            :    iteration (and after the iteration in case the last iteration is
     901                 :            :    affected).  */
     902                 :            : 
     903                 :            : /* Loop over all bits set in BITMAP, starting with MIN and setting
     904                 :            :    BITNUM to the bit number.  ITER is a bitmap iterator.  BITNUM
     905                 :            :    should be treated as a read-only variable as it contains loop
     906                 :            :    state.  */
     907                 :            : 
     908                 :            : #ifndef EXECUTE_IF_SET_IN_BITMAP
     909                 :            : /* See sbitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP.  */
     910                 :            : #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER)             \
     911                 :            :   for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM));         \
     912                 :            :        bmp_iter_set (&(ITER), &(BITNUM));                               \
     913                 :            :        bmp_iter_next (&(ITER), &(BITNUM)))
     914                 :            : #endif
     915                 :            : 
     916                 :            : /* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN
     917                 :            :    and setting BITNUM to the bit number.  ITER is a bitmap iterator.
     918                 :            :    BITNUM should be treated as a read-only variable as it contains
     919                 :            :    loop state.  */
     920                 :            : 
     921                 :            : #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER)   \
     922                 :            :   for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN),             \
     923                 :            :                           &(BITNUM));                                       \
     924                 :            :        bmp_iter_and (&(ITER), &(BITNUM));                               \
     925                 :            :        bmp_iter_next (&(ITER), &(BITNUM)))
     926                 :            : 
     927                 :            : /* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN
     928                 :            :    and setting BITNUM to the bit number.  ITER is a bitmap iterator.
     929                 :            :    BITNUM should be treated as a read-only variable as it contains
     930                 :            :    loop state.  */
     931                 :            : 
     932                 :            : #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
     933                 :            :   for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN),       \
     934                 :            :                                 &(BITNUM));                         \
     935                 :            :        bmp_iter_and_compl (&(ITER), &(BITNUM));                         \
     936                 :            :        bmp_iter_next (&(ITER), &(BITNUM)))
     937                 :            : 
     938                 :            : /* A class that ties the lifetime of a bitmap to its scope.  */
     939                 :            : class auto_bitmap
     940                 :            : {
     941                 :            :  public:
     942                 :  239180055 :   auto_bitmap () { bitmap_initialize (&m_bits, &bitmap_default_obstack); }
     943                 :   91025975 :   explicit auto_bitmap (bitmap_obstack *o) { bitmap_initialize (&m_bits, o); }
     944                 :  332804266 :   ~auto_bitmap () { bitmap_clear (&m_bits); }
     945                 :            :   // Allow calling bitmap functions on our bitmap.
     946                 :11877183680 :   operator bitmap () { return &m_bits; }
     947                 :            : 
     948                 :            :  private:
     949                 :            :   // Prevent making a copy that references our bitmap.
     950                 :            :   auto_bitmap (const auto_bitmap &);
     951                 :            :   auto_bitmap &operator = (const auto_bitmap &);
     952                 :            : #if __cplusplus >= 201103L
     953                 :            :   auto_bitmap (auto_bitmap &&);
     954                 :            :   auto_bitmap &operator = (auto_bitmap &&);
     955                 :            : #endif
     956                 :            : 
     957                 :            :   bitmap_head m_bits;
     958                 :            : };
     959                 :            : 
     960                 :            : /* Base class for bitmap_view; see there for details.  */
     961                 :            : template<typename T, typename Traits = array_traits<T> >
     962                 :            : class base_bitmap_view
     963                 :            : {
     964                 :            : public:
     965                 :            :   typedef typename Traits::element_type array_element_type;
     966                 :            : 
     967                 :            :   base_bitmap_view (const T &, bitmap_element *);
     968                 :   98354884 :   operator const_bitmap () const { return &m_head; }
     969                 :            : 
     970                 :            : private:
     971                 :            :   base_bitmap_view (const base_bitmap_view &);
     972                 :            : 
     973                 :            :   bitmap_head m_head;
     974                 :            : };
     975                 :            : 
     976                 :            : /* Provides a read-only bitmap view of a single integer bitmask or a
     977                 :            :    constant-sized array of integer bitmasks, or of a wrapper around such
     978                 :            :    bitmasks.  */
     979                 :            : template<typename T, typename Traits>
     980                 :            : class bitmap_view<T, Traits, true> : public base_bitmap_view<T, Traits>
     981                 :            : {
     982                 :            : public:
     983                 :   98354884 :   bitmap_view (const T &array)
     984                 :   98354884 :     : base_bitmap_view<T, Traits> (array, m_bitmap_elements) {}
     985                 :            : 
     986                 :            : private:
     987                 :            :   /* How many bitmap_elements we need to hold a full T.  */
     988                 :            :   static const size_t num_bitmap_elements
     989                 :            :     = CEIL (CHAR_BIT
     990                 :            :             * sizeof (typename Traits::element_type)
     991                 :            :             * Traits::constant_size,
     992                 :            :             BITMAP_ELEMENT_ALL_BITS);
     993                 :            :   bitmap_element m_bitmap_elements[num_bitmap_elements];
     994                 :            : };
     995                 :            : 
     996                 :            : /* Initialize the view for array ARRAY, using the array of bitmap
     997                 :            :    elements in BITMAP_ELEMENTS (which is known to contain enough
     998                 :            :    entries).  */
     999                 :            : template<typename T, typename Traits>
    1000                 :   98354900 : base_bitmap_view<T, Traits>::base_bitmap_view (const T &array,
    1001                 :   98354900 :                                                bitmap_element *bitmap_elements)
    1002                 :            : {
    1003                 :   98354900 :   m_head.obstack = NULL;
    1004                 :            : 
    1005                 :            :   /* The code currently assumes that each element of ARRAY corresponds
    1006                 :            :      to exactly one bitmap_element.  */
    1007                 :   98354900 :   const size_t array_element_bits = CHAR_BIT * sizeof (array_element_type);
    1008                 :            :   STATIC_ASSERT (BITMAP_ELEMENT_ALL_BITS % array_element_bits == 0);
    1009                 :   98354900 :   size_t array_step = BITMAP_ELEMENT_ALL_BITS / array_element_bits;
    1010                 :   98354900 :   size_t array_size = Traits::size (array);
    1011                 :            : 
    1012                 :            :   /* Process each potential bitmap_element in turn.  The loop is written
    1013                 :            :      this way rather than per array element because usually there are
    1014                 :            :      only a small number of array elements per bitmap element (typically
    1015                 :            :      two or four).  The inner loops should therefore unroll completely.  */
    1016                 :   98354900 :   const array_element_type *array_elements = Traits::base (array);
    1017                 :   98354900 :   unsigned int indx = 0;
    1018                 :  196710000 :   for (size_t array_base = 0;
    1019                 :  196710000 :        array_base < array_size;
    1020                 :            :        array_base += array_step, indx += 1)
    1021                 :            :     {
    1022                 :            :       /* How many array elements are in this particular bitmap_element.  */
    1023                 :   98354900 :       unsigned int array_count
    1024                 :            :         = (STATIC_CONSTANT_P (array_size % array_step == 0)
    1025                 :   98354900 :            ? array_step : MIN (array_step, array_size - array_base));
    1026                 :            : 
    1027                 :            :       /* See whether we need this bitmap element.  */
    1028                 :   98354900 :       array_element_type ior = array_elements[array_base];
    1029                 :  196710000 :       for (size_t i = 1; i < array_count; ++i)
    1030                 :   98354900 :         ior |= array_elements[array_base + i];
    1031                 :   98354900 :       if (ior == 0)
    1032                 :   63704000 :         continue;
    1033                 :            : 
    1034                 :            :       /* Grab the next bitmap element and chain it.  */
    1035                 :   34650900 :       bitmap_element *bitmap_element = bitmap_elements++;
    1036                 :   34650900 :       if (m_head.current)
    1037                 :          0 :         m_head.current->next = bitmap_element;
    1038                 :            :       else
    1039                 :   34650900 :         m_head.first = bitmap_element;
    1040                 :   34650900 :       bitmap_element->prev = m_head.current;
    1041                 :   34650900 :       bitmap_element->next = NULL;
    1042                 :   34650900 :       bitmap_element->indx = indx;
    1043                 :   34650900 :       m_head.current = bitmap_element;
    1044                 :   34650900 :       m_head.indx = indx;
    1045                 :            : 
    1046                 :            :       /* Fill in the bits of the bitmap element.  */
    1047                 :            :       if (array_element_bits < BITMAP_WORD_BITS)
    1048                 :            :         {
    1049                 :            :           /* Multiple array elements fit in one element of
    1050                 :            :              bitmap_element->bits.  */
    1051                 :            :           size_t array_i = array_base;
    1052                 :            :           for (unsigned int word_i = 0; word_i < BITMAP_ELEMENT_WORDS;
    1053                 :            :                ++word_i)
    1054                 :            :             {
    1055                 :            :               BITMAP_WORD word = 0;
    1056                 :            :               for (unsigned int shift = 0;
    1057                 :            :                    shift < BITMAP_WORD_BITS && array_i < array_size;
    1058                 :            :                    shift += array_element_bits)
    1059                 :            :                 word |= array_elements[array_i++] << shift;
    1060                 :            :               bitmap_element->bits[word_i] = word;
    1061                 :            :             }
    1062                 :            :         }
    1063                 :            :       else
    1064                 :            :         {
    1065                 :            :           /* Array elements are the same size as elements of
    1066                 :            :              bitmap_element->bits, or are an exact multiple of that size.  */
    1067                 :   34650900 :           unsigned int word_i = 0;
    1068                 :  103953000 :           for (unsigned int i = 0; i < array_count; ++i)
    1069                 :  138604000 :             for (unsigned int shift = 0; shift < array_element_bits;
    1070                 :            :                  shift += BITMAP_WORD_BITS)
    1071                 :   69301800 :               bitmap_element->bits[word_i++]
    1072                 :   69301800 :                 = array_elements[array_base + i] >> shift;
    1073                 :   34650900 :           while (word_i < BITMAP_ELEMENT_WORDS)
    1074                 :          0 :             bitmap_element->bits[word_i++] = 0;
    1075                 :            :         }
    1076                 :            :     }
    1077                 :   98354900 : }
    1078                 :            : 
    1079                 :            : #endif /* GCC_BITMAP_H */

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.