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

           Branch data     Line data    Source code
       1                 :            : /* Simple bitmaps.
       2                 :            :    Copyright (C) 1999-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_SBITMAP_H
      21                 :            : #define GCC_SBITMAP_H
      22                 :            : 
      23                 :            : /* Implementation of sets using simple bitmap vectors.
      24                 :            : 
      25                 :            :    This set representation is suitable for non-sparse sets with a known
      26                 :            :    (a priori) universe.  The set is represented as a simple array of the
      27                 :            :    host's fastest unsigned integer.  For a given member I in the set:
      28                 :            :      - the element for I will be at sbitmap[I / (bits per element)]
      29                 :            :      - the position for I within element is I % (bits per element)
      30                 :            : 
      31                 :            :    This representation is very space-efficient for large non-sparse sets
      32                 :            :    with random access patterns.
      33                 :            : 
      34                 :            :    The following operations can be performed in O(1) time:
      35                 :            : 
      36                 :            :      * set_size                 : SBITMAP_SIZE
      37                 :            :      * member_p                 : bitmap_bit_p
      38                 :            :      * add_member               : bitmap_set_bit
      39                 :            :      * remove_member            : bitmap_clear_bit
      40                 :            : 
      41                 :            :    Most other operations on this set representation are O(U) where U is
      42                 :            :    the size of the set universe:
      43                 :            : 
      44                 :            :      * clear                    : bitmap_clear
      45                 :            :      * choose_one               : bitmap_first_set_bit /
      46                 :            :                                   bitmap_last_set_bit
      47                 :            :      * forall                   : EXECUTE_IF_SET_IN_BITMAP
      48                 :            :      * set_copy                 : bitmap_copy
      49                 :            :      * set_intersection         : bitmap_and
      50                 :            :      * set_union                : bitmap_ior
      51                 :            :      * set_difference           : bitmap_and_compl
      52                 :            :      * set_disjuction           : (not implemented)
      53                 :            :      * set_compare              : bitmap_equal_p
      54                 :            :      * bit_in_range_p           : bitmap_bit_in_range_p
      55                 :            : 
      56                 :            :    Some operations on 3 sets that occur frequently in data flow problems
      57                 :            :    are also implemented:
      58                 :            : 
      59                 :            :       * A | (B & C)         : bitmap_or_and
      60                 :            :       * A | (B & ~C)                : bitmap_ior_and_compl
      61                 :            :       * A & (B | C)         : bitmap_and_or
      62                 :            : 
      63                 :            :    Most of the set functions have two variants: One that returns non-zero
      64                 :            :    if members were added or removed from the target set, and one that just
      65                 :            :    performs the operation without feedback.  The former operations are a
      66                 :            :    bit more expensive but the result can often be used to avoid iterations
      67                 :            :    on other sets.
      68                 :            : 
      69                 :            :    Allocating a bitmap is done with sbitmap_alloc, and resizing is
      70                 :            :    performed with sbitmap_resize.
      71                 :            : 
      72                 :            :    The storage requirements for simple bitmap sets is O(U) where U is the
      73                 :            :    size of the set universe (colloquially the number of bits in the bitmap).
      74                 :            : 
      75                 :            :    This set representation works well for relatively small data flow problems
      76                 :            :    (there are special routines for that, see sbitmap_vector_*).  The set
      77                 :            :    operations can be vectorized and there is almost no computating overhead,
      78                 :            :    so that even sparse simple bitmap sets outperform dedicated sparse set
      79                 :            :    representations like linked-list bitmaps.  For larger problems, the size
      80                 :            :    overhead of simple bitmap sets gets too high and other set representations
      81                 :            :    have to be used.  */
      82                 :            : 
      83                 :            : #define SBITMAP_ELT_BITS (HOST_BITS_PER_WIDEST_FAST_INT * 1u)
      84                 :            : #define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
      85                 :            : 
      86                 :            : struct simple_bitmap_def
      87                 :            : {
      88                 :            :   unsigned int n_bits;          /* Number of bits.  */
      89                 :            :   unsigned int size;            /* Size in elements.  */
      90                 :            :   SBITMAP_ELT_TYPE elms[1];     /* The elements.  */
      91                 :            : };
      92                 :            : 
      93                 :            : /* Return the set size needed for N elements.  */
      94                 :            : #define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS)
      95                 :            : 
      96                 :            : /* Return the number of bits in BITMAP.  */
      97                 :            : #define SBITMAP_SIZE(BITMAP) ((BITMAP)->n_bits)
      98                 :            : 
      99                 :            : /* Verify that access at INDEX in bitmap MAP is valid.  */ 
     100                 :            : 
     101                 :            : static inline void
     102                 :            : bitmap_check_index (const_sbitmap map, int index)
     103                 :            : {
     104                 :            :   gcc_checking_assert (index >= 0);
     105                 :            :   gcc_checking_assert ((unsigned int)index < map->n_bits);
     106                 :            : }
     107                 :            : 
     108                 :            : /* Verify that bitmaps A and B have same size.  */ 
     109                 :            : 
     110                 :            : static inline void
     111                 :  274710000 : bitmap_check_sizes (const_sbitmap a, const_sbitmap b)
     112                 :            : {
     113                 :  136695000 :   gcc_checking_assert (a->n_bits == b->n_bits);
     114                 :            : }
     115                 :            : 
     116                 :            : /* Test if bit number bitno in the bitmap is set.  */
     117                 :            : static inline SBITMAP_ELT_TYPE
     118                 :11447477910 : bitmap_bit_p (const_sbitmap map, int bitno)
     119                 :            : {
     120                 : 8180204912 :   bitmap_check_index (map, bitno);
     121                 :            : 
     122                 :11447477910 :   size_t i = bitno / SBITMAP_ELT_BITS;
     123                 :11447477910 :   unsigned int s = bitno % SBITMAP_ELT_BITS;
     124                 :11292334917 :   return (map->elms[i] >> s) & (SBITMAP_ELT_TYPE) 1;
     125                 :            : }
     126                 :            : 
     127                 :            : /* Set bit number BITNO in the sbitmap MAP.  */
     128                 :            : 
     129                 :            : static inline void
     130                 : 6317627748 : bitmap_set_bit (sbitmap map, int bitno)
     131                 :            : {
     132                 : 5634057699 :   bitmap_check_index (map, bitno);
     133                 :            : 
     134                 : 6317627748 :   map->elms[bitno / SBITMAP_ELT_BITS]
     135                 : 4893653816 :     |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS;
     136                 : 1337770637 : }
     137                 :            : 
     138                 :            : /* Reset bit number BITNO in the sbitmap MAP.  */
     139                 :            : 
     140                 :            : static inline void
     141                 :  637113132 : bitmap_clear_bit (sbitmap map, int bitno)
     142                 :            : {
     143                 :  637113132 :   bitmap_check_index (map, bitno);
     144                 :            : 
     145                 :  637113132 :   map->elms[bitno / SBITMAP_ELT_BITS]
     146                 :  584965365 :     &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS);
     147                 :  258481835 : }
     148                 :            : 
     149                 :            : /* The iterator for sbitmap.  */
     150                 :            : struct sbitmap_iterator {
     151                 :            :   /* The pointer to the first word of the bitmap.  */
     152                 :            :   const SBITMAP_ELT_TYPE *ptr;
     153                 :            : 
     154                 :            :   /* The size of the bitmap.  */
     155                 :            :   unsigned int size;
     156                 :            : 
     157                 :            :   /* The current word index.  */
     158                 :            :   unsigned int word_num;
     159                 :            : 
     160                 :            :   /* The current bit index (not modulo SBITMAP_ELT_BITS).  */
     161                 :            :   unsigned int bit_num;
     162                 :            : 
     163                 :            :   /* The words currently visited.  */
     164                 :            :   SBITMAP_ELT_TYPE word;
     165                 :            : };
     166                 :            : 
     167                 :            : /* Initialize the iterator I with sbitmap BMP and the initial index
     168                 :            :    MIN.  */
     169                 :            : 
     170                 :            : static inline void
     171                 :   61809726 : bmp_iter_set_init (sbitmap_iterator *i, const_sbitmap bmp,
     172                 :            :                    unsigned int min, unsigned *bit_no ATTRIBUTE_UNUSED)
     173                 :            : {
     174                 :   61809726 :   i->word_num = min / (unsigned int) SBITMAP_ELT_BITS;
     175                 :   61809726 :   i->bit_num = min;
     176                 :   61809726 :   i->size = bmp->size;
     177                 :   61809726 :   i->ptr = bmp->elms;
     178                 :            : 
     179                 :   60928466 :   if (i->word_num >= i->size)
     180                 :          1 :     i->word = 0;
     181                 :            :   else
     182                 :   61809591 :     i->word = (i->ptr[i->word_num]
     183                 :        135 :                >> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS));
     184                 :            : }
     185                 :            : 
     186                 :            : /* Return true if we have more bits to visit, in which case *N is set
     187                 :            :    to the index of the bit to be visited.  Otherwise, return
     188                 :            :    false.  */
     189                 :            : 
     190                 :            : static inline bool
     191                 :  323725511 : bmp_iter_set (sbitmap_iterator *i, unsigned int *n)
     192                 :            : {
     193                 :            :   /* Skip words that are zeros.  */
     194                 :  372603281 :   for (; i->word == 0; i->word = i->ptr[i->word_num])
     195                 :            :     {
     196                 :  107465947 :       i->word_num++;
     197                 :            : 
     198                 :            :       /* If we have reached the end, break.  */
     199                 :  107465947 :       if (i->word_num >= i->size)
     200                 :            :         return false;
     201                 :            : 
     202                 :   48877180 :       i->bit_num = i->word_num * SBITMAP_ELT_BITS;
     203                 :            :     }
     204                 :            : 
     205                 :            :   /* Skip bits that are zero.  */
     206                 :  675231128 :   for (; (i->word & 1) == 0; i->word >>= 1)
     207                 :  410094470 :     i->bit_num++;
     208                 :            : 
     209                 :  265137094 :   *n = i->bit_num;
     210                 :            : 
     211                 :  265137094 :   return true;
     212                 :            : }
     213                 :            : 
     214                 :            : /* Advance to the next bit.  */
     215                 :            : 
     216                 :            : static inline void
     217                 :  261916064 : bmp_iter_next (sbitmap_iterator *i, unsigned *bit_no ATTRIBUTE_UNUSED)
     218                 :            : {
     219                 :  261916064 :   i->word >>= 1;
     220                 :  261916064 :   i->bit_num++;
     221                 :  261916064 : }
     222                 :            : 
     223                 :            : /* Loop over all elements of SBITMAP, starting with MIN.  In each
     224                 :            :    iteration, N is set to the index of the bit being visited.  ITER is
     225                 :            :    an instance of sbitmap_iterator used to iterate the bitmap.  */
     226                 :            : 
     227                 :            : #ifndef EXECUTE_IF_SET_IN_BITMAP
     228                 :            : /* See bitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP.  */
     229                 :            : #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER)     \
     230                 :            :   for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \
     231                 :            :        bmp_iter_set (&(ITER), &(BITNUM));                       \
     232                 :            :        bmp_iter_next (&(ITER), &(BITNUM)))
     233                 :            : #endif
     234                 :            : 
     235                 :  568271902 : inline void sbitmap_free (sbitmap map)
     236                 :            : {
     237                 :  551146373 :   free (map);
     238                 :    1779918 : }
     239                 :            : 
     240                 :    3880914 : inline void sbitmap_vector_free (sbitmap * vec)
     241                 :            : {
     242                 :    2363341 :   free (vec);
     243                 :     609911 : }
     244                 :            : 
     245                 :            : extern void dump_bitmap (FILE *, const_sbitmap);
     246                 :            : extern void debug_raw (const simple_bitmap_def &ref);
     247                 :            : extern void debug_raw (const simple_bitmap_def *ptr);
     248                 :            : extern void dump_bitmap_file (FILE *, const_sbitmap);
     249                 :            : extern void debug (const simple_bitmap_def &ref);
     250                 :            : extern void debug (const simple_bitmap_def *ptr);
     251                 :            : extern void dump_bitmap_vector (FILE *, const char *, const char *, sbitmap *,
     252                 :            :                                  int);
     253                 :            : extern sbitmap sbitmap_alloc (unsigned int);
     254                 :            : extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int);
     255                 :            : extern sbitmap sbitmap_resize (sbitmap, unsigned int, int);
     256                 :            : extern void bitmap_copy (sbitmap, const_sbitmap);
     257                 :            : extern int bitmap_equal_p (const_sbitmap, const_sbitmap);
     258                 :            : extern unsigned int bitmap_count_bits (const_sbitmap);
     259                 :            : extern bool bitmap_empty_p (const_sbitmap);
     260                 :            : extern void bitmap_clear (sbitmap);
     261                 :            : extern void bitmap_clear_range (sbitmap, unsigned, unsigned);
     262                 :            : extern void bitmap_set_range (sbitmap, unsigned, unsigned);
     263                 :            : extern void bitmap_ones (sbitmap);
     264                 :            : extern void bitmap_vector_clear (sbitmap *, unsigned int);
     265                 :            : extern void bitmap_vector_ones (sbitmap *, unsigned int);
     266                 :            : 
     267                 :            : extern bool bitmap_ior_and_compl (sbitmap, const_sbitmap,
     268                 :            :                                       const_sbitmap, const_sbitmap);
     269                 :            : extern void bitmap_and_compl (sbitmap, const_sbitmap, const_sbitmap);
     270                 :            : extern void bitmap_not (sbitmap, const_sbitmap);
     271                 :            : extern bool bitmap_or_and (sbitmap, const_sbitmap,
     272                 :            :                                      const_sbitmap, const_sbitmap);
     273                 :            : extern bool bitmap_and_or (sbitmap, const_sbitmap,
     274                 :            :                                      const_sbitmap, const_sbitmap);
     275                 :            : extern bool bitmap_intersect_p (const_sbitmap, const_sbitmap);
     276                 :            : extern bool bitmap_and (sbitmap, const_sbitmap, const_sbitmap);
     277                 :            : extern bool bitmap_ior (sbitmap, const_sbitmap, const_sbitmap);
     278                 :            : extern bool bitmap_xor (sbitmap, const_sbitmap, const_sbitmap);
     279                 :            : extern bool bitmap_subset_p (const_sbitmap, const_sbitmap);
     280                 :            : extern bool bitmap_bit_in_range_p (const_sbitmap, unsigned int, unsigned int);
     281                 :            : 
     282                 :            : extern int bitmap_first_set_bit (const_sbitmap);
     283                 :            : extern int bitmap_last_set_bit (const_sbitmap);
     284                 :            : 
     285                 :            : extern void debug_bitmap (const_sbitmap);
     286                 :            : extern sbitmap sbitmap_realloc (sbitmap, unsigned int);
     287                 :            : 
     288                 :            : /* a class that ties the lifetime of a sbitmap to its scope.  */
     289                 :            : class auto_sbitmap
     290                 :            : {
     291                 :            : public:
     292                 :  497575417 :   explicit auto_sbitmap (unsigned int size) :
     293                 :  499520102 :     m_bitmap (sbitmap_alloc (size)) {}
     294                 :  270680191 :   ~auto_sbitmap () { sbitmap_free (m_bitmap); }
     295                 :            : 
     296                 :            :   /* Allow calling sbitmap functions on our bitmap.  */
     297                 : 8489109335 :   operator sbitmap () { return m_bitmap; }
     298                 :      72486 :   operator const_sbitmap () const { return m_bitmap; }
     299                 :            : 
     300                 :            : private:
     301                 :            :   /* Prevent making a copy that refers to our sbitmap.  */
     302                 :            :   auto_sbitmap (const auto_sbitmap &);
     303                 :            :   auto_sbitmap &operator = (const auto_sbitmap &);
     304                 :            : #if __cplusplus >= 201103L
     305                 :            :   auto_sbitmap (auto_sbitmap &&);
     306                 :            :   auto_sbitmap &operator = (auto_sbitmap &&);
     307                 :            : #endif
     308                 :            : 
     309                 :            :   /* The bitmap we are managing.  */
     310                 :            :   sbitmap m_bitmap;
     311                 :            : };
     312                 :            : 
     313                 :            : #endif /* ! GCC_SBITMAP_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.