LCOV - code coverage report
Current view: top level - gcc - bitmap.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 86.4 % 1390 1201
Test Date: 2024-11-30 13:30:02 Functions: 80.3 % 76 61
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-2024 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                 :             : #include "config.h"
      21                 :             : #include "system.h"
      22                 :             : #include "coretypes.h"
      23                 :             : #include "bitmap.h"
      24                 :             : #include "selftest.h"
      25                 :             : 
      26                 :             : /* Memory allocation statistics purpose instance.  */
      27                 :             : mem_alloc_description<bitmap_usage> bitmap_mem_desc;
      28                 :             : 
      29                 :             : /* Static zero-initialized bitmap obstack used for default initialization
      30                 :             :    of bitmap_head.  */
      31                 :             : bitmap_obstack bitmap_head::crashme;
      32                 :             : 
      33                 :             : static bitmap_element *bitmap_tree_listify_from (bitmap, bitmap_element *);
      34                 :             : 
      35                 :             : /* Register new bitmap.  */
      36                 :             : void
      37                 :           0 : bitmap_register (bitmap b MEM_STAT_DECL)
      38                 :             : {
      39                 :           0 :   static unsigned alloc_descriptor_max_uid = 1;
      40                 :           0 :   gcc_assert (b->alloc_descriptor == 0);
      41                 :           0 :   b->alloc_descriptor = alloc_descriptor_max_uid++;
      42                 :             : 
      43                 :           0 :   bitmap_mem_desc.register_descriptor (b->get_descriptor (), BITMAP_ORIGIN,
      44                 :             :                                        false FINAL_PASS_MEM_STAT);
      45                 :           0 : }
      46                 :             : 
      47                 :             : /* Account the overhead.  */
      48                 :             : static void
      49                 :           0 : register_overhead (bitmap b, size_t amount)
      50                 :             : {
      51                 :           0 :   unsigned *d = b->get_descriptor ();
      52                 :           0 :   if (bitmap_mem_desc.contains_descriptor_for_instance (d))
      53                 :           0 :     bitmap_mem_desc.register_instance_overhead (amount, d);
      54                 :           0 : }
      55                 :             : 
      56                 :             : /* Release the overhead.  */
      57                 :             : static void
      58                 :           0 : release_overhead (bitmap b, size_t amount, bool remove_from_map)
      59                 :             : {
      60                 :           0 :   unsigned *d = b->get_descriptor ();
      61                 :           0 :   if (bitmap_mem_desc.contains_descriptor_for_instance (d))
      62                 :           0 :     bitmap_mem_desc.release_instance_overhead (d, amount, remove_from_map);
      63                 :           0 : }
      64                 :             : 
      65                 :             : 
      66                 :             : /* Global data */
      67                 :             : bitmap_element bitmap_zero_bits;  /* An element of all zero bits.  */
      68                 :             : bitmap_obstack bitmap_default_obstack;    /* The default bitmap obstack.  */
      69                 :             : static int bitmap_default_obstack_depth;
      70                 :             : static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of
      71                 :             :                                                             GC'd elements.  */
      72                 :             : 
      73                 :             : 
      74                 :             : /* Bitmap memory management.  */
      75                 :             : 
      76                 :             : /* Add ELT to the appropriate freelist.  */
      77                 :             : static inline void
      78                 :   879315922 : bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
      79                 :             : {
      80                 :   879315922 :   bitmap_obstack *bit_obstack = head->obstack;
      81                 :             : 
      82                 :   879315922 :   if (GATHER_STATISTICS)
      83                 :             :     release_overhead (head, sizeof (bitmap_element), false);
      84                 :             : 
      85                 :   879315922 :   elt->next = NULL;
      86                 :   879315922 :   elt->indx = -1;
      87                 :   879315922 :   if (bit_obstack)
      88                 :             :     {
      89                 :   876203169 :       elt->prev = bit_obstack->elements;
      90                 :   876203169 :       bit_obstack->elements = elt;
      91                 :             :     }
      92                 :             :   else
      93                 :             :     {
      94                 :     3112753 :       elt->prev = bitmap_ggc_free;
      95                 :     3112753 :       bitmap_ggc_free = elt;
      96                 :             :     }
      97                 :             : }
      98                 :             : 
      99                 :             : /* Allocate a bitmap element.  The bits are cleared, but nothing else is.  */
     100                 :             : 
     101                 :             : static inline bitmap_element *
     102                 : 13008833916 : bitmap_element_allocate (bitmap head)
     103                 :             : {
     104                 : 13008833916 :   bitmap_element *element;
     105                 : 13008833916 :   bitmap_obstack *bit_obstack = head->obstack;
     106                 :             : 
     107                 : 13008833916 :   if (bit_obstack)
     108                 :             :     {
     109                 : 12876206068 :       element = bit_obstack->elements;
     110                 :             : 
     111                 : 12876206068 :       if (element)
     112                 :             :         /* Use up the inner list first before looking at the next
     113                 :             :            element of the outer list.  */
     114                 :  9732098632 :         if (element->next)
     115                 :             :           {
     116                 :  2700587572 :             bit_obstack->elements = element->next;
     117                 :  2700587572 :             bit_obstack->elements->prev = element->prev;
     118                 :             :           }
     119                 :             :         else
     120                 :             :           /*  Inner list was just a singleton.  */
     121                 :  7031511060 :           bit_obstack->elements = element->prev;
     122                 :             :       else
     123                 :  3144107436 :         element = XOBNEW (&bit_obstack->obstack, bitmap_element);
     124                 :             :     }
     125                 :             :   else
     126                 :             :     {
     127                 :   132627848 :       element = bitmap_ggc_free;
     128                 :   132627848 :       if (element)
     129                 :             :         /* Use up the inner list first before looking at the next
     130                 :             :            element of the outer list.  */
     131                 :   109292199 :         if (element->next)
     132                 :             :           {
     133                 :    13389123 :             bitmap_ggc_free = element->next;
     134                 :    13389123 :             bitmap_ggc_free->prev = element->prev;
     135                 :             :           }
     136                 :             :         else
     137                 :             :           /*  Inner list was just a singleton.  */
     138                 :    95903076 :           bitmap_ggc_free = element->prev;
     139                 :             :       else
     140                 :    23335649 :         element = ggc_alloc<bitmap_element> ();
     141                 :             :     }
     142                 :             : 
     143                 : 13008833916 :   if (GATHER_STATISTICS)
     144                 :             :     register_overhead (head, sizeof (bitmap_element));
     145                 :             : 
     146                 : 13008833916 :   memset (element->bits, 0, sizeof (element->bits));
     147                 :             : 
     148                 : 13008833916 :   return element;
     149                 :             : }
     150                 :             : 
     151                 :             : /* Remove ELT and all following elements from bitmap HEAD.
     152                 :             :    Put the released elements in the freelist for HEAD.  */
     153                 :             : 
     154                 :             : void
     155                 :  6885134466 : bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
     156                 :             : {
     157                 :  6885134466 :   bitmap_element *prev;
     158                 :  6885134466 :   bitmap_obstack *bit_obstack = head->obstack;
     159                 :             : 
     160                 :  6885134466 :   if (!elt)
     161                 :             :     return;
     162                 :             : 
     163                 :  6550362032 :   if (head->tree_form)
     164                 :    48949482 :     elt = bitmap_tree_listify_from (head, elt);
     165                 :             : 
     166                 :  6550362032 :   if (GATHER_STATISTICS)
     167                 :             :     {
     168                 :             :       int n = 0;
     169                 :             :       for (prev = elt; prev; prev = prev->next)
     170                 :             :         n++;
     171                 :             :       release_overhead (head, sizeof (bitmap_element) * n, false);
     172                 :             :     }
     173                 :             : 
     174                 :  6550362032 :   prev = elt->prev;
     175                 :  6550362032 :   if (prev)
     176                 :             :     {
     177                 :   109950558 :       prev->next = NULL;
     178                 :   109950558 :       if (head->current->indx > prev->indx)
     179                 :             :         {
     180                 :      467459 :           head->current = prev;
     181                 :      467459 :           head->indx = prev->indx;
     182                 :             :         }
     183                 :             :     }
     184                 :             :   else
     185                 :             :     {
     186                 :  6440411474 :       head->first = NULL;
     187                 :  6440411474 :       head->current = NULL;
     188                 :  6440411474 :       head->indx = 0;
     189                 :             :     }
     190                 :             : 
     191                 :             :   /* Put the entire list onto the freelist in one operation. */
     192                 :  6550362032 :   if (bit_obstack)
     193                 :             :     {
     194                 :  6452724114 :       elt->prev = bit_obstack->elements;
     195                 :  6452724114 :       bit_obstack->elements = elt;
     196                 :             :     }
     197                 :             :   else
     198                 :             :     {
     199                 :    97637918 :       elt->prev = bitmap_ggc_free;
     200                 :    97637918 :       bitmap_ggc_free = elt;
     201                 :             :     }
     202                 :             : }
     203                 :             : 
     204                 :             : /* Linked-list view of bitmaps.
     205                 :             : 
     206                 :             :    In this representation, the bitmap elements form a double-linked list
     207                 :             :    with elements sorted by increasing index.  */
     208                 :             : 
     209                 :             : /* Link the bitmap element into the current bitmap linked list.  */
     210                 :             : 
     211                 :             : static inline void
     212                 :  7167737419 : bitmap_list_link_element (bitmap head, bitmap_element *element)
     213                 :             : {
     214                 :  7167737419 :   unsigned int indx = element->indx;
     215                 :  7167737419 :   bitmap_element *ptr;
     216                 :             : 
     217                 :  7167737419 :   gcc_checking_assert (!head->tree_form);
     218                 :             : 
     219                 :             :   /* If this is the first and only element, set it in.  */
     220                 :  7167737419 :   if (head->first == 0)
     221                 :             :     {
     222                 :  5767185825 :       element->next = element->prev = 0;
     223                 :  5767185825 :       head->first = element;
     224                 :             :     }
     225                 :             : 
     226                 :             :   /* If this index is less than that of the current element, it goes someplace
     227                 :             :      before the current element.  */
     228                 :  1400551594 :   else if (indx < head->indx)
     229                 :             :     {
     230                 :   478070637 :       for (ptr = head->current;
     231                 :   478070637 :            ptr->prev != 0 && ptr->prev->indx > indx;
     232                 :             :            ptr = ptr->prev)
     233                 :             :         ;
     234                 :             : 
     235                 :   478070637 :       if (ptr->prev)
     236                 :   121404520 :         ptr->prev->next = element;
     237                 :             :       else
     238                 :   356666117 :         head->first = element;
     239                 :             : 
     240                 :   478070637 :       element->prev = ptr->prev;
     241                 :   478070637 :       element->next = ptr;
     242                 :   478070637 :       ptr->prev = element;
     243                 :             :     }
     244                 :             : 
     245                 :             :   /* Otherwise, it must go someplace after the current element.  */
     246                 :             :   else
     247                 :             :     {
     248                 :   922480957 :       for (ptr = head->current;
     249                 :   922480957 :            ptr->next != 0 && ptr->next->indx < indx;
     250                 :             :            ptr = ptr->next)
     251                 :             :         ;
     252                 :             : 
     253                 :   922480957 :       if (ptr->next)
     254                 :    53603134 :         ptr->next->prev = element;
     255                 :             : 
     256                 :   922480957 :       element->next = ptr->next;
     257                 :   922480957 :       element->prev = ptr;
     258                 :   922480957 :       ptr->next = element;
     259                 :             :     }
     260                 :             : 
     261                 :             :   /* Set up so this is the first element searched.  */
     262                 :  7167737419 :   head->current = element;
     263                 :  7167737419 :   head->indx = indx;
     264                 :  7167737419 : }
     265                 :             : 
     266                 :             : /* Unlink the bitmap element from the current bitmap linked list,
     267                 :             :    and return it to the freelist.  */
     268                 :             : 
     269                 :             : static inline void
     270                 :   769226779 : bitmap_list_unlink_element (bitmap head, bitmap_element *element,
     271                 :             :                             bool to_freelist = true)
     272                 :             : {
     273                 :   769226779 :   bitmap_element *next = element->next;
     274                 :   769226779 :   bitmap_element *prev = element->prev;
     275                 :             : 
     276                 :   769226779 :   gcc_checking_assert (!head->tree_form);
     277                 :             : 
     278                 :   769226779 :   if (prev)
     279                 :   328472132 :     prev->next = next;
     280                 :             : 
     281                 :   769226779 :   if (next)
     282                 :   251344976 :     next->prev = prev;
     283                 :             : 
     284                 :   769226779 :   if (head->first == element)
     285                 :   440754647 :     head->first = next;
     286                 :             : 
     287                 :             :   /* Since the first thing we try is to insert before current,
     288                 :             :      make current the next entry in preference to the previous.  */
     289                 :   769226779 :   if (head->current == element)
     290                 :             :     {
     291                 :   658976045 :       head->current = next != 0 ? next : prev;
     292                 :   658976045 :       if (head->current)
     293                 :   329659893 :         head->indx = head->current->indx;
     294                 :             :       else
     295                 :   329316152 :         head->indx = 0;
     296                 :             :     }
     297                 :             : 
     298                 :   769226779 :   if (to_freelist)
     299                 :   764694544 :     bitmap_elem_to_freelist (head, element);
     300                 :   769226779 : }
     301                 :             : 
     302                 :             : /* Insert a new uninitialized element (or NODE if not NULL) into bitmap
     303                 :             :    HEAD after element ELT.  If ELT is NULL, insert the element at the start.
     304                 :             :    Return the new element.  */
     305                 :             : 
     306                 :             : static bitmap_element *
     307                 :  3290042775 : bitmap_list_insert_element_after (bitmap head,
     308                 :             :                                   bitmap_element *elt, unsigned int indx,
     309                 :             :                                   bitmap_element *node = NULL)
     310                 :             : {
     311                 :  3290042775 :   if (!node)
     312                 :  3285510540 :     node = bitmap_element_allocate (head);
     313                 :  3290042775 :   node->indx = indx;
     314                 :             : 
     315                 :  3290042775 :   gcc_checking_assert (!head->tree_form);
     316                 :             : 
     317                 :  3290042775 :   if (!elt)
     318                 :             :     {
     319                 :  1574781406 :       if (!head->current)
     320                 :             :         {
     321                 :  1527129581 :           head->current = node;
     322                 :  1527129581 :           head->indx = indx;
     323                 :             :         }
     324                 :  1574781406 :       node->next = head->first;
     325                 :  1574781406 :       if (node->next)
     326                 :    47651825 :         node->next->prev = node;
     327                 :  1574781406 :       head->first = node;
     328                 :  1574781406 :       node->prev = NULL;
     329                 :             :     }
     330                 :             :   else
     331                 :             :     {
     332                 :  1715261369 :       gcc_checking_assert (head->current);
     333                 :  1715261369 :       node->next = elt->next;
     334                 :  1715261369 :       if (node->next)
     335                 :    68127413 :         node->next->prev = node;
     336                 :  1715261369 :       elt->next = node;
     337                 :  1715261369 :       node->prev = elt;
     338                 :             :     }
     339                 :  3290042775 :   return node;
     340                 :             : }
     341                 :             : 
     342                 :             : /* Return the element for INDX, or NULL if the element doesn't exist.
     343                 :             :    Update the `current' field even if we can't find an element that
     344                 :             :    would hold the bitmap's bit to make eventual allocation
     345                 :             :    faster.  */
     346                 :             : 
     347                 :             : static inline bitmap_element *
     348                 : 91188565284 : bitmap_list_find_element (bitmap head, unsigned int indx)
     349                 :             : {
     350                 : 91188565284 :   bitmap_element *element;
     351                 :             : 
     352                 : 91188565284 :   if (head->current == NULL
     353                 : 77189854522 :       || head->indx == indx)
     354                 :             :     return head->current;
     355                 :             : 
     356                 : 10483757756 :   if (head->current == head->first
     357                 :  5225689112 :       && head->first->next == NULL)
     358                 :             :     return NULL;
     359                 :             : 
     360                 :             :   /* Usage can be NULL due to allocated bitmaps for which we do not
     361                 :             :      call initialize function.  */
     362                 :  7297952325 :   bitmap_usage *usage = NULL;
     363                 :  7297952325 :   if (GATHER_STATISTICS)
     364                 :             :     usage = bitmap_mem_desc.get_descriptor_for_instance (head);
     365                 :             : 
     366                 :             :   /* This bitmap has more than one element, and we're going to look
     367                 :             :      through the elements list.  Count that as a search.  */
     368                 :  7297952325 :   if (GATHER_STATISTICS && usage)
     369                 :             :     usage->m_nsearches++;
     370                 :             : 
     371                 :  7297952325 :   if (head->indx < indx)
     372                 :             :     /* INDX is beyond head->indx.  Search from head->current
     373                 :             :        forward.  */
     374                 :             :     for (element = head->current;
     375                 :  8646864742 :          element->next != 0 && element->indx < indx;
     376                 :             :          element = element->next)
     377                 :             :       {
     378                 :             :         if (GATHER_STATISTICS && usage)
     379                 :             :           usage->m_search_iter++;
     380                 :             :       }
     381                 :             : 
     382                 :  3854915514 :   else if (head->indx / 2 < indx)
     383                 :             :     /* INDX is less than head->indx and closer to head->indx than to
     384                 :             :        0.  Search from head->current backward.  */
     385                 :             :     for (element = head->current;
     386                 :  2485115365 :          element->prev != 0 && element->indx > indx;
     387                 :             :          element = element->prev)
     388                 :             :       {
     389                 :             :         if (GATHER_STATISTICS && usage)
     390                 :             :           usage->m_search_iter++;
     391                 :             :       }
     392                 :             : 
     393                 :             :   else
     394                 :             :     /* INDX is less than head->indx and closer to 0 than to
     395                 :             :        head->indx.  Search from head->first forward.  */
     396                 :             :     for (element = head->first;
     397                 :  4367057641 :          element->next != 0 && element->indx < indx;
     398                 :             :          element = element->next)
     399                 :             :       {
     400                 :             :         if (GATHER_STATISTICS && usage)
     401                 :             :           usage->m_search_iter++;
     402                 :             :       }
     403                 :             : 
     404                 :             :   /* `element' is the nearest to the one we want.  If it's not the one we
     405                 :             :      want, the one we want doesn't exist.  */
     406                 :  7297952325 :   gcc_checking_assert (element != NULL);
     407                 :  7297952325 :   head->current = element;
     408                 :  7297952325 :   head->indx = element->indx;
     409                 :  7297952325 :   if (element->indx != indx)
     410                 :  6270335133 :     element = 0;
     411                 :             :   return element;
     412                 :             : }
     413                 :             : 
     414                 :             : 
     415                 :             : /* Splay-tree view of bitmaps.
     416                 :             : 
     417                 :             :    This is an almost one-to-one the implementatin of the simple top-down
     418                 :             :    splay tree in Sleator and Tarjan's "Self-adjusting Binary Search Trees".
     419                 :             :    It is probably not the most efficient form of splay trees, but it should
     420                 :             :    be good enough to experiment with this idea of bitmaps-as-trees.
     421                 :             : 
     422                 :             :    For all functions below, the variable or function argument "t" is a node
     423                 :             :    in the tree, and "e" is a temporary or new node in the tree.  The rest
     424                 :             :    is sufficiently straigh-forward (and very well explained in the paper)
     425                 :             :    that comment would only clutter things.  */
     426                 :             : 
     427                 :             : static inline void
     428                 :   232764661 : bitmap_tree_link_left (bitmap_element * &t, bitmap_element * &l)
     429                 :             : {
     430                 :   232764661 :   l->next = t;
     431                 :   232764661 :   l = t;
     432                 :   232764661 :   t = t->next;
     433                 :   232764661 : }
     434                 :             : 
     435                 :             : static inline void
     436                 :   254607654 : bitmap_tree_link_right (bitmap_element * &t, bitmap_element * &r)
     437                 :             : {
     438                 :   254607654 :   r->prev = t;
     439                 :   254607654 :   r = t;
     440                 :   254607654 :   t = t->prev;
     441                 :   254607654 : }
     442                 :             : 
     443                 :             : static inline void
     444                 :    82648074 : bitmap_tree_rotate_left (bitmap_element * &t)
     445                 :             : {
     446                 :    82648074 :   bitmap_element *e = t->next;
     447                 :    82648074 :   t->next = t->next->prev;
     448                 :    82648074 :   e->prev = t;
     449                 :    82648074 :   t = e;
     450                 :    82648074 : }
     451                 :             : 
     452                 :             : static inline void
     453                 :    87730304 : bitmap_tree_rotate_right (bitmap_element * &t)
     454                 :             : {
     455                 :    87730304 :   bitmap_element *e = t->prev;
     456                 :    87730304 :   t->prev = t->prev->next;
     457                 :    87730304 :   e->next = t;
     458                 :    87730304 :   t = e;
     459                 :    87730304 : }
     460                 :             : 
     461                 :             : static bitmap_element *
     462                 :   753849726 : bitmap_tree_splay (bitmap head, bitmap_element *t, unsigned int indx)
     463                 :             : {
     464                 :   753849726 :   bitmap_element N, *l, *r;
     465                 :             : 
     466                 :   753849726 :   if (t == NULL)
     467                 :             :     return NULL;
     468                 :             : 
     469                 :   753849726 :   bitmap_usage *usage = NULL;
     470                 :   753849726 :   if (GATHER_STATISTICS)
     471                 :             :     usage = bitmap_mem_desc.get_descriptor_for_instance (head);
     472                 :             : 
     473                 :   753849726 :   N.prev = N.next = NULL;
     474                 :   753849726 :   l = r = &N;
     475                 :             : 
     476                 :  1241222041 :   while (indx != t->indx)
     477                 :             :     {
     478                 :   641325475 :       if (GATHER_STATISTICS && usage)
     479                 :             :         usage->m_search_iter++;
     480                 :             : 
     481                 :   641325475 :       if (indx < t->indx)
     482                 :             :         {
     483                 :   333735309 :           if (t->prev != NULL && indx < t->prev->indx)
     484                 :    87467728 :             bitmap_tree_rotate_right (t);
     485                 :   333735309 :           if (t->prev == NULL)
     486                 :             :             break;
     487                 :   254607654 :           bitmap_tree_link_right (t, r);
     488                 :             :         }
     489                 :   307590166 :       else if (indx > t->indx)
     490                 :             :         {
     491                 :   307590166 :           if (t->next != NULL && indx > t->next->indx)
     492                 :    82648074 :             bitmap_tree_rotate_left (t);
     493                 :   307590166 :           if (t->next == NULL)
     494                 :             :             break;
     495                 :   232764661 :           bitmap_tree_link_left (t, l);
     496                 :             :         }
     497                 :             :     }
     498                 :             : 
     499                 :   753849726 :   l->next = t->prev;
     500                 :   753849726 :   r->prev = t->next;
     501                 :   753849726 :   t->prev = N.next;
     502                 :   753849726 :   t->next = N.prev;
     503                 :   753849726 :   return t;
     504                 :             : }
     505                 :             : 
     506                 :             : /* Link bitmap element E into the current bitmap splay tree.  */
     507                 :             : 
     508                 :             : static inline void
     509                 :   182615009 : bitmap_tree_link_element (bitmap head, bitmap_element *e)
     510                 :             : {
     511                 :   182615009 :   if (head->first == NULL)
     512                 :   128450575 :     e->prev = e->next = NULL;
     513                 :             :   else
     514                 :             :     {
     515                 :    54164434 :       bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx);
     516                 :    54164434 :       if (e->indx < t->indx)
     517                 :             :         {
     518                 :    25736946 :           e->prev = t->prev;
     519                 :    25736946 :           e->next = t;
     520                 :    25736946 :           t->prev = NULL;
     521                 :             :         }
     522                 :    28427488 :       else if (e->indx > t->indx)
     523                 :             :         {
     524                 :    28427488 :           e->next = t->next;
     525                 :    28427488 :           e->prev = t;
     526                 :    28427488 :           t->next = NULL;
     527                 :             :         }
     528                 :             :       else
     529                 :           0 :         gcc_unreachable ();
     530                 :             :     }
     531                 :   182615009 :   head->first = e;
     532                 :   182615009 :   head->current = e;
     533                 :   182615009 :   head->indx = e->indx;
     534                 :   182615009 : }
     535                 :             : 
     536                 :             : /* Unlink bitmap element E from the current bitmap splay tree,
     537                 :             :    and return it to the freelist.  */
     538                 :             : 
     539                 :             : static void
     540                 :   114621378 : bitmap_tree_unlink_element (bitmap head, bitmap_element *e)
     541                 :             : {
     542                 :   114621378 :   bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx);
     543                 :             : 
     544                 :   114621378 :   gcc_checking_assert (t == e);
     545                 :             : 
     546                 :   114621378 :   if (e->prev == NULL)
     547                 :   113935077 :     t = e->next;
     548                 :             :   else
     549                 :             :     {
     550                 :      686301 :       t = bitmap_tree_splay (head, e->prev, e->indx);
     551                 :      686301 :       t->next = e->next;
     552                 :             :     }
     553                 :   114621378 :   head->first = t;
     554                 :   114621378 :   head->current = t;
     555                 :   114621378 :   head->indx = (t != NULL) ? t->indx : 0;
     556                 :             : 
     557                 :   114621378 :   bitmap_elem_to_freelist (head, e);
     558                 :   114621378 : }
     559                 :             : 
     560                 :             : /* Return the element for INDX, or NULL if the element doesn't exist.  */
     561                 :             : 
     562                 :             : static inline bitmap_element *
     563                 :  3044659329 : bitmap_tree_find_element (bitmap head, unsigned int indx)
     564                 :             : {
     565                 :  3044659329 :   if (head->current == NULL
     566                 :  2295830686 :       || head->indx == indx)
     567                 :             :     return head->current;
     568                 :             : 
     569                 :             :   /* Usage can be NULL due to allocated bitmaps for which we do not
     570                 :             :      call initialize function.  */
     571                 :   478611933 :   bitmap_usage *usage = NULL;
     572                 :   478611933 :   if (GATHER_STATISTICS)
     573                 :             :     usage = bitmap_mem_desc.get_descriptor_for_instance (head);
     574                 :             : 
     575                 :             :   /* This bitmap has more than one element, and we're going to look
     576                 :             :      through the elements list.  Count that as a search.  */
     577                 :   478611933 :   if (GATHER_STATISTICS && usage)
     578                 :             :     usage->m_nsearches++;
     579                 :             : 
     580                 :   478611933 :   bitmap_element *element = bitmap_tree_splay (head, head->first, indx);
     581                 :   478611933 :   gcc_checking_assert (element != NULL);
     582                 :   478611933 :   head->first = element;
     583                 :   478611933 :   head->current = element;
     584                 :   478611933 :   head->indx = element->indx;
     585                 :   478611933 :   if (element->indx != indx)
     586                 :    99102425 :     element = 0;
     587                 :             :   return element;
     588                 :             : }
     589                 :             : 
     590                 :             : /* Converting bitmap views from linked-list to tree and vice versa.  */
     591                 :             : 
     592                 :             : /* Splice element E and all elements with a larger index from
     593                 :             :    bitmap HEAD, convert the spliced elements to the linked-list
     594                 :             :    view, and return the head of the list (which should be E again),  */
     595                 :             : 
     596                 :             : static bitmap_element *
     597                 :    56816198 : bitmap_tree_listify_from (bitmap head, bitmap_element *e)
     598                 :             : {
     599                 :    56816198 :   bitmap_element *t, *erb;
     600                 :             : 
     601                 :             :   /* Detach the right branch from E (all elements with indx > E->indx),
     602                 :             :      and splay E to the root.  */
     603                 :    56816198 :   erb = e->next;
     604                 :    56816198 :   e->next = NULL;
     605                 :    56816198 :   t = bitmap_tree_splay (head, head->first, e->indx);
     606                 :    56816198 :   gcc_checking_assert (t == e);
     607                 :             : 
     608                 :             :   /* Because E has no right branch, and we rotated it to the root,
     609                 :             :      the left branch is the new root.  */
     610                 :    56816198 :   t = e->prev;
     611                 :    56816198 :   head->first = t;
     612                 :    56816198 :   head->current = t;
     613                 :    56816198 :   head->indx = (t != NULL) ? t->indx : 0;
     614                 :             : 
     615                 :             :   /* Detach the tree from E, and re-attach the right branch of E.  */
     616                 :    56816198 :   e->prev = NULL;
     617                 :    56816198 :   e->next = erb;
     618                 :             : 
     619                 :             :   /* The tree is now valid again.  Now we need to "un-tree" E.
     620                 :             :      It is imperative that a non-recursive implementation is used
     621                 :             :      for this, because splay trees have a worst case depth of O(N)
     622                 :             :      for a tree with N nodes.  A recursive implementation could
     623                 :             :      result in a stack overflow for a sufficiently large, unbalanced
     624                 :             :      bitmap tree.  */
     625                 :             : 
     626                 :    56816198 :   auto_vec<bitmap_element *, 32> stack;
     627                 :    56816198 :   auto_vec<bitmap_element *, 32> sorted_elements;
     628                 :    56816198 :   bitmap_element *n = e;
     629                 :             : 
     630                 :    93393630 :   while (true)
     631                 :             :     {
     632                 :   243603458 :       while (n != NULL)
     633                 :             :         {
     634                 :    93393630 :           stack.safe_push (n);
     635                 :    93393630 :           n = n->prev;
     636                 :             :         }
     637                 :             : 
     638                 :   150209828 :       if (stack.is_empty ())
     639                 :             :         break;
     640                 :             : 
     641                 :    93393630 :       n = stack.pop ();
     642                 :    93393630 :       sorted_elements.safe_push (n);
     643                 :    93393630 :       n = n->next;
     644                 :             :     }
     645                 :             : 
     646                 :    56816198 :   gcc_assert (sorted_elements[0] == e);
     647                 :             : 
     648                 :             :   bitmap_element *prev = NULL;
     649                 :             :   unsigned ix;
     650                 :   150209828 :   FOR_EACH_VEC_ELT (sorted_elements, ix, n)
     651                 :             :     {
     652                 :    93393630 :       if (prev != NULL)
     653                 :    36577432 :         prev->next = n;
     654                 :    93393630 :       n->prev = prev;
     655                 :    93393630 :       n->next = NULL;
     656                 :    93393630 :       prev = n;
     657                 :             :     }
     658                 :             : 
     659                 :    56816198 :   return e;
     660                 :    56816198 : }
     661                 :             : 
     662                 :             : /* Convert bitmap HEAD from splay-tree view to linked-list view.  */
     663                 :             : 
     664                 :             : void
     665                 :     9282429 : bitmap_list_view (bitmap head)
     666                 :             : {
     667                 :     9282429 :   bitmap_element *ptr;
     668                 :             : 
     669                 :     9282429 :   gcc_assert (head->tree_form);
     670                 :             : 
     671                 :     9282429 :   ptr = head->first;
     672                 :     9282429 :   if (ptr)
     673                 :             :     {
     674                 :     8129292 :       while (ptr->prev)
     675                 :      262576 :         bitmap_tree_rotate_right (ptr);
     676                 :     7866716 :       head->first = ptr;
     677                 :     7866716 :       head->first = bitmap_tree_listify_from (head, ptr);
     678                 :             :     }
     679                 :             : 
     680                 :     9282429 :   head->tree_form = false;
     681                 :     9282429 :   if (!head->current)
     682                 :             :     {
     683                 :     9282429 :       head->current = head->first;
     684                 :     9282429 :       head->indx = head->current ? head->current->indx : 0;
     685                 :             :     }
     686                 :     9282429 : }
     687                 :             : 
     688                 :             : /* Convert bitmap HEAD from linked-list view to splay-tree view.
     689                 :             :    This is simply a matter of dropping the prev or next pointers
     690                 :             :    and setting the tree_form flag.  The tree will balance itself
     691                 :             :    if and when it is used.  */
     692                 :             : 
     693                 :             : void
     694                 :   126682009 : bitmap_tree_view (bitmap head)
     695                 :             : {
     696                 :   126682009 :   bitmap_element *ptr;
     697                 :             : 
     698                 :   126682009 :   gcc_assert (! head->tree_form);
     699                 :             : 
     700                 :   126682009 :   ptr = head->first;
     701                 :   153633569 :   while (ptr)
     702                 :             :     {
     703                 :    26951560 :       ptr->prev = NULL;
     704                 :    26951560 :       ptr = ptr->next;
     705                 :             :     }
     706                 :             : 
     707                 :   126682009 :   head->tree_form = true;
     708                 :   126682009 : }
     709                 :             : 
     710                 :             : /* Clear a bitmap by freeing all its elements.  */
     711                 :             : 
     712                 :             : void
     713                 : 12512767812 : bitmap_clear (bitmap head)
     714                 :             : {
     715                 : 12512767812 :   if (head->first == NULL)
     716                 :             :     return;
     717                 :  6209717806 :   if (head->tree_form)
     718                 :             :     {
     719                 :             :       bitmap_element *e, *t;
     720                 :    64404397 :       for (e = head->first; e->prev; e = e->prev)
     721                 :             :         /* Loop to find the element with the smallest index.  */ ;
     722                 :    48949482 :       t = bitmap_tree_splay (head, head->first, e->indx);
     723                 :    48949482 :       gcc_checking_assert (t == e);
     724                 :    48949482 :       head->first = t;
     725                 :             :     }
     726                 :  6209717806 :   bitmap_elt_clear_from (head, head->first);
     727                 :             : }
     728                 :             : 
     729                 :             : /* Initialize a bitmap obstack.  If BIT_OBSTACK is NULL, initialize
     730                 :             :    the default bitmap obstack.  */
     731                 :             : 
     732                 :             : void
     733                 :   293999018 : bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
     734                 :             : {
     735                 :   293999018 :   if (!bit_obstack)
     736                 :             :     {
     737                 :    13656360 :       if (bitmap_default_obstack_depth++)
     738                 :             :         return;
     739                 :             :       bit_obstack = &bitmap_default_obstack;
     740                 :             :     }
     741                 :             : 
     742                 :             : #if !defined(__GNUC__) || (__GNUC__ < 2)
     743                 :             : #define __alignof__(type) 0
     744                 :             : #endif
     745                 :             : 
     746                 :   283028841 :   bit_obstack->elements = NULL;
     747                 :   283028841 :   bit_obstack->heads = NULL;
     748                 :   283028841 :   obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE,
     749                 :             :                               __alignof__ (bitmap_element),
     750                 :             :                               obstack_chunk_alloc,
     751                 :             :                               obstack_chunk_free);
     752                 :             : }
     753                 :             : 
     754                 :             : /* Release the memory from a bitmap obstack.  If BIT_OBSTACK is NULL,
     755                 :             :    release the default bitmap obstack.  */
     756                 :             : 
     757                 :             : void
     758                 :   293957228 : bitmap_obstack_release (bitmap_obstack *bit_obstack)
     759                 :             : {
     760                 :   293957228 :   if (!bit_obstack)
     761                 :             :     {
     762                 :    13632880 :       if (--bitmap_default_obstack_depth)
     763                 :             :         {
     764                 :    10969711 :           gcc_assert (bitmap_default_obstack_depth > 0);
     765                 :             :           return;
     766                 :             :         }
     767                 :             :       bit_obstack = &bitmap_default_obstack;
     768                 :             :     }
     769                 :             : 
     770                 :   282987517 :   bit_obstack->elements = NULL;
     771                 :   282987517 :   bit_obstack->heads = NULL;
     772                 :   282987517 :   obstack_free (&bit_obstack->obstack, NULL);
     773                 :             : }
     774                 :             : 
     775                 :             : /* Create a new bitmap on an obstack.  If BIT_OBSTACK is NULL, create
     776                 :             :    it on the default bitmap obstack.  */
     777                 :             : 
     778                 :             : bitmap
     779                 :  3563053373 : bitmap_alloc (bitmap_obstack *bit_obstack MEM_STAT_DECL)
     780                 :             : {
     781                 :  3563053373 :   bitmap map;
     782                 :             : 
     783                 :  3563053373 :   if (!bit_obstack)
     784                 :             :     {
     785                 :   639297092 :       gcc_assert (bitmap_default_obstack_depth > 0);
     786                 :             :       bit_obstack = &bitmap_default_obstack;
     787                 :             :     }
     788                 :  3563053373 :   map = bit_obstack->heads;
     789                 :  3563053373 :   if (map)
     790                 :  1186121973 :     bit_obstack->heads = (class bitmap_head *) map->first;
     791                 :             :   else
     792                 :  2376931400 :     map = XOBNEW (&bit_obstack->obstack, bitmap_head);
     793                 :  3563053373 :   bitmap_initialize (map, bit_obstack PASS_MEM_STAT);
     794                 :             : 
     795                 :  3563053373 :   if (GATHER_STATISTICS)
     796                 :             :     register_overhead (map, sizeof (bitmap_head));
     797                 :             : 
     798                 :  3563053373 :   return map;
     799                 :             : }
     800                 :             : 
     801                 :             : /* Create a new GCd bitmap.  */
     802                 :             : 
     803                 :             : bitmap
     804                 :    44094024 : bitmap_gc_alloc (ALONE_MEM_STAT_DECL)
     805                 :             : {
     806                 :    44094024 :   bitmap map;
     807                 :             : 
     808                 :    44094024 :   map = ggc_alloc<bitmap_head> ();
     809                 :    44094024 :   bitmap_initialize (map, NULL PASS_MEM_STAT);
     810                 :             : 
     811                 :    44094024 :   if (GATHER_STATISTICS)
     812                 :             :     register_overhead (map, sizeof (bitmap_head));
     813                 :             : 
     814                 :    44094024 :   return map;
     815                 :             : }
     816                 :             : 
     817                 :             : /* Release an obstack allocated bitmap.  */
     818                 :             : 
     819                 :             : void
     820                 :  2421867502 : bitmap_obstack_free (bitmap map)
     821                 :             : {
     822                 :  2421867502 :   if (map)
     823                 :             :     {
     824                 :  1352312694 :       bitmap_clear (map);
     825                 :  1352312694 :       map->first = (bitmap_element *) map->obstack->heads;
     826                 :             : 
     827                 :  1352312694 :       if (GATHER_STATISTICS)
     828                 :             :         release_overhead (map, sizeof (bitmap_head), true);
     829                 :             : 
     830                 :  1352312694 :       map->obstack->heads = map;
     831                 :             :     }
     832                 :  2421867502 : }
     833                 :             : 
     834                 :             : 
     835                 :             : /* Return nonzero if all bits in an element are zero.  */
     836                 :             : 
     837                 :             : static inline int
     838                 :   861157936 : bitmap_element_zerop (const bitmap_element *element)
     839                 :             : {
     840                 :             : #if BITMAP_ELEMENT_WORDS == 2
     841                 :   861157936 :   return (element->bits[0] | element->bits[1]) == 0;
     842                 :             : #else
     843                 :             :   unsigned i;
     844                 :             : 
     845                 :             :   for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
     846                 :             :     if (element->bits[i] != 0)
     847                 :             :       return 0;
     848                 :             : 
     849                 :             :   return 1;
     850                 :             : #endif
     851                 :             : }
     852                 :             : 
     853                 :             : /* Copy a bitmap to another bitmap.  */
     854                 :             : 
     855                 :             : void
     856                 :  1925827659 : bitmap_copy (bitmap to, const_bitmap from)
     857                 :             : {
     858                 :  1925827659 :   const bitmap_element *from_ptr;
     859                 :  1925827659 :   bitmap_element *to_ptr = 0;
     860                 :             : 
     861                 :  1925827659 :   gcc_checking_assert (!to->tree_form && !from->tree_form);
     862                 :             : 
     863                 :  1925827659 :   bitmap_clear (to);
     864                 :             : 
     865                 :             :   /* Copy elements in forward direction one at a time.  */
     866                 :  4298798607 :   for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
     867                 :             :     {
     868                 :  2372970948 :       bitmap_element *to_elt = bitmap_element_allocate (to);
     869                 :             : 
     870                 :  2372970948 :       to_elt->indx = from_ptr->indx;
     871                 :  2372970948 :       memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits));
     872                 :             : 
     873                 :             :       /* Here we have a special case of bitmap_list_link_element,
     874                 :             :          for the case where we know the links are being entered
     875                 :             :          in sequence.  */
     876                 :  2372970948 :       if (to_ptr == 0)
     877                 :             :         {
     878                 :  1535323743 :           to->first = to->current = to_elt;
     879                 :  1535323743 :           to->indx = from_ptr->indx;
     880                 :  1535323743 :           to_elt->next = to_elt->prev = 0;
     881                 :             :         }
     882                 :             :       else
     883                 :             :         {
     884                 :   837647205 :           to_elt->prev = to_ptr;
     885                 :   837647205 :           to_elt->next = 0;
     886                 :   837647205 :           to_ptr->next = to_elt;
     887                 :             :         }
     888                 :             : 
     889                 :  2372970948 :       to_ptr = to_elt;
     890                 :             :     }
     891                 :  1925827659 : }
     892                 :             : 
     893                 :             : /* Move a bitmap to another bitmap.  */
     894                 :             : 
     895                 :             : void
     896                 :    28167254 : bitmap_move (bitmap to, bitmap from)
     897                 :             : {
     898                 :    28167254 :   gcc_assert (to->obstack == from->obstack);
     899                 :             : 
     900                 :    28167254 :   bitmap_clear (to);
     901                 :             : 
     902                 :    28167254 :   size_t sz = 0;
     903                 :    28167254 :   if (GATHER_STATISTICS)
     904                 :             :     {
     905                 :             :       for (bitmap_element *e = to->first; e; e = e->next)
     906                 :             :         sz += sizeof (bitmap_element);
     907                 :             :       register_overhead (to, sz);
     908                 :             :     }
     909                 :             : 
     910                 :    28167254 :   *to = *from;
     911                 :             : 
     912                 :    28167254 :   if (GATHER_STATISTICS)
     913                 :             :     release_overhead (from, sz, false);
     914                 :    28167254 : }
     915                 :             : 
     916                 :             : /* Clear a single bit in a bitmap.  Return true if the bit changed.  */
     917                 :             : 
     918                 :             : bool
     919                 : 24279982733 : bitmap_clear_bit (bitmap head, int bit)
     920                 :             : {
     921                 : 24279982733 :   unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
     922                 : 24279982733 :   bitmap_element *ptr;
     923                 :             : 
     924                 : 24279982733 :   if (!head->tree_form)
     925                 : 23516896442 :     ptr = bitmap_list_find_element (head, indx);
     926                 :             :   else
     927                 :   763086291 :     ptr = bitmap_tree_find_element (head, indx);
     928                 : 24279982733 :   if (ptr != 0)
     929                 :             :     {
     930                 : 19806510083 :       unsigned bit_num  = bit % BITMAP_WORD_BITS;
     931                 : 19806510083 :       unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
     932                 : 19806510083 :       BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
     933                 : 19806510083 :       bool res = (ptr->bits[word_num] & bit_val) != 0;
     934                 : 19806510083 :       if (res)
     935                 :             :         {
     936                 :  3393493969 :           ptr->bits[word_num] &= ~bit_val;
     937                 :             :           /* If we cleared the entire word, free up the element.  */
     938                 :  3393493969 :           if (!ptr->bits[word_num]
     939                 :  3393493969 :               && bitmap_element_zerop (ptr))
     940                 :             :             {
     941                 :   570575579 :               if (!head->tree_form)
     942                 :   488757122 :                 bitmap_list_unlink_element (head, ptr);
     943                 :             :               else
     944                 :    81818457 :                 bitmap_tree_unlink_element (head, ptr);
     945                 :             :             }
     946                 :             :         }
     947                 :             : 
     948                 : 19806510083 :       return res;
     949                 :             :     }
     950                 :             : 
     951                 :             :   return false;
     952                 :             : }
     953                 :             : 
     954                 :             : /* Set a single bit in a bitmap.  Return true if the bit changed.  */
     955                 :             : 
     956                 :             : bool
     957                 : 37221739066 : bitmap_set_bit (bitmap head, int bit)
     958                 :             : {
     959                 : 37221739066 :   unsigned indx = bit / BITMAP_ELEMENT_ALL_BITS;
     960                 : 37221739066 :   bitmap_element *ptr;
     961                 : 37221739066 :   if (!head->tree_form)
     962                 : 35438285454 :     ptr = bitmap_list_find_element (head, indx);
     963                 :             :   else
     964                 :  1783453612 :     ptr = bitmap_tree_find_element (head, indx);
     965                 : 37221739066 :   unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
     966                 : 37221739066 :   unsigned bit_num  = bit % BITMAP_WORD_BITS;
     967                 : 37221739066 :   BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
     968                 :             : 
     969                 : 37221739066 :   if (ptr != 0)
     970                 :             :     {
     971                 : 30007790325 :       bool res = (ptr->bits[word_num] & bit_val) == 0;
     972                 : 30007790325 :       if (res)
     973                 : 21621837367 :         ptr->bits[word_num] |= bit_val;
     974                 : 30007790325 :       return res;
     975                 :             :     }
     976                 :             : 
     977                 :  7213948741 :   ptr = bitmap_element_allocate (head);
     978                 :  7213948741 :   ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
     979                 :  7213948741 :   ptr->bits[word_num] = bit_val;
     980                 :  7213948741 :   if (!head->tree_form)
     981                 :  7031387898 :     bitmap_list_link_element (head, ptr);
     982                 :             :   else
     983                 :   182560843 :     bitmap_tree_link_element (head, ptr);
     984                 :             :   return true;
     985                 :             : }
     986                 :             : 
     987                 :             : /* Return whether a bit is set within a bitmap.  */
     988                 :             : 
     989                 :             : bool
     990                 : 29644970121 : bitmap_bit_p (const_bitmap head, int bit)
     991                 :             : {
     992                 : 29644970121 :   unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
     993                 : 29644970121 :   const bitmap_element *ptr;
     994                 : 29644970121 :   unsigned bit_num;
     995                 : 29644970121 :   unsigned word_num;
     996                 :             : 
     997                 : 29644970121 :   if (!head->tree_form)
     998                 : 29160187456 :     ptr = bitmap_list_find_element (const_cast<bitmap> (head), indx);
     999                 :             :   else
    1000                 :   484782665 :     ptr = bitmap_tree_find_element (const_cast<bitmap> (head), indx);
    1001                 : 29644970121 :   if (ptr == 0)
    1002                 :             :     return 0;
    1003                 :             : 
    1004                 : 21983685310 :   bit_num = bit % BITMAP_WORD_BITS;
    1005                 : 21983685310 :   word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
    1006                 :             : 
    1007                 : 21983685310 :   return (ptr->bits[word_num] >> bit_num) & 1;
    1008                 :             : }
    1009                 :             : 
    1010                 :             : /* Set CHUNK_SIZE bits at a time in bitmap HEAD.
    1011                 :             :    Store CHUNK_VALUE starting at bits CHUNK * chunk_size.
    1012                 :             :    This is the set routine for viewing bitmap as a multi-bit sparse array.  */
    1013                 :             : 
    1014                 :             : void
    1015                 :      291946 : bitmap_set_aligned_chunk (bitmap head, unsigned int chunk,
    1016                 :             :                           unsigned int chunk_size, BITMAP_WORD chunk_value)
    1017                 :             : {
    1018                 :             :   // Ensure chunk size is a power of 2 and fits in BITMAP_WORD.
    1019                 :      291946 :   gcc_checking_assert (pow2p_hwi (chunk_size));
    1020                 :      291946 :   gcc_checking_assert (chunk_size < (sizeof (BITMAP_WORD) * CHAR_BIT));
    1021                 :             : 
    1022                 :             :   // Ensure chunk_value is within range of chunk_size bits.
    1023                 :      291946 :   BITMAP_WORD max_value = (1 << chunk_size) - 1;
    1024                 :      291946 :   gcc_checking_assert (chunk_value <= max_value);
    1025                 :             : 
    1026                 :      291946 :   unsigned bit = chunk * chunk_size;
    1027                 :      291946 :   unsigned indx = bit / BITMAP_ELEMENT_ALL_BITS;
    1028                 :      291946 :   bitmap_element *ptr;
    1029                 :      291946 :   if (!head->tree_form)
    1030                 :          64 :     ptr = bitmap_list_find_element (head, indx);
    1031                 :             :   else
    1032                 :      291882 :     ptr = bitmap_tree_find_element (head, indx);
    1033                 :      291946 :   unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
    1034                 :      291946 :   unsigned bit_num  = bit % BITMAP_WORD_BITS;
    1035                 :      291946 :   BITMAP_WORD bit_val = chunk_value << bit_num;
    1036                 :      291946 :   BITMAP_WORD mask = ~(max_value << bit_num);
    1037                 :             : 
    1038                 :      291946 :   if (ptr != 0)
    1039                 :             :     {
    1040                 :      237768 :       ptr->bits[word_num] &= mask;
    1041                 :      237768 :       ptr->bits[word_num] |= bit_val;
    1042                 :      237768 :       return;
    1043                 :             :     }
    1044                 :             : 
    1045                 :       54178 :   ptr = bitmap_element_allocate (head);
    1046                 :       54178 :   ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
    1047                 :       54178 :   ptr->bits[word_num] = bit_val;
    1048                 :       54178 :   if (!head->tree_form)
    1049                 :          12 :     bitmap_list_link_element (head, ptr);
    1050                 :             :   else
    1051                 :       54166 :     bitmap_tree_link_element (head, ptr);
    1052                 :             : }
    1053                 :             : 
    1054                 :             : /* This is the get routine for viewing bitmap as a multi-bit sparse array.
    1055                 :             :    Return a set of CHUNK_SIZE consecutive bits from HEAD, starting at bit
    1056                 :             :    CHUNK * chunk_size.   */
    1057                 :             : 
    1058                 :             : BITMAP_WORD
    1059                 :    13045135 : bitmap_get_aligned_chunk (const_bitmap head, unsigned int chunk,
    1060                 :             :                           unsigned int chunk_size)
    1061                 :             : {
    1062                 :             :   // Ensure chunk size is a power of 2, fits in BITMAP_WORD and is in range.
    1063                 :    13045135 :   gcc_checking_assert (pow2p_hwi (chunk_size));
    1064                 :    13045135 :   gcc_checking_assert (chunk_size < (sizeof (BITMAP_WORD) * CHAR_BIT));
    1065                 :             : 
    1066                 :    13045135 :   BITMAP_WORD max_value = (1 << chunk_size) - 1;
    1067                 :    13045135 :   unsigned bit = chunk * chunk_size;
    1068                 :    13045135 :   unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
    1069                 :    13045135 :   const bitmap_element *ptr;
    1070                 :    13045135 :   unsigned bit_num;
    1071                 :    13045135 :   unsigned word_num;
    1072                 :             : 
    1073                 :    13045135 :   if (!head->tree_form)
    1074                 :         256 :     ptr = bitmap_list_find_element (const_cast<bitmap> (head), indx);
    1075                 :             :   else
    1076                 :    13044879 :     ptr = bitmap_tree_find_element (const_cast<bitmap> (head), indx);
    1077                 :    13045135 :   if (ptr == 0)
    1078                 :             :     return 0;
    1079                 :             : 
    1080                 :     4290019 :   bit_num = bit % BITMAP_WORD_BITS;
    1081                 :     4290019 :   word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
    1082                 :             : 
    1083                 :             :   // Return 4 bits.
    1084                 :     4290019 :   return (ptr->bits[word_num] >> bit_num) & max_value;
    1085                 :             : }
    1086                 :             : 
    1087                 :             : #if GCC_VERSION < 3400
    1088                 :             : /* Table of number of set bits in a character, indexed by value of char.  */
    1089                 :             : static const unsigned char popcount_table[] =
    1090                 :             : {
    1091                 :             :     0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
    1092                 :             :     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    1093                 :             :     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    1094                 :             :     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
    1095                 :             :     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    1096                 :             :     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
    1097                 :             :     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
    1098                 :             :     3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
    1099                 :             : };
    1100                 :             : 
    1101                 :             : static unsigned long
    1102                 :             : bitmap_popcount (BITMAP_WORD a)
    1103                 :             : {
    1104                 :             :   unsigned long ret = 0;
    1105                 :             :   unsigned i;
    1106                 :             : 
    1107                 :             :   /* Just do this the table way for now  */
    1108                 :             :   for (i = 0; i < BITMAP_WORD_BITS; i+= 8)
    1109                 :             :     ret += popcount_table[(a >> i) & 0xff];
    1110                 :             :   return ret;
    1111                 :             : }
    1112                 :             : #endif
    1113                 :             : 
    1114                 :             : /* Count and return the number of bits set in the bitmap word BITS.  */
    1115                 :             : static unsigned long
    1116                 :    59883857 : bitmap_count_bits_in_word (const BITMAP_WORD *bits)
    1117                 :             : {
    1118                 :    59883857 :   unsigned long count = 0;
    1119                 :             : 
    1120                 :   181830327 :   for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
    1121                 :             :     {
    1122                 :             : #if GCC_VERSION >= 3400
    1123                 :             :       /* Note that popcountl matches BITMAP_WORD in type, so the actual size
    1124                 :             :          of BITMAP_WORD is not material.  */
    1125                 :   121220218 :       count += __builtin_popcountl (bits[ix]);
    1126                 :             : #else
    1127                 :             :       count += bitmap_popcount (bits[ix]);
    1128                 :             : #endif
    1129                 :             :     }
    1130                 :    60610109 :   return count;
    1131                 :             : }
    1132                 :             : 
    1133                 :             : /* Count the number of bits set in the bitmap, and return it.  */
    1134                 :             : 
    1135                 :             : unsigned long
    1136                 :    99160595 : bitmap_count_bits (const_bitmap a)
    1137                 :             : {
    1138                 :    99160595 :   unsigned long count = 0;
    1139                 :    99160595 :   const bitmap_element *elt;
    1140                 :             : 
    1141                 :    99160595 :   gcc_checking_assert (!a->tree_form);
    1142                 :   158908982 :   for (elt = a->first; elt; elt = elt->next)
    1143                 :   119496774 :     count += bitmap_count_bits_in_word (elt->bits);
    1144                 :             : 
    1145                 :    99160595 :   return count;
    1146                 :             : }
    1147                 :             : 
    1148                 :             : /* Count the number of unique bits set in A and B and return it.  */
    1149                 :             : 
    1150                 :             : unsigned long
    1151                 :      681776 : bitmap_count_unique_bits (const_bitmap a, const_bitmap b)
    1152                 :             : {
    1153                 :      681776 :   unsigned long count = 0;
    1154                 :      681776 :   const bitmap_element *elt_a, *elt_b;
    1155                 :             : 
    1156                 :     1543498 :   for (elt_a = a->first, elt_b = b->first; elt_a && elt_b; )
    1157                 :             :     {
    1158                 :             :       /* If we're at different indices, then count all the bits
    1159                 :             :          in the lower element.  If we're at the same index, then
    1160                 :             :          count the bits in the IOR of the two elements.  */
    1161                 :      861722 :       if (elt_a->indx < elt_b->indx)
    1162                 :             :         {
    1163                 :       55575 :           count += bitmap_count_bits_in_word (elt_a->bits);
    1164                 :       55575 :           elt_a = elt_a->next;
    1165                 :             :         }
    1166                 :      806147 :       else if (elt_b->indx < elt_a->indx)
    1167                 :             :         {
    1168                 :       79895 :           count += bitmap_count_bits_in_word (elt_b->bits);
    1169                 :       79895 :           elt_b = elt_b->next;
    1170                 :             :         }
    1171                 :             :       else
    1172                 :             :         {
    1173                 :             :           BITMAP_WORD bits[BITMAP_ELEMENT_WORDS];
    1174                 :     2178756 :           for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
    1175                 :     1452504 :             bits[ix] = elt_a->bits[ix] | elt_b->bits[ix];
    1176                 :      726252 :           count += bitmap_count_bits_in_word (bits);
    1177                 :      726252 :           elt_a = elt_a->next;
    1178                 :      726252 :           elt_b = elt_b->next;
    1179                 :             :         }
    1180                 :             :     }
    1181                 :      681776 :   return count;
    1182                 :             : }
    1183                 :             : 
    1184                 :             : /* Return true if the bitmap has a single bit set.  Otherwise return
    1185                 :             :    false.  */
    1186                 :             : 
    1187                 :             : bool
    1188                 :     5615112 : bitmap_single_bit_set_p (const_bitmap a)
    1189                 :             : {
    1190                 :     5615112 :   unsigned long count = 0;
    1191                 :     5615112 :   const bitmap_element *elt;
    1192                 :     5615112 :   unsigned ix;
    1193                 :             : 
    1194                 :     5615112 :   if (bitmap_empty_p (a))
    1195                 :             :     return false;
    1196                 :             : 
    1197                 :     5613796 :   elt = a->first;
    1198                 :             : 
    1199                 :             :   /* As there are no completely empty bitmap elements, a second one
    1200                 :             :      means we have more than one bit set.  */
    1201                 :     5613796 :   if (elt->next != NULL
    1202                 :     2257485 :       && (!a->tree_form || elt->prev != NULL))
    1203                 :             :     return false;
    1204                 :             : 
    1205                 :     6748141 :   for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
    1206                 :             :     {
    1207                 :             : #if GCC_VERSION >= 3400
    1208                 :             :       /* Note that popcountl matches BITMAP_WORD in type, so the actual size
    1209                 :             :          of BITMAP_WORD is not material.  */
    1210                 :     5419522 :       count += __builtin_popcountl (elt->bits[ix]);
    1211                 :             : #else
    1212                 :             :       count += bitmap_popcount (elt->bits[ix]);
    1213                 :             : #endif
    1214                 :     5419522 :       if (count > 1)
    1215                 :             :         return false;
    1216                 :             :     }
    1217                 :             : 
    1218                 :     1328619 :   return count == 1;
    1219                 :             : }
    1220                 :             : 
    1221                 :             : 
    1222                 :             : /* Return the bit number of the first set bit in the bitmap.  The
    1223                 :             :    bitmap must be non-empty.  When CLEAR is true it clears the bit.  */
    1224                 :             : 
    1225                 :             : static unsigned
    1226                 :  1542268907 : bitmap_first_set_bit_worker (bitmap a, bool clear)
    1227                 :             : {
    1228                 :  1542268907 :   bitmap_element *elt = a->first;
    1229                 :  1542268907 :   unsigned bit_no;
    1230                 :  1542268907 :   BITMAP_WORD word;
    1231                 :  1542268907 :   unsigned ix;
    1232                 :             : 
    1233                 :  1542268907 :   gcc_checking_assert (elt);
    1234                 :             : 
    1235                 :  1542268907 :   if (a->tree_form)
    1236                 :   309508826 :     while (elt->prev)
    1237                 :             :       elt = elt->prev;
    1238                 :             : 
    1239                 :  1542268907 :   bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
    1240                 :  1860959422 :   for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
    1241                 :             :     {
    1242                 :  1860959422 :       word = elt->bits[ix];
    1243                 :  1860959422 :       if (word)
    1244                 :  1542268907 :         goto found_bit;
    1245                 :             :     }
    1246                 :           0 :   gcc_unreachable ();
    1247                 :  1542268907 :  found_bit:
    1248                 :  1542268907 :   bit_no += ix * BITMAP_WORD_BITS;
    1249                 :             : 
    1250                 :             : #if GCC_VERSION >= 3004
    1251                 :  1542268907 :   gcc_assert (sizeof (long) == sizeof (word));
    1252                 :  1542268907 :   bit_no += __builtin_ctzl (word);
    1253                 :             : #else
    1254                 :             :   /* Binary search for the first set bit.  */
    1255                 :             : #if BITMAP_WORD_BITS > 64
    1256                 :             : #error "Fill out the table."
    1257                 :             : #endif
    1258                 :             : #if BITMAP_WORD_BITS > 32
    1259                 :             :   if (!(word & 0xffffffff))
    1260                 :             :     word >>= 32, bit_no += 32;
    1261                 :             : #endif
    1262                 :             :   if (!(word & 0xffff))
    1263                 :             :     word >>= 16, bit_no += 16;
    1264                 :             :   if (!(word & 0xff))
    1265                 :             :     word >>= 8, bit_no += 8;
    1266                 :             :   if (!(word & 0xf))
    1267                 :             :     word >>= 4, bit_no += 4;
    1268                 :             :   if (!(word & 0x3))
    1269                 :             :     word >>= 2, bit_no += 2;
    1270                 :             :   if (!(word & 0x1))
    1271                 :             :     word >>= 1, bit_no += 1;
    1272                 :             : 
    1273                 :             :  gcc_checking_assert (word & 1);
    1274                 :             : #endif
    1275                 :             : 
    1276                 :  1542268907 :  if (clear)
    1277                 :             :    {
    1278                 :  1033882780 :      elt->bits[ix] &= ~((BITMAP_WORD) 1 << (bit_no % BITMAP_WORD_BITS));
    1279                 :             :      /* If we cleared the entire word, free up the element.  */
    1280                 :  1033882780 :      if (!elt->bits[ix]
    1281                 :  1033882780 :          && bitmap_element_zerop (elt))
    1282                 :             :        {
    1283                 :   119223239 :          if (!a->tree_form)
    1284                 :    86420318 :            bitmap_list_unlink_element (a, elt);
    1285                 :             :          else
    1286                 :    32802921 :            bitmap_tree_unlink_element (a, elt);
    1287                 :             :        }
    1288                 :             :    }
    1289                 :             : 
    1290                 :  1542268907 :  return bit_no;
    1291                 :             : }
    1292                 :             : 
    1293                 :             : /* Return the bit number of the first set bit in the bitmap.  The
    1294                 :             :    bitmap must be non-empty.  */
    1295                 :             : 
    1296                 :             : unsigned
    1297                 :   508386127 : bitmap_first_set_bit (const_bitmap a)
    1298                 :             : {
    1299                 :   508386127 :   return bitmap_first_set_bit_worker (const_cast<bitmap> (a), false);
    1300                 :             : }
    1301                 :             : 
    1302                 :             : /* Return and clear the bit number of the first set bit in the bitmap.  The
    1303                 :             :    bitmap must be non-empty.  */
    1304                 :             : 
    1305                 :             : unsigned
    1306                 :  1033882780 : bitmap_clear_first_set_bit (bitmap a)
    1307                 :             : {
    1308                 :  1033882780 :   return bitmap_first_set_bit_worker (a, true);
    1309                 :             : }
    1310                 :             : 
    1311                 :             : /* Return the bit number of the first set bit in the bitmap.  The
    1312                 :             :    bitmap must be non-empty.  */
    1313                 :             : 
    1314                 :             : unsigned
    1315                 :           0 : bitmap_last_set_bit (const_bitmap a)
    1316                 :             : {
    1317                 :           0 :   const bitmap_element *elt;
    1318                 :           0 :   unsigned bit_no;
    1319                 :           0 :   BITMAP_WORD word;
    1320                 :           0 :   int ix;
    1321                 :             : 
    1322                 :           0 :   if (a->tree_form)
    1323                 :           0 :     elt = a->first;
    1324                 :             :   else
    1325                 :           0 :     elt = a->current ? a->current : a->first;
    1326                 :           0 :   gcc_checking_assert (elt);
    1327                 :             : 
    1328                 :           0 :   while (elt->next)
    1329                 :             :     elt = elt->next;
    1330                 :             : 
    1331                 :           0 :   bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
    1332                 :           0 :   for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 1; ix--)
    1333                 :             :     {
    1334                 :           0 :       word = elt->bits[ix];
    1335                 :           0 :       if (word)
    1336                 :           0 :         goto found_bit;
    1337                 :             :     }
    1338                 :           0 :   gcc_assert (elt->bits[ix] != 0);
    1339                 :           0 :  found_bit:
    1340                 :           0 :   bit_no += ix * BITMAP_WORD_BITS;
    1341                 :             : #if GCC_VERSION >= 3004
    1342                 :           0 :   gcc_assert (sizeof (long) == sizeof (word));
    1343                 :           0 :   bit_no += BITMAP_WORD_BITS - __builtin_clzl (word) - 1;
    1344                 :             : #else
    1345                 :             :   /* Hopefully this is a twos-complement host...  */
    1346                 :             :   BITMAP_WORD x = word;
    1347                 :             :   x |= (x >> 1);
    1348                 :             :   x |= (x >> 2);
    1349                 :             :   x |= (x >> 4);
    1350                 :             :   x |= (x >> 8);
    1351                 :             :   x |= (x >> 16);
    1352                 :             : #if BITMAP_WORD_BITS > 32
    1353                 :             :   x |= (x >> 32);
    1354                 :             : #endif
    1355                 :             :   bit_no += bitmap_popcount (x) - 1;
    1356                 :             : #endif
    1357                 :             : 
    1358                 :           0 :   return bit_no;
    1359                 :             : }
    1360                 :             : 
    1361                 :             : 
    1362                 :             : /* DST = A & B.  */
    1363                 :             : 
    1364                 :             : void
    1365                 :   620788928 : bitmap_and (bitmap dst, const_bitmap a, const_bitmap b)
    1366                 :             : {
    1367                 :   620788928 :   bitmap_element *dst_elt = dst->first;
    1368                 :   620788928 :   const bitmap_element *a_elt = a->first;
    1369                 :   620788928 :   const bitmap_element *b_elt = b->first;
    1370                 :   620788928 :   bitmap_element *dst_prev = NULL;
    1371                 :             : 
    1372                 :   620788928 :   gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
    1373                 :   620788928 :   gcc_assert (dst != a && dst != b);
    1374                 :             : 
    1375                 :   620788928 :   if (a == b)
    1376                 :             :     {
    1377                 :           0 :       bitmap_copy (dst, a);
    1378                 :           0 :       return;
    1379                 :             :     }
    1380                 :             : 
    1381                 :  1476506144 :   while (a_elt && b_elt)
    1382                 :             :     {
    1383                 :   855717216 :       if (a_elt->indx < b_elt->indx)
    1384                 :    22341260 :         a_elt = a_elt->next;
    1385                 :   833375956 :       else if (b_elt->indx < a_elt->indx)
    1386                 :   158690096 :         b_elt = b_elt->next;
    1387                 :             :       else
    1388                 :             :         {
    1389                 :             :           /* Matching elts, generate A & B.  */
    1390                 :   674685860 :           unsigned ix;
    1391                 :   674685860 :           BITMAP_WORD ior = 0;
    1392                 :             : 
    1393                 :   674685860 :           if (!dst_elt)
    1394                 :   209991398 :             dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
    1395                 :             :                                                         a_elt->indx);
    1396                 :             :           else
    1397                 :   464694462 :             dst_elt->indx = a_elt->indx;
    1398                 :  2024057580 :           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
    1399                 :             :             {
    1400                 :  1349371720 :               BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
    1401                 :             : 
    1402                 :  1349371720 :               dst_elt->bits[ix] = r;
    1403                 :  1349371720 :               ior |= r;
    1404                 :             :             }
    1405                 :   674685860 :           if (ior)
    1406                 :             :             {
    1407                 :   407592933 :               dst_prev = dst_elt;
    1408                 :   407592933 :               dst_elt = dst_elt->next;
    1409                 :             :             }
    1410                 :   674685860 :           a_elt = a_elt->next;
    1411                 :   674685860 :           b_elt = b_elt->next;
    1412                 :             :         }
    1413                 :             :     }
    1414                 :             :   /* Ensure that dst->current is valid.  */
    1415                 :   620788928 :   dst->current = dst->first;
    1416                 :   620788928 :   bitmap_elt_clear_from (dst, dst_elt);
    1417                 :   620788928 :   gcc_checking_assert (!dst->current == !dst->first);
    1418                 :   620788928 :   if (dst->current)
    1419                 :   350064525 :     dst->indx = dst->current->indx;
    1420                 :             : }
    1421                 :             : 
    1422                 :             : /* A &= B.  Return true if A changed.  */
    1423                 :             : 
    1424                 :             : bool
    1425                 :   925345076 : bitmap_and_into (bitmap a, const_bitmap b)
    1426                 :             : {
    1427                 :   925345076 :   bitmap_element *a_elt = a->first;
    1428                 :   925345076 :   const bitmap_element *b_elt = b->first;
    1429                 :   925345076 :   bitmap_element *next;
    1430                 :   925345076 :   bool changed = false;
    1431                 :             : 
    1432                 :   925345076 :   gcc_checking_assert (!a->tree_form && !b->tree_form);
    1433                 :             : 
    1434                 :   925345076 :   if (a == b)
    1435                 :             :     return false;
    1436                 :             : 
    1437                 :  2696563051 :   while (a_elt && b_elt)
    1438                 :             :     {
    1439                 :  1771217975 :       if (a_elt->indx < b_elt->indx)
    1440                 :             :         {
    1441                 :    40664259 :           next = a_elt->next;
    1442                 :    40664259 :           bitmap_list_unlink_element (a, a_elt);
    1443                 :    40664259 :           a_elt = next;
    1444                 :    40664259 :           changed = true;
    1445                 :             :         }
    1446                 :  1730553716 :       else if (b_elt->indx < a_elt->indx)
    1447                 :    50184727 :         b_elt = b_elt->next;
    1448                 :             :       else
    1449                 :             :         {
    1450                 :             :           /* Matching elts, generate A &= B.  */
    1451                 :             :           unsigned ix;
    1452                 :             :           BITMAP_WORD ior = 0;
    1453                 :             : 
    1454                 :  5041106967 :           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
    1455                 :             :             {
    1456                 :  3360737978 :               BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
    1457                 :  3360737978 :               if (a_elt->bits[ix] != r)
    1458                 :   342838981 :                 changed = true;
    1459                 :  3360737978 :               a_elt->bits[ix] = r;
    1460                 :  3360737978 :               ior |= r;
    1461                 :             :             }
    1462                 :  1680368989 :           next = a_elt->next;
    1463                 :  1680368989 :           if (!ior)
    1464                 :     5855010 :             bitmap_list_unlink_element (a, a_elt);
    1465                 :  1680368989 :           a_elt = next;
    1466                 :  1680368989 :           b_elt = b_elt->next;
    1467                 :             :         }
    1468                 :             :     }
    1469                 :             : 
    1470                 :   925345076 :   if (a_elt)
    1471                 :             :     {
    1472                 :    52887363 :       changed = true;
    1473                 :    52887363 :       bitmap_elt_clear_from (a, a_elt);
    1474                 :             :     }
    1475                 :             : 
    1476                 :   925345076 :   gcc_checking_assert (!a->current == !a->first
    1477                 :             :                        && (!a->current || a->indx == a->current->indx));
    1478                 :             : 
    1479                 :             :   return changed;
    1480                 :             : }
    1481                 :             : 
    1482                 :             : 
    1483                 :             : /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
    1484                 :             :    if non-NULL.  CHANGED is true if the destination bitmap had already been
    1485                 :             :    changed; the new value of CHANGED is returned.  */
    1486                 :             : 
    1487                 :             : static inline bool
    1488                 :  3030369848 : bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
    1489                 :             :                  const bitmap_element *src_elt, bool changed)
    1490                 :             : {
    1491                 :  3030369848 :   if (!changed && dst_elt && dst_elt->indx == src_elt->indx)
    1492                 :             :     {
    1493                 :             :       unsigned ix;
    1494                 :             : 
    1495                 :   283302990 :       for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
    1496                 :   188868660 :         if (src_elt->bits[ix] != dst_elt->bits[ix])
    1497                 :             :           {
    1498                 :    27987445 :             dst_elt->bits[ix] = src_elt->bits[ix];
    1499                 :    27987445 :             changed = true;
    1500                 :             :           }
    1501                 :             :     }
    1502                 :             :   else
    1503                 :             :     {
    1504                 :  3028044113 :       changed = true;
    1505                 :  2875186302 :       if (!dst_elt)
    1506                 :  2783077707 :         dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
    1507                 :  2783077707 :                                                     src_elt->indx);
    1508                 :             :       else
    1509                 :   152857811 :         dst_elt->indx = src_elt->indx;
    1510                 :  2935935518 :       memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits));
    1511                 :             :     }
    1512                 :  3030369848 :   return changed;
    1513                 :             : }
    1514                 :             : 
    1515                 :             : 
    1516                 :             : 
    1517                 :             : /* DST = A & ~B  */
    1518                 :             : 
    1519                 :             : bool
    1520                 :   180311108 : bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b)
    1521                 :             : {
    1522                 :   180311108 :   bitmap_element *dst_elt = dst->first;
    1523                 :   180311108 :   const bitmap_element *a_elt = a->first;
    1524                 :   180311108 :   const bitmap_element *b_elt = b->first;
    1525                 :   180311108 :   bitmap_element *dst_prev = NULL;
    1526                 :   180311108 :   bitmap_element **dst_prev_pnext = &dst->first;
    1527                 :   180311108 :   bool changed = false;
    1528                 :             : 
    1529                 :   180311108 :   gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
    1530                 :   180311108 :   gcc_assert (dst != a && dst != b);
    1531                 :             : 
    1532                 :   180311108 :   if (a == b)
    1533                 :             :     {
    1534                 :           0 :       changed = !bitmap_empty_p (dst);
    1535                 :           0 :       bitmap_clear (dst);
    1536                 :           0 :       return changed;
    1537                 :             :     }
    1538                 :             : 
    1539                 :   513234460 :   while (a_elt)
    1540                 :             :     {
    1541                 :   347079923 :       while (b_elt && b_elt->indx < a_elt->indx)
    1542                 :    14156571 :         b_elt = b_elt->next;
    1543                 :             : 
    1544                 :   332923352 :       if (!b_elt || b_elt->indx > a_elt->indx)
    1545                 :             :         {
    1546                 :   173723033 :           changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed);
    1547                 :   173723033 :           dst_prev = *dst_prev_pnext;
    1548                 :   173723033 :           dst_prev_pnext = &dst_prev->next;
    1549                 :   173723033 :           dst_elt = *dst_prev_pnext;
    1550                 :   173723033 :           a_elt = a_elt->next;
    1551                 :             :         }
    1552                 :             : 
    1553                 :             :       else
    1554                 :             :         {
    1555                 :             :           /* Matching elts, generate A & ~B.  */
    1556                 :   159200319 :           unsigned ix;
    1557                 :   159200319 :           BITMAP_WORD ior = 0;
    1558                 :             : 
    1559                 :   159200319 :           if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
    1560                 :             :             {
    1561                 :   124314801 :               for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
    1562                 :             :                 {
    1563                 :    82876534 :                   BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
    1564                 :             : 
    1565                 :    82876534 :                   if (dst_elt->bits[ix] != r)
    1566                 :             :                     {
    1567                 :    28121811 :                       changed = true;
    1568                 :    28121811 :                       dst_elt->bits[ix] = r;
    1569                 :             :                     }
    1570                 :    82876534 :                   ior |= r;
    1571                 :             :                 }
    1572                 :             :             }
    1573                 :             :           else
    1574                 :             :             {
    1575                 :   101496969 :               bool new_element;
    1576                 :   117762052 :               if (!dst_elt || dst_elt->indx > a_elt->indx)
    1577                 :             :                 {
    1578                 :   116615577 :                   dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
    1579                 :             :                                                               a_elt->indx);
    1580                 :   116615577 :                   new_element = true;
    1581                 :             :                 }
    1582                 :             :               else
    1583                 :             :                 {
    1584                 :     1146475 :                   dst_elt->indx = a_elt->indx;
    1585                 :     1146475 :                   new_element = false;
    1586                 :             :                 }
    1587                 :             : 
    1588                 :   353286156 :               for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
    1589                 :             :                 {
    1590                 :   235524104 :                   BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
    1591                 :             : 
    1592                 :   235524104 :                   dst_elt->bits[ix] = r;
    1593                 :   235524104 :                   ior |= r;
    1594                 :             :                 }
    1595                 :             : 
    1596                 :   117762052 :               if (ior)
    1597                 :             :                 changed = true;
    1598                 :             :               else
    1599                 :             :                 {
    1600                 :    42032013 :                   changed |= !new_element;
    1601                 :    42032013 :                   bitmap_list_unlink_element (dst, dst_elt);
    1602                 :    42032013 :                   dst_elt = *dst_prev_pnext;
    1603                 :             :                 }
    1604                 :             :             }
    1605                 :             : 
    1606                 :    83470280 :           if (ior)
    1607                 :             :             {
    1608                 :   116239796 :               dst_prev = *dst_prev_pnext;
    1609                 :   116239796 :               dst_prev_pnext = &dst_prev->next;
    1610                 :   116239796 :               dst_elt = *dst_prev_pnext;
    1611                 :             :             }
    1612                 :   159200319 :           a_elt = a_elt->next;
    1613                 :   159200319 :           b_elt = b_elt->next;
    1614                 :             :         }
    1615                 :             :     }
    1616                 :             : 
    1617                 :             :   /* Ensure that dst->current is valid.  */
    1618                 :   180311108 :   dst->current = dst->first;
    1619                 :             : 
    1620                 :   180311108 :   if (dst_elt)
    1621                 :             :     {
    1622                 :     1730903 :       changed = true;
    1623                 :     1730903 :       bitmap_elt_clear_from (dst, dst_elt);
    1624                 :             :     }
    1625                 :   180311108 :   gcc_checking_assert (!dst->current == !dst->first);
    1626                 :   180311108 :   if (dst->current)
    1627                 :   133737254 :     dst->indx = dst->current->indx;
    1628                 :             : 
    1629                 :             :   return changed;
    1630                 :             : }
    1631                 :             : 
    1632                 :             : /* A &= ~B. Returns true if A changes */
    1633                 :             : 
    1634                 :             : bool
    1635                 :   349920338 : bitmap_and_compl_into (bitmap a, const_bitmap b)
    1636                 :             : {
    1637                 :   349920338 :   bitmap_element *a_elt = a->first;
    1638                 :   349920338 :   const bitmap_element *b_elt = b->first;
    1639                 :   349920338 :   bitmap_element *next;
    1640                 :   349920338 :   BITMAP_WORD changed = 0;
    1641                 :             : 
    1642                 :   349920338 :   gcc_checking_assert (!a->tree_form && !b->tree_form);
    1643                 :             : 
    1644                 :   349920338 :   if (a == b)
    1645                 :             :     {
    1646                 :           0 :       if (bitmap_empty_p (a))
    1647                 :             :         return false;
    1648                 :             :       else
    1649                 :             :         {
    1650                 :           0 :           bitmap_clear (a);
    1651                 :           0 :           return true;
    1652                 :             :         }
    1653                 :             :     }
    1654                 :             : 
    1655                 :  1065719880 :   while (a_elt && b_elt)
    1656                 :             :     {
    1657                 :   715799542 :       if (a_elt->indx < b_elt->indx)
    1658                 :   150030966 :         a_elt = a_elt->next;
    1659                 :   565768576 :       else if (b_elt->indx < a_elt->indx)
    1660                 :   304258210 :         b_elt = b_elt->next;
    1661                 :             :       else
    1662                 :             :         {
    1663                 :             :           /* Matching elts, generate A &= ~B.  */
    1664                 :             :           unsigned ix;
    1665                 :             :           BITMAP_WORD ior = 0;
    1666                 :             : 
    1667                 :   784531098 :           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
    1668                 :             :             {
    1669                 :   523020732 :               BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
    1670                 :   523020732 :               BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
    1671                 :             : 
    1672                 :   523020732 :               a_elt->bits[ix] = r;
    1673                 :   523020732 :               changed |= cleared;
    1674                 :   523020732 :               ior |= r;
    1675                 :             :             }
    1676                 :   261510366 :           next = a_elt->next;
    1677                 :   261510366 :           if (!ior)
    1678                 :    12349159 :             bitmap_list_unlink_element (a, a_elt);
    1679                 :   261510366 :           a_elt = next;
    1680                 :   261510366 :           b_elt = b_elt->next;
    1681                 :             :         }
    1682                 :             :     }
    1683                 :   349920338 :   gcc_checking_assert (!a->current == !a->first
    1684                 :             :                        && (!a->current || a->indx == a->current->indx));
    1685                 :   349920338 :   return changed != 0;
    1686                 :             : }
    1687                 :             : 
    1688                 :             : /* Set COUNT bits from START in HEAD.  */
    1689                 :             : void
    1690                 :  1617519168 : bitmap_set_range (bitmap head, unsigned int start, unsigned int count)
    1691                 :             : {
    1692                 :  1617519168 :   unsigned int first_index, end_bit_plus1, last_index;
    1693                 :  1617519168 :   bitmap_element *elt, *elt_prev;
    1694                 :  1617519168 :   unsigned int i;
    1695                 :             : 
    1696                 :  1617519168 :   gcc_checking_assert (!head->tree_form);
    1697                 :             : 
    1698                 :  1617519168 :   if (!count)
    1699                 :             :     return;
    1700                 :             : 
    1701                 :  1298697479 :   if (count == 1)
    1702                 :             :     {
    1703                 :   582099909 :       bitmap_set_bit (head, start);
    1704                 :   582099909 :       return;
    1705                 :             :     }
    1706                 :             : 
    1707                 :   716597570 :   first_index = start / BITMAP_ELEMENT_ALL_BITS;
    1708                 :   716597570 :   end_bit_plus1 = start + count;
    1709                 :   716597570 :   last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
    1710                 :   716597570 :   elt = bitmap_list_find_element (head, first_index);
    1711                 :             : 
    1712                 :             :   /* If bitmap_list_find_element returns zero, the current is the closest block
    1713                 :             :      to the result.  Otherwise, just use bitmap_element_allocate to
    1714                 :             :      ensure ELT is set; in the loop below, ELT == NULL means "insert
    1715                 :             :      at the end of the bitmap".  */
    1716                 :   716597570 :   if (!elt)
    1717                 :             :     {
    1718                 :   136349509 :       elt = bitmap_element_allocate (head);
    1719                 :   136349509 :       elt->indx = first_index;
    1720                 :   136349509 :       bitmap_list_link_element (head, elt);
    1721                 :             :     }
    1722                 :             : 
    1723                 :   716597570 :   gcc_checking_assert (elt->indx == first_index);
    1724                 :   716597570 :   elt_prev = elt->prev;
    1725                 :  1487438114 :   for (i = first_index; i <= last_index; i++)
    1726                 :             :     {
    1727                 :   770840544 :       unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS;
    1728                 :   770840544 :       unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
    1729                 :             : 
    1730                 :   770840544 :       unsigned int first_word_to_mod;
    1731                 :   770840544 :       BITMAP_WORD first_mask;
    1732                 :   770840544 :       unsigned int last_word_to_mod;
    1733                 :   770840544 :       BITMAP_WORD last_mask;
    1734                 :   770840544 :       unsigned int ix;
    1735                 :             : 
    1736                 :   770840544 :       if (!elt || elt->indx != i)
    1737                 :    54017857 :         elt = bitmap_list_insert_element_after (head, elt_prev, i);
    1738                 :             : 
    1739                 :   770840544 :       if (elt_start_bit <= start)
    1740                 :             :         {
    1741                 :             :           /* The first bit to turn on is somewhere inside this
    1742                 :             :              elt.  */
    1743                 :   716597570 :           first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
    1744                 :             : 
    1745                 :             :           /* This mask should have 1s in all bits >= start position. */
    1746                 :   716597570 :           first_mask =
    1747                 :   716597570 :             (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
    1748                 :   716597570 :           first_mask = ~first_mask;
    1749                 :             :         }
    1750                 :             :       else
    1751                 :             :         {
    1752                 :             :           /* The first bit to turn on is below this start of this elt.  */
    1753                 :             :           first_word_to_mod = 0;
    1754                 :             :           first_mask = ~(BITMAP_WORD) 0;
    1755                 :             :         }
    1756                 :             : 
    1757                 :   770840544 :       if (elt_end_bit_plus1 <= end_bit_plus1)
    1758                 :             :         {
    1759                 :             :           /* The last bit to turn on is beyond this elt.  */
    1760                 :             :           last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
    1761                 :             :           last_mask = ~(BITMAP_WORD) 0;
    1762                 :             :         }
    1763                 :             :       else
    1764                 :             :         {
    1765                 :             :           /* The last bit to turn on is inside to this elt.  */
    1766                 :   712287150 :           last_word_to_mod =
    1767                 :   712287150 :             (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
    1768                 :             : 
    1769                 :             :           /* The last mask should have 1s below the end bit.  */
    1770                 :   712287150 :           last_mask =
    1771                 :   712287150 :             (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1;
    1772                 :             :         }
    1773                 :             : 
    1774                 :   770840544 :       if (first_word_to_mod == last_word_to_mod)
    1775                 :             :         {
    1776                 :   703042590 :           BITMAP_WORD mask = first_mask & last_mask;
    1777                 :   703042590 :           elt->bits[first_word_to_mod] |= mask;
    1778                 :             :         }
    1779                 :             :       else
    1780                 :             :         {
    1781                 :    67797954 :           elt->bits[first_word_to_mod] |= first_mask;
    1782                 :    67797954 :           if (BITMAP_ELEMENT_WORDS > 2)
    1783                 :             :             for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++)
    1784                 :             :               elt->bits[ix] = ~(BITMAP_WORD) 0;
    1785                 :    67797954 :           elt->bits[last_word_to_mod] |= last_mask;
    1786                 :             :         }
    1787                 :             : 
    1788                 :   770840544 :       elt_prev = elt;
    1789                 :   770840544 :       elt = elt->next;
    1790                 :             :     }
    1791                 :             : 
    1792                 :   716597570 :   head->current = elt ? elt : elt_prev;
    1793                 :   716597570 :   head->indx = head->current->indx;
    1794                 :             : }
    1795                 :             : 
    1796                 :             : /* Clear COUNT bits from START in HEAD.  */
    1797                 :             : void
    1798                 :  2767747101 : bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
    1799                 :             : {
    1800                 :  2767747101 :   unsigned int first_index, end_bit_plus1, last_index;
    1801                 :  2767747101 :   bitmap_element *elt;
    1802                 :             : 
    1803                 :  2767747101 :   gcc_checking_assert (!head->tree_form);
    1804                 :             : 
    1805                 :  2767747101 :   if (!count)
    1806                 :             :     return;
    1807                 :             : 
    1808                 :  2767746730 :   if (count == 1)
    1809                 :             :     {
    1810                 :   411148688 :       bitmap_clear_bit (head, start);
    1811                 :   411148688 :       return;
    1812                 :             :     }
    1813                 :             : 
    1814                 :  2356598042 :   first_index = start / BITMAP_ELEMENT_ALL_BITS;
    1815                 :  2356598042 :   end_bit_plus1 = start + count;
    1816                 :  2356598042 :   last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
    1817                 :  2356598042 :   elt = bitmap_list_find_element (head, first_index);
    1818                 :             : 
    1819                 :             :   /* If bitmap_list_find_element returns zero, the current is the closest block
    1820                 :             :      to the result.  If the current is less than first index, find the
    1821                 :             :      next one.  Otherwise, just set elt to be current.  */
    1822                 :  2356598042 :   if (!elt)
    1823                 :             :     {
    1824                 :  1623111958 :       if (head->current)
    1825                 :             :         {
    1826                 :  1567937780 :           if (head->indx < first_index)
    1827                 :             :             {
    1828                 :  1115757185 :               elt = head->current->next;
    1829                 :  1115757185 :               if (!elt)
    1830                 :             :                 return;
    1831                 :             :             }
    1832                 :             :           else
    1833                 :             :             elt = head->current;
    1834                 :             :         }
    1835                 :             :       else
    1836                 :             :         return;
    1837                 :             :     }
    1838                 :             : 
    1839                 :  2604743274 :   while (elt && (elt->indx <= last_index))
    1840                 :             :     {
    1841                 :   884375991 :       bitmap_element * next_elt = elt->next;
    1842                 :   884375991 :       unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
    1843                 :   884375991 :       unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
    1844                 :             : 
    1845                 :             : 
    1846                 :   884375991 :       if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
    1847                 :             :         /* Get rid of the entire elt and go to the next one.  */
    1848                 :    48348962 :         bitmap_list_unlink_element (head, elt);
    1849                 :             :       else
    1850                 :             :         {
    1851                 :             :           /* Going to have to knock out some bits in this elt.  */
    1852                 :   836027029 :           unsigned int first_word_to_mod;
    1853                 :   836027029 :           BITMAP_WORD first_mask;
    1854                 :   836027029 :           unsigned int last_word_to_mod;
    1855                 :   836027029 :           BITMAP_WORD last_mask;
    1856                 :   836027029 :           unsigned int i;
    1857                 :   836027029 :           bool clear = true;
    1858                 :             : 
    1859                 :   836027029 :           if (elt_start_bit <= start)
    1860                 :             :             {
    1861                 :             :               /* The first bit to turn off is somewhere inside this
    1862                 :             :                  elt.  */
    1863                 :   731485484 :               first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
    1864                 :             : 
    1865                 :             :               /* This mask should have 1s in all bits >= start position. */
    1866                 :   731485484 :               first_mask =
    1867                 :   731485484 :                 (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
    1868                 :   731485484 :               first_mask = ~first_mask;
    1869                 :             :             }
    1870                 :             :           else
    1871                 :             :             {
    1872                 :             :               /* The first bit to turn off is below this start of this elt.  */
    1873                 :             :               first_word_to_mod = 0;
    1874                 :             :               first_mask = 0;
    1875                 :             :               first_mask = ~first_mask;
    1876                 :             :             }
    1877                 :             : 
    1878                 :   836027029 :           if (elt_end_bit_plus1 <= end_bit_plus1)
    1879                 :             :             {
    1880                 :             :               /* The last bit to turn off is beyond this elt.  */
    1881                 :             :               last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
    1882                 :             :               last_mask = 0;
    1883                 :             :               last_mask = ~last_mask;
    1884                 :             :             }
    1885                 :             :           else
    1886                 :             :             {
    1887                 :             :               /* The last bit to turn off is inside to this elt.  */
    1888                 :   696871353 :               last_word_to_mod =
    1889                 :   696871353 :                 (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
    1890                 :             : 
    1891                 :             :               /* The last mask should have 1s below the end bit.  */
    1892                 :   696871353 :               last_mask =
    1893                 :   696871353 :                 (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
    1894                 :             :             }
    1895                 :             : 
    1896                 :             : 
    1897                 :   836027029 :           if (first_word_to_mod == last_word_to_mod)
    1898                 :             :             {
    1899                 :   694893391 :               BITMAP_WORD mask = first_mask & last_mask;
    1900                 :   694893391 :               elt->bits[first_word_to_mod] &= ~mask;
    1901                 :             :             }
    1902                 :             :           else
    1903                 :             :             {
    1904                 :   141133638 :               elt->bits[first_word_to_mod] &= ~first_mask;
    1905                 :   141133638 :               if (BITMAP_ELEMENT_WORDS > 2)
    1906                 :             :                 for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
    1907                 :             :                   elt->bits[i] = 0;
    1908                 :   141133638 :               elt->bits[last_word_to_mod] &= ~last_mask;
    1909                 :             :             }
    1910                 :  1120706772 :           for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
    1911                 :  1080439071 :             if (elt->bits[i])
    1912                 :             :               {
    1913                 :             :                 clear = false;
    1914                 :             :                 break;
    1915                 :             :               }
    1916                 :             :           /* Check to see if there are any bits left.  */
    1917                 :   836027029 :           if (clear)
    1918                 :    40267701 :             bitmap_list_unlink_element (head, elt);
    1919                 :             :         }
    1920                 :             :       elt = next_elt;
    1921                 :             :     }
    1922                 :             : 
    1923                 :  1720367283 :   if (elt)
    1924                 :             :     {
    1925                 :  1357080398 :       head->current = elt;
    1926                 :  1357080398 :       head->indx = head->current->indx;
    1927                 :             :     }
    1928                 :             : }
    1929                 :             : 
    1930                 :             : /* A = ~A & B. */
    1931                 :             : 
    1932                 :             : void
    1933                 :           0 : bitmap_compl_and_into (bitmap a, const_bitmap b)
    1934                 :             : {
    1935                 :           0 :   bitmap_element *a_elt = a->first;
    1936                 :           0 :   const bitmap_element *b_elt = b->first;
    1937                 :           0 :   bitmap_element *a_prev = NULL;
    1938                 :           0 :   bitmap_element *next;
    1939                 :             : 
    1940                 :           0 :   gcc_checking_assert (!a->tree_form && !b->tree_form);
    1941                 :           0 :   gcc_assert (a != b);
    1942                 :             : 
    1943                 :           0 :   if (bitmap_empty_p (a))
    1944                 :             :     {
    1945                 :           0 :       bitmap_copy (a, b);
    1946                 :           0 :       return;
    1947                 :             :     }
    1948                 :           0 :   if (bitmap_empty_p (b))
    1949                 :             :     {
    1950                 :           0 :       bitmap_clear (a);
    1951                 :           0 :       return;
    1952                 :             :     }
    1953                 :             : 
    1954                 :           0 :   while (a_elt || b_elt)
    1955                 :             :     {
    1956                 :           0 :       if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
    1957                 :             :         {
    1958                 :             :           /* A is before B.  Remove A */
    1959                 :           0 :           next = a_elt->next;
    1960                 :           0 :           a_prev = a_elt->prev;
    1961                 :           0 :           bitmap_list_unlink_element (a, a_elt);
    1962                 :           0 :           a_elt = next;
    1963                 :             :         }
    1964                 :           0 :       else if (!a_elt || b_elt->indx < a_elt->indx)
    1965                 :             :         {
    1966                 :             :           /* B is before A.  Copy B. */
    1967                 :           0 :           next = bitmap_list_insert_element_after (a, a_prev, b_elt->indx);
    1968                 :           0 :           memcpy (next->bits, b_elt->bits, sizeof (next->bits));
    1969                 :           0 :           a_prev = next;
    1970                 :           0 :           b_elt = b_elt->next;
    1971                 :             :         }
    1972                 :             :       else
    1973                 :             :         {
    1974                 :             :           /* Matching elts, generate A = ~A & B.  */
    1975                 :             :           unsigned ix;
    1976                 :             :           BITMAP_WORD ior = 0;
    1977                 :             : 
    1978                 :           0 :           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
    1979                 :             :             {
    1980                 :           0 :               BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
    1981                 :           0 :               BITMAP_WORD r = b_elt->bits[ix] ^ cleared;
    1982                 :             : 
    1983                 :           0 :               a_elt->bits[ix] = r;
    1984                 :           0 :               ior |= r;
    1985                 :             :             }
    1986                 :           0 :           next = a_elt->next;
    1987                 :           0 :           if (!ior)
    1988                 :           0 :             bitmap_list_unlink_element (a, a_elt);
    1989                 :             :           else
    1990                 :             :             a_prev = a_elt;
    1991                 :           0 :           a_elt = next;
    1992                 :           0 :           b_elt = b_elt->next;
    1993                 :             :         }
    1994                 :             :     }
    1995                 :           0 :   gcc_checking_assert (!a->current == !a->first
    1996                 :             :                        && (!a->current || a->indx == a->current->indx));
    1997                 :             :   return;
    1998                 :             : }
    1999                 :             : 
    2000                 :             : 
    2001                 :             : /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
    2002                 :             :    overwriting DST_ELT if non-NULL.  CHANGED is true if the destination bitmap
    2003                 :             :    had already been changed; the new value of CHANGED is returned.  */
    2004                 :             : 
    2005                 :             : static inline bool
    2006                 :  6456601483 : bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
    2007                 :             :                 const bitmap_element *a_elt, const bitmap_element *b_elt,
    2008                 :             :                 bool changed)
    2009                 :             : {
    2010                 :  6456601483 :   gcc_assert (a_elt || b_elt);
    2011                 :             : 
    2012                 :  6456601483 :   if (a_elt && b_elt && a_elt->indx == b_elt->indx)
    2013                 :             :     {
    2014                 :             :       /* Matching elts, generate A | B.  */
    2015                 :  3695063480 :       unsigned ix;
    2016                 :             : 
    2017                 :  3695063480 :       if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
    2018                 :             :         {
    2019                 :  9702479634 :           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
    2020                 :             :             {
    2021                 :  6468319756 :               BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
    2022                 :  6468319756 :               if (r != dst_elt->bits[ix])
    2023                 :             :                 {
    2024                 :  1105961408 :                   dst_elt->bits[ix] = r;
    2025                 :  1105961408 :                   changed = true;
    2026                 :             :                 }
    2027                 :             :             }
    2028                 :             :         }
    2029                 :             :       else
    2030                 :             :         {
    2031                 :   799348722 :           changed = true;
    2032                 :   460253121 :           if (!dst_elt)
    2033                 :   121808001 :             dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
    2034                 :             :                                                         a_elt->indx);
    2035                 :             :           else
    2036                 :   339095601 :             dst_elt->indx = a_elt->indx;
    2037                 :  1382710806 :           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
    2038                 :             :             {
    2039                 :   921807204 :               BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
    2040                 :   921807204 :               dst_elt->bits[ix] = r;
    2041                 :             :             }
    2042                 :             :         }
    2043                 :             :     }
    2044                 :             :   else
    2045                 :             :     {
    2046                 :             :       /* Copy a single element.  */
    2047                 :  2546495893 :       const bitmap_element *src;
    2048                 :             : 
    2049                 :  2761538003 :       if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
    2050                 :             :         src = a_elt;
    2051                 :             :       else
    2052                 :   174342601 :         src = b_elt;
    2053                 :             : 
    2054                 :  2720838494 :       gcc_checking_assert (src);
    2055                 :  2761538003 :       changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed);
    2056                 :             :     }
    2057                 :  6456601483 :   return changed;
    2058                 :             : }
    2059                 :             : 
    2060                 :             : 
    2061                 :             : /* DST = A | B.  Return true if DST changes.  */
    2062                 :             : 
    2063                 :             : bool
    2064                 :   305105766 : bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b)
    2065                 :             : {
    2066                 :   305105766 :   bitmap_element *dst_elt = dst->first;
    2067                 :   305105766 :   const bitmap_element *a_elt = a->first;
    2068                 :   305105766 :   const bitmap_element *b_elt = b->first;
    2069                 :   305105766 :   bitmap_element *dst_prev = NULL;
    2070                 :   305105766 :   bitmap_element **dst_prev_pnext = &dst->first;
    2071                 :   305105766 :   bool changed = false;
    2072                 :             : 
    2073                 :   305105766 :   gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
    2074                 :   305105766 :   gcc_assert (dst != a && dst != b);
    2075                 :             : 
    2076                 :   850424062 :   while (a_elt || b_elt)
    2077                 :             :     {
    2078                 :   545318296 :       changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed);
    2079                 :             : 
    2080                 :   545318296 :       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
    2081                 :             :         {
    2082                 :   187578854 :           a_elt = a_elt->next;
    2083                 :   187578854 :           b_elt = b_elt->next;
    2084                 :             :         }
    2085                 :             :       else
    2086                 :             :         {
    2087                 :   357739442 :           if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
    2088                 :    31129986 :             a_elt = a_elt->next;
    2089                 :   326609456 :           else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
    2090                 :   326609456 :             b_elt = b_elt->next;
    2091                 :             :         }
    2092                 :             : 
    2093                 :   545318296 :       dst_prev = *dst_prev_pnext;
    2094                 :   545318296 :       dst_prev_pnext = &dst_prev->next;
    2095                 :   545318296 :       dst_elt = *dst_prev_pnext;
    2096                 :             :     }
    2097                 :             : 
    2098                 :   305105766 :   if (dst_elt)
    2099                 :             :     {
    2100                 :        6142 :       changed = true;
    2101                 :             :       /* Ensure that dst->current is valid.  */
    2102                 :        6142 :       dst->current = dst->first;
    2103                 :        6142 :       bitmap_elt_clear_from (dst, dst_elt);
    2104                 :             :     }
    2105                 :   305105766 :   gcc_checking_assert (!dst->current == !dst->first);
    2106                 :   305105766 :   if (dst->current)
    2107                 :   303846902 :     dst->indx = dst->current->indx;
    2108                 :   305105766 :   return changed;
    2109                 :             : }
    2110                 :             : 
    2111                 :             : /* A |= B.  Return true if A changes.  */
    2112                 :             : 
    2113                 :             : bool
    2114                 :  4156938150 : bitmap_ior_into (bitmap a, const_bitmap b)
    2115                 :             : {
    2116                 :  4156938150 :   bitmap_element *a_elt = a->first;
    2117                 :  4156938150 :   const bitmap_element *b_elt = b->first;
    2118                 :  4156938150 :   bitmap_element *a_prev = NULL;
    2119                 :  4156938150 :   bitmap_element **a_prev_pnext = &a->first;
    2120                 :  4156938150 :   bool changed = false;
    2121                 :             : 
    2122                 :  4156938150 :   gcc_checking_assert (!a->tree_form && !b->tree_form);
    2123                 :  4156938150 :   if (a == b)
    2124                 :             :     return false;
    2125                 :             : 
    2126                 :  9790256250 :   while (b_elt)
    2127                 :             :     {
    2128                 :             :       /* If A lags behind B, just advance it.  */
    2129                 :  5633321537 :       if (!a_elt || a_elt->indx == b_elt->indx)
    2130                 :             :         {
    2131                 :  4881368828 :           changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
    2132                 :  4881368828 :           b_elt = b_elt->next;
    2133                 :             :         }
    2134                 :   751952709 :       else if (a_elt->indx > b_elt->indx)
    2135                 :             :         {
    2136                 :    93832274 :           changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed);
    2137                 :    93832274 :           b_elt = b_elt->next;
    2138                 :             :         }
    2139                 :             : 
    2140                 :  5633321537 :       a_prev = *a_prev_pnext;
    2141                 :  5633321537 :       a_prev_pnext = &a_prev->next;
    2142                 :  5633321537 :       a_elt = *a_prev_pnext;
    2143                 :             :     }
    2144                 :             : 
    2145                 :  4156934713 :   gcc_checking_assert (!a->current == !a->first);
    2146                 :  4156934713 :   if (a->current)
    2147                 :  3862832944 :     a->indx = a->current->indx;
    2148                 :             :   return changed;
    2149                 :             : }
    2150                 :             : 
    2151                 :             : /* A |= B.  Return true if A changes.  Free B (re-using its storage
    2152                 :             :    for the result).  */
    2153                 :             : 
    2154                 :             : bool
    2155                 :    11266727 : bitmap_ior_into_and_free (bitmap a, bitmap *b_)
    2156                 :             : {
    2157                 :    11266727 :   bitmap b = *b_;
    2158                 :    11266727 :   bitmap_element *a_elt = a->first;
    2159                 :    11266727 :   bitmap_element *b_elt = b->first;
    2160                 :    11266727 :   bitmap_element *a_prev = NULL;
    2161                 :    11266727 :   bitmap_element **a_prev_pnext = &a->first;
    2162                 :    11266727 :   bool changed = false;
    2163                 :             : 
    2164                 :    11266727 :   gcc_checking_assert (!a->tree_form && !b->tree_form);
    2165                 :    11266727 :   gcc_assert (a->obstack == b->obstack);
    2166                 :    11266727 :   if (a == b)
    2167                 :             :     return false;
    2168                 :             : 
    2169                 :    37878391 :   while (b_elt)
    2170                 :             :     {
    2171                 :             :       /* If A lags behind B, just advance it.  */
    2172                 :    26611664 :       if (!a_elt || a_elt->indx == b_elt->indx)
    2173                 :             :         {
    2174                 :    16416089 :           changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
    2175                 :    16416089 :           b_elt = b_elt->next;
    2176                 :             :         }
    2177                 :    10195575 :       else if (a_elt->indx > b_elt->indx)
    2178                 :             :         {
    2179                 :     4532235 :           bitmap_element *b_elt_next = b_elt->next;
    2180                 :     4532235 :           bitmap_list_unlink_element (b, b_elt, false);
    2181                 :     4532235 :           bitmap_list_insert_element_after (a, a_prev, b_elt->indx, b_elt);
    2182                 :     4532235 :           b_elt = b_elt_next;
    2183                 :             :         }
    2184                 :             : 
    2185                 :    26611664 :       a_prev = *a_prev_pnext;
    2186                 :    26611664 :       a_prev_pnext = &a_prev->next;
    2187                 :    26611664 :       a_elt = *a_prev_pnext;
    2188                 :             :     }
    2189                 :             : 
    2190                 :    11266727 :   gcc_checking_assert (!a->current == !a->first);
    2191                 :    11266727 :   if (a->current)
    2192                 :    11266727 :     a->indx = a->current->indx;
    2193                 :             : 
    2194                 :    11266727 :   if (b->obstack)
    2195                 :    11266727 :     BITMAP_FREE (*b_);
    2196                 :             :   else
    2197                 :           0 :     bitmap_clear (b);
    2198                 :             :   return changed;
    2199                 :             : }
    2200                 :             : 
    2201                 :             : /* DST = A ^ B  */
    2202                 :             : 
    2203                 :             : void
    2204                 :           0 : bitmap_xor (bitmap dst, const_bitmap a, const_bitmap b)
    2205                 :             : {
    2206                 :           0 :   bitmap_element *dst_elt = dst->first;
    2207                 :           0 :   const bitmap_element *a_elt = a->first;
    2208                 :           0 :   const bitmap_element *b_elt = b->first;
    2209                 :           0 :   bitmap_element *dst_prev = NULL;
    2210                 :             : 
    2211                 :           0 :   gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
    2212                 :           0 :   gcc_assert (dst != a && dst != b);
    2213                 :             : 
    2214                 :           0 :   if (a == b)
    2215                 :             :     {
    2216                 :           0 :       bitmap_clear (dst);
    2217                 :           0 :       return;
    2218                 :             :     }
    2219                 :             : 
    2220                 :           0 :   while (a_elt || b_elt)
    2221                 :             :     {
    2222                 :           0 :       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
    2223                 :             :         {
    2224                 :             :           /* Matching elts, generate A ^ B.  */
    2225                 :           0 :           unsigned ix;
    2226                 :           0 :           BITMAP_WORD ior = 0;
    2227                 :             : 
    2228                 :           0 :           if (!dst_elt)
    2229                 :           0 :             dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
    2230                 :             :                                                         a_elt->indx);
    2231                 :             :           else
    2232                 :           0 :             dst_elt->indx = a_elt->indx;
    2233                 :           0 :           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
    2234                 :             :             {
    2235                 :           0 :               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
    2236                 :             : 
    2237                 :           0 :               ior |= r;
    2238                 :           0 :               dst_elt->bits[ix] = r;
    2239                 :             :             }
    2240                 :           0 :           a_elt = a_elt->next;
    2241                 :           0 :           b_elt = b_elt->next;
    2242                 :           0 :           if (ior)
    2243                 :             :             {
    2244                 :           0 :               dst_prev = dst_elt;
    2245                 :           0 :               dst_elt = dst_elt->next;
    2246                 :             :             }
    2247                 :             :         }
    2248                 :             :       else
    2249                 :             :         {
    2250                 :             :           /* Copy a single element.  */
    2251                 :           0 :           const bitmap_element *src;
    2252                 :             : 
    2253                 :           0 :           if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
    2254                 :             :             {
    2255                 :           0 :               src = a_elt;
    2256                 :           0 :               a_elt = a_elt->next;
    2257                 :             :             }
    2258                 :             :           else
    2259                 :             :             {
    2260                 :           0 :               src = b_elt;
    2261                 :           0 :               b_elt = b_elt->next;
    2262                 :             :             }
    2263                 :             : 
    2264                 :           0 :           if (!dst_elt)
    2265                 :           0 :             dst_elt = bitmap_list_insert_element_after (dst, dst_prev,
    2266                 :           0 :                                                         src->indx);
    2267                 :             :           else
    2268                 :           0 :             dst_elt->indx = src->indx;
    2269                 :           0 :           memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
    2270                 :           0 :           dst_prev = dst_elt;
    2271                 :           0 :           dst_elt = dst_elt->next;
    2272                 :             :         }
    2273                 :             :     }
    2274                 :             :   /* Ensure that dst->current is valid.  */
    2275                 :           0 :   dst->current = dst->first;
    2276                 :           0 :   bitmap_elt_clear_from (dst, dst_elt);
    2277                 :           0 :   gcc_checking_assert (!dst->current == !dst->first);
    2278                 :           0 :   if (dst->current)
    2279                 :           0 :     dst->indx = dst->current->indx;
    2280                 :             : }
    2281                 :             : 
    2282                 :             : /* A ^= B */
    2283                 :             : 
    2284                 :             : void
    2285                 :           0 : bitmap_xor_into (bitmap a, const_bitmap b)
    2286                 :             : {
    2287                 :           0 :   bitmap_element *a_elt = a->first;
    2288                 :           0 :   const bitmap_element *b_elt = b->first;
    2289                 :           0 :   bitmap_element *a_prev = NULL;
    2290                 :             : 
    2291                 :           0 :   gcc_checking_assert (!a->tree_form && !b->tree_form);
    2292                 :             : 
    2293                 :           0 :   if (a == b)
    2294                 :             :     {
    2295                 :           0 :       bitmap_clear (a);
    2296                 :           0 :       return;
    2297                 :             :     }
    2298                 :             : 
    2299                 :           0 :   while (b_elt)
    2300                 :             :     {
    2301                 :           0 :       if (!a_elt || b_elt->indx < a_elt->indx)
    2302                 :             :         {
    2303                 :             :           /* Copy b_elt.  */
    2304                 :           0 :           bitmap_element *dst = bitmap_list_insert_element_after (a, a_prev,
    2305                 :           0 :                                                                   b_elt->indx);
    2306                 :           0 :           memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
    2307                 :           0 :           a_prev = dst;
    2308                 :           0 :           b_elt = b_elt->next;
    2309                 :           0 :         }
    2310                 :           0 :       else if (a_elt->indx < b_elt->indx)
    2311                 :             :         {
    2312                 :           0 :           a_prev = a_elt;
    2313                 :           0 :           a_elt = a_elt->next;
    2314                 :             :         }
    2315                 :             :       else
    2316                 :             :         {
    2317                 :             :           /* Matching elts, generate A ^= B.  */
    2318                 :           0 :           unsigned ix;
    2319                 :           0 :           BITMAP_WORD ior = 0;
    2320                 :           0 :           bitmap_element *next = a_elt->next;
    2321                 :             : 
    2322                 :           0 :           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
    2323                 :             :             {
    2324                 :           0 :               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
    2325                 :             : 
    2326                 :           0 :               ior |= r;
    2327                 :           0 :               a_elt->bits[ix] = r;
    2328                 :             :             }
    2329                 :           0 :           b_elt = b_elt->next;
    2330                 :           0 :           if (ior)
    2331                 :             :             a_prev = a_elt;
    2332                 :             :           else
    2333                 :           0 :             bitmap_list_unlink_element (a, a_elt);
    2334                 :             :           a_elt = next;
    2335                 :             :         }
    2336                 :             :     }
    2337                 :           0 :   gcc_checking_assert (!a->current == !a->first);
    2338                 :           0 :   if (a->current)
    2339                 :           0 :     a->indx = a->current->indx;
    2340                 :             : }
    2341                 :             : 
    2342                 :             : /* Return true if two bitmaps are identical.
    2343                 :             :    We do not bother with a check for pointer equality, as that never
    2344                 :             :    occurs in practice.  */
    2345                 :             : 
    2346                 :             : bool
    2347                 :   472284148 : bitmap_equal_p (const_bitmap a, const_bitmap b)
    2348                 :             : {
    2349                 :   472284148 :   const bitmap_element *a_elt;
    2350                 :   472284148 :   const bitmap_element *b_elt;
    2351                 :   472284148 :   unsigned ix;
    2352                 :             : 
    2353                 :   472284148 :   gcc_checking_assert (!a->tree_form && !b->tree_form);
    2354                 :             : 
    2355                 :   472284148 :   for (a_elt = a->first, b_elt = b->first;
    2356                 :  1049969737 :        a_elt && b_elt;
    2357                 :   577685589 :        a_elt = a_elt->next, b_elt = b_elt->next)
    2358                 :             :     {
    2359                 :   678328593 :       if (a_elt->indx != b_elt->indx)
    2360                 :             :         return false;
    2361                 :  1809887727 :       for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
    2362                 :  1232202138 :         if (a_elt->bits[ix] != b_elt->bits[ix])
    2363                 :             :           return false;
    2364                 :             :     }
    2365                 :   371641144 :   return !a_elt && !b_elt;
    2366                 :             : }
    2367                 :             : 
    2368                 :             : /* Return true if A AND B is not empty.  */
    2369                 :             : 
    2370                 :             : bool
    2371                 :   274494844 : bitmap_intersect_p (const_bitmap a, const_bitmap b)
    2372                 :             : {
    2373                 :   274494844 :   const bitmap_element *a_elt;
    2374                 :   274494844 :   const bitmap_element *b_elt;
    2375                 :   274494844 :   unsigned ix;
    2376                 :             : 
    2377                 :   274494844 :   gcc_checking_assert (!a->tree_form && !b->tree_form);
    2378                 :             : 
    2379                 :   274494844 :   for (a_elt = a->first, b_elt = b->first;
    2380                 :   509917983 :        a_elt && b_elt;)
    2381                 :             :     {
    2382                 :   303392830 :       if (a_elt->indx < b_elt->indx)
    2383                 :   103141484 :         a_elt = a_elt->next;
    2384                 :   200251346 :       else if (b_elt->indx < a_elt->indx)
    2385                 :    40573727 :         b_elt = b_elt->next;
    2386                 :             :       else
    2387                 :             :         {
    2388                 :   365305141 :           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
    2389                 :   273597213 :             if (a_elt->bits[ix] & b_elt->bits[ix])
    2390                 :             :               return true;
    2391                 :    91707928 :           a_elt = a_elt->next;
    2392                 :    91707928 :           b_elt = b_elt->next;
    2393                 :             :         }
    2394                 :             :     }
    2395                 :             :   return false;
    2396                 :             : }
    2397                 :             : 
    2398                 :             : /* Return true if A AND NOT B is not empty.  */
    2399                 :             : 
    2400                 :             : bool
    2401                 :          83 : bitmap_intersect_compl_p (const_bitmap a, const_bitmap b)
    2402                 :             : {
    2403                 :          83 :   const bitmap_element *a_elt;
    2404                 :          83 :   const bitmap_element *b_elt;
    2405                 :          83 :   unsigned ix;
    2406                 :             : 
    2407                 :          83 :   gcc_checking_assert (!a->tree_form && !b->tree_form);
    2408                 :             : 
    2409                 :          83 :   for (a_elt = a->first, b_elt = b->first;
    2410                 :         160 :        a_elt && b_elt;)
    2411                 :             :     {
    2412                 :          83 :       if (a_elt->indx < b_elt->indx)
    2413                 :             :         return true;
    2414                 :          83 :       else if (b_elt->indx < a_elt->indx)
    2415                 :           0 :         b_elt = b_elt->next;
    2416                 :             :       else
    2417                 :             :         {
    2418                 :         237 :           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
    2419                 :         160 :             if (a_elt->bits[ix] & ~b_elt->bits[ix])
    2420                 :             :               return true;
    2421                 :          77 :           a_elt = a_elt->next;
    2422                 :          77 :           b_elt = b_elt->next;
    2423                 :             :         }
    2424                 :             :     }
    2425                 :             :   return a_elt != NULL;
    2426                 :             : }
    2427                 :             : 
    2428                 :             : 
    2429                 :             : /* DST = A | (FROM1 & ~FROM2).  Return true if DST changes.  */
    2430                 :             : 
    2431                 :             : bool
    2432                 :   790803461 : bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill)
    2433                 :             : {
    2434                 :   790803461 :   bool changed = false;
    2435                 :             : 
    2436                 :   790803461 :   bitmap_element *dst_elt = dst->first;
    2437                 :   790803461 :   const bitmap_element *a_elt = a->first;
    2438                 :   790803461 :   const bitmap_element *b_elt = b->first;
    2439                 :   790803461 :   const bitmap_element *kill_elt = kill->first;
    2440                 :   790803461 :   bitmap_element *dst_prev = NULL;
    2441                 :   790803461 :   bitmap_element **dst_prev_pnext = &dst->first;
    2442                 :             : 
    2443                 :   790803461 :   gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form
    2444                 :             :                        && !kill->tree_form);
    2445                 :   790803461 :   gcc_assert (dst != a && dst != b && dst != kill);
    2446                 :             : 
    2447                 :             :   /* Special cases.  We don't bother checking for bitmap_equal_p (b, kill).  */
    2448                 :   790803461 :   if (b == kill || bitmap_empty_p (b))
    2449                 :             :     {
    2450                 :    60693331 :       changed = !bitmap_equal_p (dst, a);
    2451                 :    60693331 :       if (changed)
    2452                 :     3888614 :         bitmap_copy (dst, a);
    2453                 :    60693331 :       return changed;
    2454                 :             :     }
    2455                 :   730110130 :   if (bitmap_empty_p (kill))
    2456                 :   259548052 :     return bitmap_ior (dst, a, b);
    2457                 :   470562078 :   if (bitmap_empty_p (a))
    2458                 :    33556323 :     return bitmap_and_compl (dst, b, kill);
    2459                 :             : 
    2460                 :  1443648787 :   while (a_elt || b_elt)
    2461                 :             :     {
    2462                 :  1006643032 :       bool new_element = false;
    2463                 :             : 
    2464                 :  1006643032 :       if (b_elt)
    2465                 :  1002514845 :         while (kill_elt && kill_elt->indx < b_elt->indx)
    2466                 :    24550384 :           kill_elt = kill_elt->next;
    2467                 :             : 
    2468                 :  1006643032 :       if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
    2469                 :   559189304 :           && (!a_elt || a_elt->indx >= b_elt->indx))
    2470                 :             :         {
    2471                 :   553417520 :           bitmap_element tmp_elt;
    2472                 :   553417520 :           unsigned ix;
    2473                 :             : 
    2474                 :   553417520 :           BITMAP_WORD ior = 0;
    2475                 :   553417520 :           tmp_elt.indx = b_elt->indx;
    2476                 :  1660252560 :           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
    2477                 :             :             {
    2478                 :  1106835040 :               BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix];
    2479                 :  1106835040 :               ior |= r;
    2480                 :  1106835040 :               tmp_elt.bits[ix] = r;
    2481                 :             :             }
    2482                 :             : 
    2483                 :   553417520 :           if (ior)
    2484                 :             :             {
    2485                 :   512788598 :               changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
    2486                 :             :                                         a_elt, &tmp_elt, changed);
    2487                 :   512788598 :               new_element = true;
    2488                 :   512788598 :               if (a_elt && a_elt->indx == b_elt->indx)
    2489                 :   447480044 :                 a_elt = a_elt->next;
    2490                 :             :             }
    2491                 :             : 
    2492                 :   553417520 :           b_elt = b_elt->next;
    2493                 :   553417520 :           kill_elt = kill_elt->next;
    2494                 :             :         }
    2495                 :             :       else
    2496                 :             :         {
    2497                 :   453225512 :           changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
    2498                 :             :                                     a_elt, b_elt, changed);
    2499                 :   453225512 :           new_element = true;
    2500                 :             : 
    2501                 :   453225512 :           if (a_elt && b_elt && a_elt->indx == b_elt->indx)
    2502                 :             :             {
    2503                 :   123401752 :               a_elt = a_elt->next;
    2504                 :   123401752 :               b_elt = b_elt->next;
    2505                 :             :             }
    2506                 :             :           else
    2507                 :             :             {
    2508                 :   329823760 :               if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
    2509                 :    47527520 :                 a_elt = a_elt->next;
    2510                 :   282296240 :               else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
    2511                 :   282296240 :                 b_elt = b_elt->next;
    2512                 :             :             }
    2513                 :             :         }
    2514                 :             : 
    2515                 :  1006643032 :       if (new_element)
    2516                 :             :         {
    2517                 :   966014110 :           dst_prev = *dst_prev_pnext;
    2518                 :   966014110 :           dst_prev_pnext = &dst_prev->next;
    2519                 :   966014110 :           dst_elt = *dst_prev_pnext;
    2520                 :             :         }
    2521                 :             :     }
    2522                 :             : 
    2523                 :   437005755 :   if (dst_elt)
    2524                 :             :     {
    2525                 :        3324 :       changed = true;
    2526                 :             :       /* Ensure that dst->current is valid.  */
    2527                 :        3324 :       dst->current = dst->first;
    2528                 :        3324 :       bitmap_elt_clear_from (dst, dst_elt);
    2529                 :             :     }
    2530                 :   437005755 :   gcc_checking_assert (!dst->current == !dst->first);
    2531                 :   437005755 :   if (dst->current)
    2532                 :   437005755 :     dst->indx = dst->current->indx;
    2533                 :             : 
    2534                 :             :   return changed;
    2535                 :             : }
    2536                 :             : 
    2537                 :             : /* A |= (B & ~C).  Return true if A changes.  */
    2538                 :             : 
    2539                 :             : bool
    2540                 :    51293411 : bitmap_ior_and_compl_into (bitmap a, const_bitmap b, const_bitmap c)
    2541                 :             : {
    2542                 :    51293411 :   bitmap_element *a_elt = a->first;
    2543                 :    51293411 :   const bitmap_element *b_elt = b->first;
    2544                 :    51293411 :   const bitmap_element *c_elt = c->first;
    2545                 :    51293411 :   bitmap_element and_elt;
    2546                 :    51293411 :   bitmap_element *a_prev = NULL;
    2547                 :    51293411 :   bitmap_element **a_prev_pnext = &a->first;
    2548                 :    51293411 :   bool changed = false;
    2549                 :    51293411 :   unsigned ix;
    2550                 :             : 
    2551                 :    51293411 :   gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form);
    2552                 :             : 
    2553                 :    51293411 :   if (a == b)
    2554                 :             :     return false;
    2555                 :    51001017 :   if (bitmap_empty_p (c))
    2556                 :    11319233 :     return bitmap_ior_into (a, b);
    2557                 :    39681784 :   else if (bitmap_empty_p (a))
    2558                 :    20310109 :     return bitmap_and_compl (a, b, c);
    2559                 :             : 
    2560                 :    19371675 :   and_elt.indx = -1;
    2561                 :    62074464 :   while (b_elt)
    2562                 :             :     {
    2563                 :             :       /* Advance C.  */
    2564                 :    53869987 :       while (c_elt && c_elt->indx < b_elt->indx)
    2565                 :    11167198 :         c_elt = c_elt->next;
    2566                 :             : 
    2567                 :    42702789 :       const bitmap_element *and_elt_ptr;
    2568                 :    42702789 :       if (c_elt && c_elt->indx == b_elt->indx)
    2569                 :             :         {
    2570                 :    12831742 :           BITMAP_WORD overall = 0;
    2571                 :    12831742 :           and_elt_ptr = &and_elt;
    2572                 :    12831742 :           and_elt.indx = b_elt->indx;
    2573                 :    38495226 :           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
    2574                 :             :             {
    2575                 :    25663484 :               and_elt.bits[ix] = b_elt->bits[ix] & ~c_elt->bits[ix];
    2576                 :    25663484 :               overall |= and_elt.bits[ix];
    2577                 :             :             }
    2578                 :    12831742 :           if (!overall)
    2579                 :             :             {
    2580                 :     1250333 :               b_elt = b_elt->next;
    2581                 :     1250333 :               continue;
    2582                 :             :             }
    2583                 :             :         }
    2584                 :             :       else
    2585                 :             :         and_elt_ptr = b_elt;
    2586                 :             : 
    2587                 :    41452456 :       b_elt = b_elt->next;
    2588                 :             : 
    2589                 :             :       /* Now find a place to insert AND_ELT.  */
    2590                 :    48341570 :       do
    2591                 :             :         {
    2592                 :    48341570 :           ix = a_elt ? a_elt->indx : and_elt_ptr->indx;
    2593                 :    48341570 :           if (ix == and_elt_ptr->indx)
    2594                 :    40218207 :             changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt,
    2595                 :             :                                       and_elt_ptr, changed);
    2596                 :     8123363 :           else if (ix > and_elt_ptr->indx)
    2597                 :     1234249 :             changed = bitmap_elt_copy (a, NULL, a_prev, and_elt_ptr, changed);
    2598                 :             : 
    2599                 :    48341570 :           a_prev = *a_prev_pnext;
    2600                 :    48341570 :           a_prev_pnext = &a_prev->next;
    2601                 :    48341570 :           a_elt = *a_prev_pnext;
    2602                 :             : 
    2603                 :             :           /* If A lagged behind B/C, we advanced it so loop once more.  */
    2604                 :             :         }
    2605                 :    48341570 :       while (ix < and_elt_ptr->indx);
    2606                 :             :     }
    2607                 :             : 
    2608                 :    19371675 :   gcc_checking_assert (!a->current == !a->first);
    2609                 :    19371675 :   if (a->current)
    2610                 :    19371675 :     a->indx = a->current->indx;
    2611                 :             :   return changed;
    2612                 :             : }
    2613                 :             : 
    2614                 :             : /* A |= (B & C).  Return true if A changes.  */
    2615                 :             : 
    2616                 :             : bool
    2617                 :     7881091 : bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c)
    2618                 :             : {
    2619                 :     7881091 :   bitmap_element *a_elt = a->first;
    2620                 :     7881091 :   const bitmap_element *b_elt = b->first;
    2621                 :     7881091 :   const bitmap_element *c_elt = c->first;
    2622                 :     7881091 :   bitmap_element and_elt;
    2623                 :     7881091 :   bitmap_element *a_prev = NULL;
    2624                 :     7881091 :   bitmap_element **a_prev_pnext = &a->first;
    2625                 :     7881091 :   bool changed = false;
    2626                 :     7881091 :   unsigned ix;
    2627                 :             : 
    2628                 :     7881091 :   gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form);
    2629                 :             : 
    2630                 :     7881091 :   if (b == c)
    2631                 :           0 :     return bitmap_ior_into (a, b);
    2632                 :     7881091 :   if (bitmap_empty_p (b) || bitmap_empty_p (c))
    2633                 :             :     return false;
    2634                 :             : 
    2635                 :     7881087 :   and_elt.indx = -1;
    2636                 :    18199778 :   while (b_elt && c_elt)
    2637                 :             :     {
    2638                 :             :       BITMAP_WORD overall;
    2639                 :             : 
    2640                 :             :       /* Find a common item of B and C.  */
    2641                 :    15104302 :       while (b_elt->indx != c_elt->indx)
    2642                 :             :         {
    2643                 :     4785611 :           if (b_elt->indx < c_elt->indx)
    2644                 :             :             {
    2645                 :      461495 :               b_elt = b_elt->next;
    2646                 :      461495 :               if (!b_elt)
    2647                 :      119480 :                 goto done;
    2648                 :             :             }
    2649                 :             :           else
    2650                 :             :             {
    2651                 :     4324116 :               c_elt = c_elt->next;
    2652                 :     4324116 :               if (!c_elt)
    2653                 :      170429 :                 goto done;
    2654                 :             :             }
    2655                 :             :         }
    2656                 :             : 
    2657                 :    10318691 :       overall = 0;
    2658                 :    10318691 :       and_elt.indx = b_elt->indx;
    2659                 :    30956073 :       for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
    2660                 :             :         {
    2661                 :    20637382 :           and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix];
    2662                 :    20637382 :           overall |= and_elt.bits[ix];
    2663                 :             :         }
    2664                 :             : 
    2665                 :    10318691 :       b_elt = b_elt->next;
    2666                 :    10318691 :       c_elt = c_elt->next;
    2667                 :    10318691 :       if (!overall)
    2668                 :     3010449 :         continue;
    2669                 :             : 
    2670                 :             :       /* Now find a place to insert AND_ELT.  */
    2671                 :     7308321 :       do
    2672                 :             :         {
    2673                 :     7308321 :           ix = a_elt ? a_elt->indx : and_elt.indx;
    2674                 :     7308321 :           if (ix == and_elt.indx)
    2675                 :     7265953 :             changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed);
    2676                 :       42368 :           else if (ix > and_elt.indx)
    2677                 :       42289 :             changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed);
    2678                 :             : 
    2679                 :     7308321 :           a_prev = *a_prev_pnext;
    2680                 :     7308321 :           a_prev_pnext = &a_prev->next;
    2681                 :     7308321 :           a_elt = *a_prev_pnext;
    2682                 :             : 
    2683                 :             :           /* If A lagged behind B/C, we advanced it so loop once more.  */
    2684                 :             :         }
    2685                 :     7308321 :       while (ix < and_elt.indx);
    2686                 :             :     }
    2687                 :             : 
    2688                 :     7591178 :  done:
    2689                 :     7881087 :   gcc_checking_assert (!a->current == !a->first);
    2690                 :     7881087 :   if (a->current)
    2691                 :     6146046 :     a->indx = a->current->indx;
    2692                 :             :   return changed;
    2693                 :             : }
    2694                 :             : 
    2695                 :             : /* Compute hash of bitmap (for purposes of hashing).  */
    2696                 :             : 
    2697                 :             : hashval_t
    2698                 :   247793145 : bitmap_hash (const_bitmap head)
    2699                 :             : {
    2700                 :   247793145 :   const bitmap_element *ptr;
    2701                 :   247793145 :   BITMAP_WORD hash = 0;
    2702                 :   247793145 :   int ix;
    2703                 :             : 
    2704                 :   247793145 :   gcc_checking_assert (!head->tree_form);
    2705                 :             : 
    2706                 :   563658990 :   for (ptr = head->first; ptr; ptr = ptr->next)
    2707                 :             :     {
    2708                 :   315865845 :       hash ^= ptr->indx;
    2709                 :   947597535 :       for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
    2710                 :   631731690 :         hash ^= ptr->bits[ix];
    2711                 :             :     }
    2712                 :   247793145 :   return iterative_hash (&hash, sizeof (hash), 0);
    2713                 :             : }
    2714                 :             : 
    2715                 :             : 
    2716                 :             : /* Function to obtain a vector of bitmap elements in bit order from
    2717                 :             :    HEAD in tree view.  */
    2718                 :             : 
    2719                 :             : static void
    2720                 :         168 : bitmap_tree_to_vec (vec<bitmap_element *> &elts, const_bitmap head)
    2721                 :             : {
    2722                 :         168 :   gcc_checking_assert (head->tree_form);
    2723                 :         168 :   auto_vec<bitmap_element *, 32> stack;
    2724                 :         168 :   bitmap_element *e = head->first;
    2725                 :         168 :   while (true)
    2726                 :             :     {
    2727                 :         504 :       while (e != NULL)
    2728                 :             :         {
    2729                 :         168 :           stack.safe_push (e);
    2730                 :         168 :           e = e->prev;
    2731                 :             :         }
    2732                 :         504 :       if (stack.is_empty ())
    2733                 :             :         break;
    2734                 :             : 
    2735                 :         168 :       e = stack.pop ();
    2736                 :         168 :       elts.safe_push (e);
    2737                 :         168 :       e = e->next;
    2738                 :             :     }
    2739                 :         168 : }
    2740                 :             : 
    2741                 :             : /* Debugging function to print out the contents of a bitmap element.  */
    2742                 :             : 
    2743                 :             : DEBUG_FUNCTION void
    2744                 :          63 : debug_bitmap_elt_file (FILE *file, const bitmap_element *ptr)
    2745                 :             : {
    2746                 :          63 :   unsigned int i, j, col = 26;
    2747                 :             : 
    2748                 :          63 :   fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
    2749                 :             :            " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
    2750                 :          63 :            (const void*) ptr, (const void*) ptr->next,
    2751                 :          63 :            (const void*) ptr->prev, ptr->indx);
    2752                 :             : 
    2753                 :         252 :   for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
    2754                 :        8190 :     for (j = 0; j < BITMAP_WORD_BITS; j++)
    2755                 :        8064 :       if ((ptr->bits[i] >> j) & 1)
    2756                 :             :         {
    2757                 :         551 :           if (col > 70)
    2758                 :             :             {
    2759                 :           5 :               fprintf (file, "\n\t\t\t");
    2760                 :           5 :               col = 24;
    2761                 :             :             }
    2762                 :             : 
    2763                 :         551 :           fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
    2764                 :         551 :                                  + i * BITMAP_WORD_BITS + j));
    2765                 :         551 :           col += 4;
    2766                 :             :         }
    2767                 :             : 
    2768                 :          63 :   fprintf (file, " }\n");
    2769                 :          63 : }
    2770                 :             : 
    2771                 :             : /* Debugging function to print out the contents of a bitmap.  */
    2772                 :             : 
    2773                 :             : DEBUG_FUNCTION void
    2774                 :          63 : debug_bitmap_file (FILE *file, const_bitmap head)
    2775                 :             : {
    2776                 :          63 :   const bitmap_element *ptr;
    2777                 :             : 
    2778                 :          63 :   fprintf (file, "\nfirst = " HOST_PTR_PRINTF
    2779                 :             :            " current = " HOST_PTR_PRINTF " indx = %u\n",
    2780                 :          63 :            (void *) head->first, (void *) head->current, head->indx);
    2781                 :             : 
    2782                 :          63 :   if (head->tree_form)
    2783                 :             :     {
    2784                 :           0 :       auto_vec<bitmap_element *, 32> elts;
    2785                 :           0 :       bitmap_tree_to_vec (elts, head);
    2786                 :           0 :       for (unsigned i = 0; i < elts.length (); ++i)
    2787                 :           0 :         debug_bitmap_elt_file (file, elts[i]);
    2788                 :           0 :     }
    2789                 :             :   else
    2790                 :         126 :     for (ptr = head->first; ptr; ptr = ptr->next)
    2791                 :          63 :       debug_bitmap_elt_file (file, ptr);
    2792                 :          63 : }
    2793                 :             : 
    2794                 :             : /* Function to be called from the debugger to print the contents
    2795                 :             :    of a bitmap.  */
    2796                 :             : 
    2797                 :             : DEBUG_FUNCTION void
    2798                 :           0 : debug_bitmap (const_bitmap head)
    2799                 :             : {
    2800                 :           0 :   debug_bitmap_file (stderr, head);
    2801                 :           0 : }
    2802                 :             : 
    2803                 :             : /* Function to print out the contents of a bitmap.  Unlike debug_bitmap_file,
    2804                 :             :    it does not print anything but the bits.  */
    2805                 :             : 
    2806                 :             : DEBUG_FUNCTION void
    2807                 :        2599 : bitmap_print (FILE *file, const_bitmap head, const char *prefix,
    2808                 :             :               const char *suffix)
    2809                 :             : {
    2810                 :        2599 :   const char *comma = "";
    2811                 :        2599 :   unsigned i;
    2812                 :             : 
    2813                 :        2599 :   fputs (prefix, file);
    2814                 :        2599 :   if (head->tree_form)
    2815                 :             :     {
    2816                 :         168 :       auto_vec<bitmap_element *, 32> elts;
    2817                 :         168 :       bitmap_tree_to_vec (elts, head);
    2818                 :         336 :       for (i = 0; i < elts.length (); ++i)
    2819                 :         504 :         for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ++ix)
    2820                 :             :           {
    2821                 :         336 :             BITMAP_WORD word = elts[i]->bits[ix];
    2822                 :       21840 :             for (unsigned bit = 0; bit != BITMAP_WORD_BITS; ++bit)
    2823                 :       21504 :               if (word & ((BITMAP_WORD)1 << bit))
    2824                 :             :                 {
    2825                 :         586 :                   fprintf (file, "%s%d", comma,
    2826                 :             :                            (bit + BITMAP_WORD_BITS * ix
    2827                 :         293 :                             + elts[i]->indx * BITMAP_ELEMENT_ALL_BITS));
    2828                 :         293 :                   comma = ", ";
    2829                 :             :                 }
    2830                 :             :           }
    2831                 :         168 :     }
    2832                 :             :   else
    2833                 :             :     {
    2834                 :        2431 :       bitmap_iterator bi;
    2835                 :       23008 :       EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
    2836                 :             :         {
    2837                 :       20577 :           fprintf (file, "%s%d", comma, i);
    2838                 :       20577 :           comma = ", ";
    2839                 :             :         }
    2840                 :             :     }
    2841                 :        2599 :   fputs (suffix, file);
    2842                 :        2599 : }
    2843                 :             : 
    2844                 :             : /* Output per-bitmap memory usage statistics.  */
    2845                 :             : void
    2846                 :           0 : dump_bitmap_statistics (void)
    2847                 :             : {
    2848                 :           0 :   if (!GATHER_STATISTICS)
    2849                 :           0 :     return;
    2850                 :             : 
    2851                 :             :   bitmap_mem_desc.dump (BITMAP_ORIGIN);
    2852                 :             : }
    2853                 :             : 
    2854                 :             : DEBUG_FUNCTION void
    2855                 :           0 : debug (const bitmap_head &ref)
    2856                 :             : {
    2857                 :           0 :   dump_bitmap (stderr, &ref);
    2858                 :           0 : }
    2859                 :             : 
    2860                 :             : DEBUG_FUNCTION void
    2861                 :           0 : debug (const bitmap_head *ptr)
    2862                 :             : {
    2863                 :           0 :   if (ptr)
    2864                 :           0 :     debug (*ptr);
    2865                 :             :   else
    2866                 :           0 :     fprintf (stderr, "<nil>\n");
    2867                 :           0 : }
    2868                 :             : 
    2869                 :             : DEBUG_FUNCTION void
    2870                 :           0 : debug (const auto_bitmap &ref)
    2871                 :             : {
    2872                 :           0 :   debug ((const bitmap_head &) ref);
    2873                 :           0 : }
    2874                 :             : 
    2875                 :             : DEBUG_FUNCTION void
    2876                 :           0 : debug (const auto_bitmap *ptr)
    2877                 :             : {
    2878                 :           0 :   debug ((const bitmap_head *) ptr);
    2879                 :           0 : }
    2880                 :             : 
    2881                 :             : void
    2882                 :           0 : bitmap_head::dump ()
    2883                 :             : {
    2884                 :           0 :   debug (this);
    2885                 :           0 : }
    2886                 :             : 
    2887                 :             : #if CHECKING_P
    2888                 :             : 
    2889                 :             : namespace selftest {
    2890                 :             : 
    2891                 :             : /* Selftests for bitmaps.  */
    2892                 :             : 
    2893                 :             : /* Freshly-created bitmaps ought to be empty.  */
    2894                 :             : 
    2895                 :             : static void
    2896                 :           4 : test_gc_alloc ()
    2897                 :             : {
    2898                 :           4 :   bitmap b = bitmap_gc_alloc ();
    2899                 :           4 :   ASSERT_TRUE (bitmap_empty_p (b));
    2900                 :           4 : }
    2901                 :             : 
    2902                 :             : /* Verify bitmap_set_range.  */
    2903                 :             : 
    2904                 :             : static void
    2905                 :           4 : test_set_range ()
    2906                 :             : {
    2907                 :           4 :   bitmap b = bitmap_gc_alloc ();
    2908                 :           4 :   ASSERT_TRUE (bitmap_empty_p (b));
    2909                 :             : 
    2910                 :           4 :   bitmap_set_range (b, 7, 5);
    2911                 :           4 :   ASSERT_FALSE (bitmap_empty_p (b));
    2912                 :           4 :   ASSERT_EQ (5, bitmap_count_bits (b));
    2913                 :             : 
    2914                 :             :   /* Verify bitmap_bit_p at the boundaries.  */
    2915                 :           4 :   ASSERT_FALSE (bitmap_bit_p (b, 6));
    2916                 :           4 :   ASSERT_TRUE (bitmap_bit_p (b, 7));
    2917                 :           4 :   ASSERT_TRUE (bitmap_bit_p (b, 11));
    2918                 :           4 :   ASSERT_FALSE (bitmap_bit_p (b, 12));
    2919                 :           4 : }
    2920                 :             : 
    2921                 :             : /* Verify splitting a range into two pieces using bitmap_clear_bit.  */
    2922                 :             : 
    2923                 :             : static void
    2924                 :           4 : test_clear_bit_in_middle ()
    2925                 :             : {
    2926                 :           4 :   bitmap b = bitmap_gc_alloc ();
    2927                 :             : 
    2928                 :             :   /* Set b to [100..200].  */
    2929                 :           4 :   bitmap_set_range (b, 100, 100);
    2930                 :           4 :   ASSERT_EQ (100, bitmap_count_bits (b));
    2931                 :             : 
    2932                 :             :   /* Clear a bit in the middle.  */
    2933                 :           4 :   bool changed = bitmap_clear_bit (b, 150);
    2934                 :           4 :   ASSERT_TRUE (changed);
    2935                 :           4 :   ASSERT_EQ (99, bitmap_count_bits (b));
    2936                 :           4 :   ASSERT_TRUE (bitmap_bit_p (b, 149));
    2937                 :           4 :   ASSERT_FALSE (bitmap_bit_p (b, 150));
    2938                 :           4 :   ASSERT_TRUE (bitmap_bit_p (b, 151));
    2939                 :           4 : }
    2940                 :             : 
    2941                 :             : /* Verify bitmap_copy.  */
    2942                 :             : 
    2943                 :             : static void
    2944                 :           4 : test_copying ()
    2945                 :             : {
    2946                 :           4 :   bitmap src = bitmap_gc_alloc ();
    2947                 :           4 :   bitmap_set_range (src, 40, 10);
    2948                 :             : 
    2949                 :           4 :   bitmap dst = bitmap_gc_alloc ();
    2950                 :           4 :   ASSERT_FALSE (bitmap_equal_p (src, dst));
    2951                 :           4 :   bitmap_copy (dst, src);
    2952                 :           4 :   ASSERT_TRUE (bitmap_equal_p (src, dst));
    2953                 :             : 
    2954                 :             :   /* Verify that we can make them unequal again...  */
    2955                 :           4 :   bitmap_set_range (src, 70, 5);
    2956                 :           4 :   ASSERT_FALSE (bitmap_equal_p (src, dst));
    2957                 :             : 
    2958                 :             :   /* ...and that changing src after the copy didn't affect
    2959                 :             :      the other: */
    2960                 :           4 :   ASSERT_FALSE (bitmap_bit_p (dst, 70));
    2961                 :           4 : }
    2962                 :             : 
    2963                 :             : /* Verify bitmap_single_bit_set_p.  */
    2964                 :             : 
    2965                 :             : static void
    2966                 :           4 : test_bitmap_single_bit_set_p ()
    2967                 :             : {
    2968                 :           4 :   bitmap b = bitmap_gc_alloc ();
    2969                 :             : 
    2970                 :           4 :   ASSERT_FALSE (bitmap_single_bit_set_p (b));
    2971                 :             : 
    2972                 :           4 :   bitmap_set_range (b, 42, 1);
    2973                 :           4 :   ASSERT_TRUE (bitmap_single_bit_set_p (b));
    2974                 :           4 :   ASSERT_EQ (42, bitmap_first_set_bit (b));
    2975                 :             : 
    2976                 :           4 :   bitmap_set_range (b, 1066, 1);
    2977                 :           4 :   ASSERT_FALSE (bitmap_single_bit_set_p (b));
    2978                 :           4 :   ASSERT_EQ (42, bitmap_first_set_bit (b));
    2979                 :             : 
    2980                 :           4 :   bitmap_clear_range (b, 0, 100);
    2981                 :           4 :   ASSERT_TRUE (bitmap_single_bit_set_p (b));
    2982                 :           4 :   ASSERT_EQ (1066, bitmap_first_set_bit (b));
    2983                 :           4 : }
    2984                 :             : 
    2985                 :             : /* Verify accessing aligned bit chunks works as expected.  */
    2986                 :             : 
    2987                 :             : static void
    2988                 :          12 : test_aligned_chunk (unsigned num_bits)
    2989                 :             : {
    2990                 :          12 :   bitmap b = bitmap_gc_alloc ();
    2991                 :          12 :   int limit = 2 ^ num_bits;
    2992                 :             : 
    2993                 :          12 :   int index = 3;
    2994                 :          76 :   for (int x = 0; x < limit; x++)
    2995                 :             :     {
    2996                 :          64 :       bitmap_set_aligned_chunk (b, index, num_bits, (BITMAP_WORD) x);
    2997                 :          64 :       ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index, num_bits) == x);
    2998                 :          64 :       ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index + 1,
    2999                 :             :                                                    num_bits) == 0);
    3000                 :          64 :       ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index - 1,
    3001                 :             :                                                    num_bits) == 0);
    3002                 :          64 :       index += 3;
    3003                 :             :     }
    3004                 :             :   index = 3;
    3005                 :          76 :   for (int x = 0; x < limit ; x++)
    3006                 :             :     {
    3007                 :          64 :       ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index, num_bits) == x);
    3008                 :          64 :       index += 3;
    3009                 :             :     }
    3010                 :          12 : }
    3011                 :             : 
    3012                 :             : /* Run all of the selftests within this file.  */
    3013                 :             : 
    3014                 :             : void
    3015                 :           4 : bitmap_cc_tests ()
    3016                 :             : {
    3017                 :           4 :   test_gc_alloc ();
    3018                 :           4 :   test_set_range ();
    3019                 :           4 :   test_clear_bit_in_middle ();
    3020                 :           4 :   test_copying ();
    3021                 :           4 :   test_bitmap_single_bit_set_p ();
    3022                 :             :   /* Test 2, 4 and 8 bit aligned chunks.  */
    3023                 :           4 :   test_aligned_chunk (2);
    3024                 :           4 :   test_aligned_chunk (4);
    3025                 :           4 :   test_aligned_chunk (8);
    3026                 :           4 : }
    3027                 :             : 
    3028                 :             : } // namespace selftest
    3029                 :             : #endif /* CHECKING_P */
    3030                 :             : 
    3031                 :             : #include "gt-bitmap.h"
        

Generated by: LCOV version 2.1-beta

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,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.