150397Sobrien/* Functions to support general ended bitmaps. 2169689Skan Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005 3117395Skan Free Software Foundation, Inc. 450397Sobrien 590075SobrienThis file is part of GCC. 650397Sobrien 790075SobrienGCC is free software; you can redistribute it and/or modify it under 890075Sobrienthe terms of the GNU General Public License as published by the Free 990075SobrienSoftware Foundation; either version 2, or (at your option) any later 1090075Sobrienversion. 1150397Sobrien 1290075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1390075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1490075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1590075Sobrienfor more details. 1650397Sobrien 1750397SobrienYou should have received a copy of the GNU General Public License 1890075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 2150397Sobrien 2250397Sobrien#include "config.h" 2350397Sobrien#include "system.h" 24132718Skan#include "coretypes.h" 25132718Skan#include "tm.h" 2650397Sobrien#include "rtl.h" 2750397Sobrien#include "flags.h" 2850397Sobrien#include "obstack.h" 29117395Skan#include "ggc.h" 3090075Sobrien#include "bitmap.h" 3150397Sobrien 3250397Sobrien/* Global data */ 33169689Skanbitmap_element bitmap_zero_bits; /* An element of all zero bits. */ 34169689Skanbitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */ 35169689Skanstatic GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of 36169689Skan GC'd elements. */ 3750397Sobrien 38132718Skanstatic void bitmap_elem_to_freelist (bitmap, bitmap_element *); 39132718Skanstatic void bitmap_element_free (bitmap, bitmap_element *); 40132718Skanstatic bitmap_element *bitmap_element_allocate (bitmap); 41132718Skanstatic int bitmap_element_zerop (bitmap_element *); 42132718Skanstatic void bitmap_element_link (bitmap, bitmap_element *); 43169689Skanstatic bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int); 44169689Skanstatic void bitmap_elt_clear_from (bitmap, bitmap_element *); 45132718Skanstatic bitmap_element *bitmap_find_bit (bitmap, unsigned int); 4650397Sobrien 47169689Skan 48117395Skan/* Add ELEM to the appropriate freelist. */ 49169689Skanstatic inline void 50132718Skanbitmap_elem_to_freelist (bitmap head, bitmap_element *elt) 51117395Skan{ 52169689Skan bitmap_obstack *bit_obstack = head->obstack; 53169689Skan 54169689Skan elt->next = NULL; 55169689Skan if (bit_obstack) 56117395Skan { 57169689Skan elt->prev = bit_obstack->elements; 58169689Skan bit_obstack->elements = elt; 59117395Skan } 60117395Skan else 61117395Skan { 62169689Skan elt->prev = bitmap_ggc_free; 63117395Skan bitmap_ggc_free = elt; 64117395Skan } 65117395Skan} 66117395Skan 6790075Sobrien/* Free a bitmap element. Since these are allocated off the 6890075Sobrien bitmap_obstack, "free" actually means "put onto the freelist". */ 6950397Sobrien 70169689Skanstatic inline void 71132718Skanbitmap_element_free (bitmap head, bitmap_element *elt) 7250397Sobrien{ 7350397Sobrien bitmap_element *next = elt->next; 7450397Sobrien bitmap_element *prev = elt->prev; 7550397Sobrien 7650397Sobrien if (prev) 7750397Sobrien prev->next = next; 7850397Sobrien 7950397Sobrien if (next) 8050397Sobrien next->prev = prev; 8150397Sobrien 8250397Sobrien if (head->first == elt) 8350397Sobrien head->first = next; 8450397Sobrien 8550397Sobrien /* Since the first thing we try is to insert before current, 8650397Sobrien make current the next entry in preference to the previous. */ 8750397Sobrien if (head->current == elt) 8890075Sobrien { 8990075Sobrien head->current = next != 0 ? next : prev; 9090075Sobrien if (head->current) 9190075Sobrien head->indx = head->current->indx; 92169689Skan else 93169689Skan head->indx = 0; 9490075Sobrien } 95117395Skan bitmap_elem_to_freelist (head, elt); 9650397Sobrien} 9750397Sobrien 9850397Sobrien/* Allocate a bitmap element. The bits are cleared, but nothing else is. */ 9950397Sobrien 100169689Skanstatic inline bitmap_element * 101132718Skanbitmap_element_allocate (bitmap head) 10250397Sobrien{ 10350397Sobrien bitmap_element *element; 104169689Skan bitmap_obstack *bit_obstack = head->obstack; 10550397Sobrien 106169689Skan if (bit_obstack) 10750397Sobrien { 108169689Skan element = bit_obstack->elements; 109169689Skan 110169689Skan if (element) 111169689Skan /* Use up the inner list first before looking at the next 112169689Skan element of the outer list. */ 113169689Skan if (element->next) 114169689Skan { 115169689Skan bit_obstack->elements = element->next; 116169689Skan bit_obstack->elements->prev = element->prev; 117169689Skan } 118169689Skan else 119169689Skan /* Inner list was just a singleton. */ 120169689Skan bit_obstack->elements = element->prev; 121117395Skan else 122169689Skan element = XOBNEW (&bit_obstack->obstack, bitmap_element); 123169689Skan } 124169689Skan else 125169689Skan { 126169689Skan element = bitmap_ggc_free; 127169689Skan if (element) 128169689Skan /* Use up the inner list first before looking at the next 129169689Skan element of the outer list. */ 130169689Skan if (element->next) 131169689Skan { 132169689Skan bitmap_ggc_free = element->next; 133169689Skan bitmap_ggc_free->prev = element->prev; 134169689Skan } 135169689Skan else 136169689Skan /* Inner list was just a singleton. */ 137169689Skan bitmap_ggc_free = element->prev; 138169689Skan else 139169689Skan element = GGC_NEW (bitmap_element); 140169689Skan } 141132718Skan 142169689Skan memset (element->bits, 0, sizeof (element->bits)); 143132718Skan 144169689Skan return element; 145169689Skan} 146132718Skan 147169689Skan/* Remove ELT and all following elements from bitmap HEAD. */ 148169689Skan 149169689Skanvoid 150169689Skanbitmap_elt_clear_from (bitmap head, bitmap_element *elt) 151169689Skan{ 152169689Skan bitmap_element *prev; 153169689Skan bitmap_obstack *bit_obstack = head->obstack; 154169689Skan 155169689Skan if (!elt) return; 156169689Skan 157169689Skan prev = elt->prev; 158169689Skan if (prev) 159169689Skan { 160169689Skan prev->next = NULL; 161169689Skan if (head->current->indx > prev->indx) 162169689Skan { 163169689Skan head->current = prev; 164169689Skan head->indx = prev->indx; 16550397Sobrien } 16650397Sobrien } 167117395Skan else 168117395Skan { 169169689Skan head->first = NULL; 170169689Skan head->current = NULL; 171169689Skan head->indx = 0; 172117395Skan } 17350397Sobrien 174169689Skan /* Put the entire list onto the free list in one operation. */ 175169689Skan if (bit_obstack) 176169689Skan { 177169689Skan elt->prev = bit_obstack->elements; 178169689Skan bit_obstack->elements = elt; 179169689Skan } 180169689Skan else 181169689Skan { 182169689Skan elt->prev = bitmap_ggc_free; 183169689Skan bitmap_ggc_free = elt; 184169689Skan } 185169689Skan} 18650397Sobrien 187169689Skan/* Clear a bitmap by freeing the linked list. */ 188169689Skan 189169689Skaninline void 190169689Skanbitmap_clear (bitmap head) 191169689Skan{ 192169689Skan if (head->first) 193169689Skan bitmap_elt_clear_from (head, head->first); 19450397Sobrien} 195169689Skan 196169689Skan/* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize 197169689Skan the default bitmap obstack. */ 19850397Sobrien 199169689Skanvoid 200169689Skanbitmap_obstack_initialize (bitmap_obstack *bit_obstack) 201169689Skan{ 202169689Skan if (!bit_obstack) 203169689Skan bit_obstack = &bitmap_default_obstack; 20490075Sobrien 205169689Skan#if !defined(__GNUC__) || (__GNUC__ < 2) 206169689Skan#define __alignof__(type) 0 207169689Skan#endif 208169689Skan 209169689Skan bit_obstack->elements = NULL; 210169689Skan bit_obstack->heads = NULL; 211169689Skan obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE, 212169689Skan __alignof__ (bitmap_element), 213169689Skan obstack_chunk_alloc, 214169689Skan obstack_chunk_free); 215169689Skan} 216169689Skan 217169689Skan/* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL, 218169689Skan release the default bitmap obstack. */ 219169689Skan 22090075Sobrienvoid 221169689Skanbitmap_obstack_release (bitmap_obstack *bit_obstack) 22290075Sobrien{ 223169689Skan if (!bit_obstack) 224169689Skan bit_obstack = &bitmap_default_obstack; 225169689Skan 226169689Skan bit_obstack->elements = NULL; 227169689Skan bit_obstack->heads = NULL; 228169689Skan obstack_free (&bit_obstack->obstack, NULL); 229169689Skan} 230169689Skan 231169689Skan/* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create 232169689Skan it on the default bitmap obstack. */ 233169689Skan 234169689Skanbitmap 235169689Skanbitmap_obstack_alloc (bitmap_obstack *bit_obstack) 236169689Skan{ 237169689Skan bitmap map; 238169689Skan 239169689Skan if (!bit_obstack) 240169689Skan bit_obstack = &bitmap_default_obstack; 241169689Skan map = bit_obstack->heads; 242169689Skan if (map) 243169689Skan bit_obstack->heads = (void *)map->first; 244169689Skan else 245169689Skan map = XOBNEW (&bit_obstack->obstack, bitmap_head); 246169689Skan bitmap_initialize (map, bit_obstack); 247169689Skan 248169689Skan return map; 249169689Skan} 250169689Skan 251169689Skan/* Create a new GCd bitmap. */ 252169689Skan 253169689Skanbitmap 254169689Skanbitmap_gc_alloc (void) 255169689Skan{ 256169689Skan bitmap map; 257169689Skan 258169689Skan map = GGC_NEW (struct bitmap_head_def); 259169689Skan bitmap_initialize (map, NULL); 260169689Skan 261169689Skan return map; 262169689Skan} 263169689Skan 264169689Skan/* Release an obstack allocated bitmap. */ 265169689Skan 266169689Skanvoid 267169689Skanbitmap_obstack_free (bitmap map) 268169689Skan{ 269169689Skan if (map) 27090075Sobrien { 271169689Skan bitmap_clear (map); 272169689Skan map->first = (void *)map->obstack->heads; 273169689Skan map->obstack->heads = map; 27490075Sobrien } 27590075Sobrien} 27690075Sobrien 277169689Skan 27850397Sobrien/* Return nonzero if all bits in an element are zero. */ 27950397Sobrien 280169689Skanstatic inline int 281132718Skanbitmap_element_zerop (bitmap_element *element) 28250397Sobrien{ 28350397Sobrien#if BITMAP_ELEMENT_WORDS == 2 28450397Sobrien return (element->bits[0] | element->bits[1]) == 0; 28550397Sobrien#else 286169689Skan unsigned i; 28750397Sobrien 28850397Sobrien for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) 28950397Sobrien if (element->bits[i] != 0) 29050397Sobrien return 0; 29150397Sobrien 29250397Sobrien return 1; 29350397Sobrien#endif 29450397Sobrien} 29550397Sobrien 29650397Sobrien/* Link the bitmap element into the current bitmap linked list. */ 29750397Sobrien 298169689Skanstatic inline void 299132718Skanbitmap_element_link (bitmap head, bitmap_element *element) 30050397Sobrien{ 30150397Sobrien unsigned int indx = element->indx; 30250397Sobrien bitmap_element *ptr; 30350397Sobrien 30450397Sobrien /* If this is the first and only element, set it in. */ 30550397Sobrien if (head->first == 0) 30650397Sobrien { 30750397Sobrien element->next = element->prev = 0; 30850397Sobrien head->first = element; 30950397Sobrien } 31050397Sobrien 31150397Sobrien /* If this index is less than that of the current element, it goes someplace 31250397Sobrien before the current element. */ 31350397Sobrien else if (indx < head->indx) 31450397Sobrien { 31550397Sobrien for (ptr = head->current; 31650397Sobrien ptr->prev != 0 && ptr->prev->indx > indx; 31750397Sobrien ptr = ptr->prev) 31850397Sobrien ; 31950397Sobrien 32050397Sobrien if (ptr->prev) 32150397Sobrien ptr->prev->next = element; 32250397Sobrien else 32350397Sobrien head->first = element; 32450397Sobrien 32550397Sobrien element->prev = ptr->prev; 32650397Sobrien element->next = ptr; 32750397Sobrien ptr->prev = element; 32850397Sobrien } 32950397Sobrien 33050397Sobrien /* Otherwise, it must go someplace after the current element. */ 33150397Sobrien else 33250397Sobrien { 33350397Sobrien for (ptr = head->current; 33450397Sobrien ptr->next != 0 && ptr->next->indx < indx; 33550397Sobrien ptr = ptr->next) 33650397Sobrien ; 33750397Sobrien 33850397Sobrien if (ptr->next) 33950397Sobrien ptr->next->prev = element; 34050397Sobrien 34150397Sobrien element->next = ptr->next; 34250397Sobrien element->prev = ptr; 34350397Sobrien ptr->next = element; 34450397Sobrien } 34550397Sobrien 34650397Sobrien /* Set up so this is the first element searched. */ 34750397Sobrien head->current = element; 34850397Sobrien head->indx = indx; 34950397Sobrien} 35050397Sobrien 351169689Skan/* Insert a new uninitialized element into bitmap HEAD after element 352169689Skan ELT. If ELT is NULL, insert the element at the start. Return the 353169689Skan new element. */ 354169689Skan 355169689Skanstatic bitmap_element * 356169689Skanbitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx) 35750397Sobrien{ 358169689Skan bitmap_element *node = bitmap_element_allocate (head); 359169689Skan node->indx = indx; 36050397Sobrien 361169689Skan if (!elt) 36250397Sobrien { 363169689Skan if (!head->current) 364169689Skan { 365169689Skan head->current = node; 366169689Skan head->indx = indx; 367169689Skan } 368169689Skan node->next = head->first; 369169689Skan if (node->next) 370169689Skan node->next->prev = node; 371169689Skan head->first = node; 372169689Skan node->prev = NULL; 37350397Sobrien } 374169689Skan else 375169689Skan { 376169689Skan gcc_assert (head->current); 377169689Skan node->next = elt->next; 378169689Skan if (node->next) 379169689Skan node->next->prev = node; 380169689Skan elt->next = node; 381169689Skan node->prev = elt; 382169689Skan } 383169689Skan return node; 38450397Sobrien} 38550397Sobrien 38690075Sobrien/* Copy a bitmap to another bitmap. */ 38750397Sobrien 38850397Sobrienvoid 389132718Skanbitmap_copy (bitmap to, bitmap from) 39050397Sobrien{ 39150397Sobrien bitmap_element *from_ptr, *to_ptr = 0; 39250397Sobrien 39350397Sobrien bitmap_clear (to); 39450397Sobrien 395132718Skan /* Copy elements in forward direction one at a time. */ 39650397Sobrien for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next) 39750397Sobrien { 398117395Skan bitmap_element *to_elt = bitmap_element_allocate (to); 39950397Sobrien 40050397Sobrien to_elt->indx = from_ptr->indx; 401169689Skan memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits)); 40250397Sobrien 40350397Sobrien /* Here we have a special case of bitmap_element_link, for the case 40450397Sobrien where we know the links are being entered in sequence. */ 40550397Sobrien if (to_ptr == 0) 40650397Sobrien { 40750397Sobrien to->first = to->current = to_elt; 40850397Sobrien to->indx = from_ptr->indx; 40950397Sobrien to_elt->next = to_elt->prev = 0; 41050397Sobrien } 41150397Sobrien else 41250397Sobrien { 41350397Sobrien to_elt->prev = to_ptr; 41450397Sobrien to_elt->next = 0; 41550397Sobrien to_ptr->next = to_elt; 41650397Sobrien } 41750397Sobrien 41850397Sobrien to_ptr = to_elt; 41950397Sobrien } 42050397Sobrien} 42150397Sobrien 42250397Sobrien/* Find a bitmap element that would hold a bitmap's bit. 42350397Sobrien Update the `current' field even if we can't find an element that 42450397Sobrien would hold the bitmap's bit to make eventual allocation 42550397Sobrien faster. */ 42650397Sobrien 427169689Skanstatic inline bitmap_element * 428132718Skanbitmap_find_bit (bitmap head, unsigned int bit) 42950397Sobrien{ 43050397Sobrien bitmap_element *element; 431117395Skan unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS; 43250397Sobrien 433102780Skan if (head->current == 0 434102780Skan || head->indx == indx) 435102780Skan return head->current; 43650397Sobrien 437169689Skan if (head->indx < indx) 438169689Skan /* INDX is beyond head->indx. Search from head->current 439169689Skan forward. */ 44050397Sobrien for (element = head->current; 441169689Skan element->next != 0 && element->indx < indx; 442169689Skan element = element->next) 443169689Skan ; 444169689Skan 445169689Skan else if (head->indx / 2 < indx) 446169689Skan /* INDX is less than head->indx and closer to head->indx than to 447169689Skan 0. Search from head->current backward. */ 448169689Skan for (element = head->current; 44950397Sobrien element->prev != 0 && element->indx > indx; 45050397Sobrien element = element->prev) 45150397Sobrien ; 45250397Sobrien 45350397Sobrien else 454169689Skan /* INDX is less than head->indx and closer to 0 than to 455169689Skan head->indx. Search from head->first forward. */ 456169689Skan for (element = head->first; 45750397Sobrien element->next != 0 && element->indx < indx; 45850397Sobrien element = element->next) 45950397Sobrien ; 46050397Sobrien 46150397Sobrien /* `element' is the nearest to the one we want. If it's not the one we 46250397Sobrien want, the one we want doesn't exist. */ 46350397Sobrien head->current = element; 46450397Sobrien head->indx = element->indx; 46550397Sobrien if (element != 0 && element->indx != indx) 46650397Sobrien element = 0; 46750397Sobrien 46850397Sobrien return element; 46950397Sobrien} 47050397Sobrien 47150397Sobrien/* Clear a single bit in a bitmap. */ 47250397Sobrien 47350397Sobrienvoid 474132718Skanbitmap_clear_bit (bitmap head, int bit) 47550397Sobrien{ 47650397Sobrien bitmap_element *ptr = bitmap_find_bit (head, bit); 47750397Sobrien 47850397Sobrien if (ptr != 0) 47950397Sobrien { 480117395Skan unsigned bit_num = bit % BITMAP_WORD_BITS; 481117395Skan unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 482117395Skan ptr->bits[word_num] &= ~ (((BITMAP_WORD) 1) << bit_num); 48350397Sobrien 484132718Skan /* If we cleared the entire word, free up the element. */ 48550397Sobrien if (bitmap_element_zerop (ptr)) 48650397Sobrien bitmap_element_free (head, ptr); 48750397Sobrien } 48850397Sobrien} 48950397Sobrien 49050397Sobrien/* Set a single bit in a bitmap. */ 49150397Sobrien 49250397Sobrienvoid 493132718Skanbitmap_set_bit (bitmap head, int bit) 49450397Sobrien{ 49550397Sobrien bitmap_element *ptr = bitmap_find_bit (head, bit); 496117395Skan unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 497117395Skan unsigned bit_num = bit % BITMAP_WORD_BITS; 498117395Skan BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; 49950397Sobrien 50050397Sobrien if (ptr == 0) 50150397Sobrien { 502117395Skan ptr = bitmap_element_allocate (head); 50350397Sobrien ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS; 50450397Sobrien ptr->bits[word_num] = bit_val; 50550397Sobrien bitmap_element_link (head, ptr); 50650397Sobrien } 50750397Sobrien else 50850397Sobrien ptr->bits[word_num] |= bit_val; 50950397Sobrien} 51090075Sobrien 51150397Sobrien/* Return whether a bit is set within a bitmap. */ 51250397Sobrien 51350397Sobrienint 514132718Skanbitmap_bit_p (bitmap head, int bit) 51550397Sobrien{ 51650397Sobrien bitmap_element *ptr; 51750397Sobrien unsigned bit_num; 51850397Sobrien unsigned word_num; 51950397Sobrien 52050397Sobrien ptr = bitmap_find_bit (head, bit); 52150397Sobrien if (ptr == 0) 52250397Sobrien return 0; 52350397Sobrien 524117395Skan bit_num = bit % BITMAP_WORD_BITS; 525117395Skan word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 52650397Sobrien 52790075Sobrien return (ptr->bits[word_num] >> bit_num) & 1; 52850397Sobrien} 52950397Sobrien 530169689Skan#if GCC_VERSION < 3400 531169689Skan/* Table of number of set bits in a character, indexed by value of char. */ 532169689Skanstatic unsigned char popcount_table[] = 533169689Skan{ 534169689Skan 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, 535169689Skan 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, 536169689Skan 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, 537169689Skan 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, 538169689Skan 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, 539169689Skan 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, 540169689Skan 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, 541169689Skan 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, 542169689Skan}; 54350397Sobrien 544169689Skanstatic unsigned long 545169689Skanbitmap_popcount (BITMAP_WORD a) 54690075Sobrien{ 547169689Skan unsigned long ret = 0; 548169689Skan unsigned i; 54990075Sobrien 550169689Skan /* Just do this the table way for now */ 551169689Skan for (i = 0; i < BITMAP_WORD_BITS; i+= 8) 552169689Skan ret += popcount_table[(a >> i) & 0xff]; 553169689Skan return ret; 554169689Skan} 555169689Skan#endif 556169689Skan/* Count the number of bits set in the bitmap, and return it. */ 55790075Sobrien 558169689Skanunsigned long 559169689Skanbitmap_count_bits (bitmap a) 560169689Skan{ 561169689Skan unsigned long count = 0; 562169689Skan bitmap_element *elt; 563169689Skan unsigned ix; 564169689Skan 565169689Skan for (elt = a->first; elt; elt = elt->next) 566169689Skan { 567169689Skan for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) 568169689Skan { 569169689Skan#if GCC_VERSION >= 3400 570169689Skan /* Note that popcountl matches BITMAP_WORD in type, so the actual size 571169689Skan of BITMAP_WORD is not material. */ 572169689Skan count += __builtin_popcountl (elt->bits[ix]); 57390075Sobrien#else 574169689Skan count += bitmap_popcount (elt->bits[ix]); 57590075Sobrien#endif 576169689Skan } 577169689Skan } 578169689Skan return count; 579169689Skan} 58090075Sobrien 58190075Sobrien 58290075Sobrien 583169689Skan/* Return the bit number of the first set bit in the bitmap. The 584169689Skan bitmap must be non-empty. */ 585169689Skan 586169689Skanunsigned 587169689Skanbitmap_first_set_bit (bitmap a) 588169689Skan{ 589169689Skan bitmap_element *elt = a->first; 590169689Skan unsigned bit_no; 591169689Skan BITMAP_WORD word; 592169689Skan unsigned ix; 593169689Skan 594169689Skan gcc_assert (elt); 595169689Skan bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; 596169689Skan for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) 597169689Skan { 598169689Skan word = elt->bits[ix]; 599169689Skan if (word) 600169689Skan goto found_bit; 601169689Skan } 602169689Skan gcc_unreachable (); 603169689Skan found_bit: 604169689Skan bit_no += ix * BITMAP_WORD_BITS; 605169689Skan 606169689Skan#if GCC_VERSION >= 3004 607169689Skan gcc_assert (sizeof(long) == sizeof (word)); 608169689Skan bit_no += __builtin_ctzl (word); 609169689Skan#else 610169689Skan /* Binary search for the first set bit. */ 611169689Skan#if BITMAP_WORD_BITS > 64 612169689Skan#error "Fill out the table." 61390075Sobrien#endif 614169689Skan#if BITMAP_WORD_BITS > 32 615169689Skan if (!(word & 0xffffffff)) 616169689Skan word >>= 32, bit_no += 32; 61790075Sobrien#endif 618169689Skan if (!(word & 0xffff)) 619169689Skan word >>= 16, bit_no += 16; 620169689Skan if (!(word & 0xff)) 621169689Skan word >>= 8, bit_no += 8; 622169689Skan if (!(word & 0xf)) 623169689Skan word >>= 4, bit_no += 4; 624169689Skan if (!(word & 0x3)) 625169689Skan word >>= 2, bit_no += 2; 626169689Skan if (!(word & 0x1)) 627169689Skan word >>= 1, bit_no += 1; 62890075Sobrien 629169689Skan gcc_assert (word & 1); 630169689Skan#endif 631169689Skan return bit_no; 63290075Sobrien} 633169689Skan 63490075Sobrien 635169689Skan/* DST = A & B. */ 63690075Sobrien 637169689Skanvoid 638169689Skanbitmap_and (bitmap dst, bitmap a, bitmap b) 63990075Sobrien{ 640169689Skan bitmap_element *dst_elt = dst->first; 641169689Skan bitmap_element *a_elt = a->first; 642169689Skan bitmap_element *b_elt = b->first; 643169689Skan bitmap_element *dst_prev = NULL; 64490075Sobrien 645169689Skan gcc_assert (dst != a && dst != b); 64690075Sobrien 647169689Skan if (a == b) 648169689Skan { 649169689Skan bitmap_copy (dst, a); 650169689Skan return; 651169689Skan } 65290075Sobrien 653169689Skan while (a_elt && b_elt) 654169689Skan { 655169689Skan if (a_elt->indx < b_elt->indx) 656169689Skan a_elt = a_elt->next; 657169689Skan else if (b_elt->indx < a_elt->indx) 658169689Skan b_elt = b_elt->next; 659169689Skan else 660169689Skan { 661169689Skan /* Matching elts, generate A & B. */ 662169689Skan unsigned ix; 663169689Skan BITMAP_WORD ior = 0; 66490075Sobrien 665169689Skan if (!dst_elt) 666169689Skan dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); 667169689Skan else 668169689Skan dst_elt->indx = a_elt->indx; 669169689Skan for (ix = BITMAP_ELEMENT_WORDS; ix--;) 670169689Skan { 671169689Skan BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; 67290075Sobrien 673169689Skan dst_elt->bits[ix] = r; 674169689Skan ior |= r; 675169689Skan } 676169689Skan if (ior) 677169689Skan { 678169689Skan dst_prev = dst_elt; 679169689Skan dst_elt = dst_elt->next; 680169689Skan } 681169689Skan a_elt = a_elt->next; 682169689Skan b_elt = b_elt->next; 683169689Skan } 684169689Skan } 685169689Skan bitmap_elt_clear_from (dst, dst_elt); 686169689Skan gcc_assert (!dst->current == !dst->first); 687169689Skan if (dst->current) 688169689Skan dst->indx = dst->current->indx; 68990075Sobrien} 69090075Sobrien 691169689Skan/* A &= B. */ 692169689Skan 693169689Skanvoid 694169689Skanbitmap_and_into (bitmap a, bitmap b) 69550397Sobrien{ 696169689Skan bitmap_element *a_elt = a->first; 697169689Skan bitmap_element *b_elt = b->first; 698169689Skan bitmap_element *next; 69990075Sobrien 700169689Skan if (a == b) 701169689Skan return; 70290075Sobrien 703169689Skan while (a_elt && b_elt) 704169689Skan { 705169689Skan if (a_elt->indx < b_elt->indx) 706169689Skan { 707169689Skan next = a_elt->next; 708169689Skan bitmap_element_free (a, a_elt); 709169689Skan a_elt = next; 710169689Skan } 711169689Skan else if (b_elt->indx < a_elt->indx) 712169689Skan b_elt = b_elt->next; 713169689Skan else 714169689Skan { 715169689Skan /* Matching elts, generate A &= B. */ 716169689Skan unsigned ix; 717169689Skan BITMAP_WORD ior = 0; 71850397Sobrien 719169689Skan for (ix = BITMAP_ELEMENT_WORDS; ix--;) 720169689Skan { 721169689Skan BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; 72250397Sobrien 723169689Skan a_elt->bits[ix] = r; 724169689Skan ior |= r; 725169689Skan } 726169689Skan next = a_elt->next; 727169689Skan if (!ior) 728169689Skan bitmap_element_free (a, a_elt); 729169689Skan a_elt = next; 730169689Skan b_elt = b_elt->next; 731169689Skan } 732169689Skan } 733169689Skan bitmap_elt_clear_from (a, a_elt); 734169689Skan gcc_assert (!a->current == !a->first); 735169689Skan gcc_assert (!a->current || a->indx == a->current->indx); 736169689Skan} 737169689Skan 738169689Skan/* DST = A & ~B */ 739169689Skan 740169689Skanvoid 741169689Skanbitmap_and_compl (bitmap dst, bitmap a, bitmap b) 742169689Skan{ 743169689Skan bitmap_element *dst_elt = dst->first; 744169689Skan bitmap_element *a_elt = a->first; 745169689Skan bitmap_element *b_elt = b->first; 746169689Skan bitmap_element *dst_prev = NULL; 747169689Skan 748169689Skan gcc_assert (dst != a && dst != b); 749169689Skan 750169689Skan if (a == b) 75150397Sobrien { 752169689Skan bitmap_clear (dst); 753169689Skan return; 754169689Skan } 755169689Skan 756169689Skan while (a_elt) 757169689Skan { 758169689Skan if (!b_elt || a_elt->indx < b_elt->indx) 75950397Sobrien { 760169689Skan /* Copy a_elt. */ 761169689Skan if (!dst_elt) 762169689Skan dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); 763169689Skan else 764169689Skan dst_elt->indx = a_elt->indx; 765169689Skan memcpy (dst_elt->bits, a_elt->bits, sizeof (dst_elt->bits)); 766169689Skan dst_prev = dst_elt; 767169689Skan dst_elt = dst_elt->next; 768169689Skan a_elt = a_elt->next; 76950397Sobrien } 770169689Skan else if (b_elt->indx < a_elt->indx) 771169689Skan b_elt = b_elt->next; 772169689Skan else 77350397Sobrien { 774169689Skan /* Matching elts, generate A & ~B. */ 775169689Skan unsigned ix; 776169689Skan BITMAP_WORD ior = 0; 777169689Skan 778169689Skan if (!dst_elt) 779169689Skan dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); 780169689Skan else 781169689Skan dst_elt->indx = a_elt->indx; 782169689Skan for (ix = BITMAP_ELEMENT_WORDS; ix--;) 783169689Skan { 784169689Skan BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; 785169689Skan 786169689Skan dst_elt->bits[ix] = r; 787169689Skan ior |= r; 788169689Skan } 789169689Skan if (ior) 790169689Skan { 791169689Skan dst_prev = dst_elt; 792169689Skan dst_elt = dst_elt->next; 793169689Skan } 794169689Skan a_elt = a_elt->next; 795169689Skan b_elt = b_elt->next; 79650397Sobrien } 797169689Skan } 798169689Skan bitmap_elt_clear_from (dst, dst_elt); 799169689Skan gcc_assert (!dst->current == !dst->first); 800169689Skan if (dst->current) 801169689Skan dst->indx = dst->current->indx; 802169689Skan} 803169689Skan 804169689Skan/* A &= ~B. Returns true if A changes */ 805169689Skan 806169689Skanbool 807169689Skanbitmap_and_compl_into (bitmap a, bitmap b) 808169689Skan{ 809169689Skan bitmap_element *a_elt = a->first; 810169689Skan bitmap_element *b_elt = b->first; 811169689Skan bitmap_element *next; 812169689Skan BITMAP_WORD changed = 0; 813169689Skan 814169689Skan if (a == b) 815169689Skan { 816169689Skan if (bitmap_empty_p (a)) 817169689Skan return false; 81850397Sobrien else 81950397Sobrien { 820169689Skan bitmap_clear (a); 821169689Skan return true; 82250397Sobrien } 823169689Skan } 82450397Sobrien 825169689Skan while (a_elt && b_elt) 826169689Skan { 827169689Skan if (a_elt->indx < b_elt->indx) 828169689Skan a_elt = a_elt->next; 829169689Skan else if (b_elt->indx < a_elt->indx) 830169689Skan b_elt = b_elt->next; 831169689Skan else 83290075Sobrien { 833169689Skan /* Matching elts, generate A &= ~B. */ 834169689Skan unsigned ix; 835169689Skan BITMAP_WORD ior = 0; 836169689Skan 837169689Skan for (ix = BITMAP_ELEMENT_WORDS; ix--;) 838169689Skan { 839169689Skan BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; 840169689Skan BITMAP_WORD r = a_elt->bits[ix] ^ cleared; 841169689Skan 842169689Skan a_elt->bits[ix] = r; 843169689Skan changed |= cleared; 844169689Skan ior |= r; 845169689Skan } 846169689Skan next = a_elt->next; 847169689Skan if (!ior) 848169689Skan bitmap_element_free (a, a_elt); 849169689Skan a_elt = next; 850169689Skan b_elt = b_elt->next; 85190075Sobrien } 852169689Skan } 853169689Skan gcc_assert (!a->current == !a->first); 854169689Skan gcc_assert (!a->current || a->indx == a->current->indx); 855169689Skan return changed != 0; 856169689Skan} 857169689Skan 858169689Skan/* Clear COUNT bits from START in HEAD. */ 859169689Skanvoid 860169689Skanbitmap_clear_range (bitmap head, unsigned int start, unsigned int count) 861169689Skan{ 862169689Skan unsigned int first_index = start / BITMAP_ELEMENT_ALL_BITS; 863169689Skan unsigned int end_bit_plus1 = start + count; 864169689Skan unsigned int end_bit = end_bit_plus1 - 1; 865169689Skan unsigned int last_index = (end_bit) / BITMAP_ELEMENT_ALL_BITS; 866169689Skan bitmap_element *elt = bitmap_find_bit (head, start); 867169689Skan 868169689Skan /* If bitmap_find_bit returns zero, the current is the closest block 869169689Skan to the result. If the current is less than first index, find the 870169689Skan next one. Otherwise, just set elt to be current. */ 871169689Skan if (!elt) 872169689Skan { 873169689Skan if (head->current) 87490075Sobrien { 875169689Skan if (head->indx < first_index) 876169689Skan { 877169689Skan elt = head->current->next; 878169689Skan if (!elt) 879169689Skan return; 880169689Skan } 881169689Skan else 882169689Skan elt = head->current; 88390075Sobrien } 88490075Sobrien else 885169689Skan return; 886169689Skan } 88750397Sobrien 888169689Skan while (elt && (elt->indx <= last_index)) 889169689Skan { 890169689Skan bitmap_element * next_elt = elt->next; 891169689Skan unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS; 892169689Skan unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; 893169689Skan 894169689Skan 895169689Skan if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1) 896169689Skan /* Get rid of the entire elt and go to the next one. */ 897169689Skan bitmap_element_free (head, elt); 898169689Skan else 89950397Sobrien { 900169689Skan /* Going to have to knock out some bits in this elt. */ 901169689Skan unsigned int first_word_to_mod; 902169689Skan BITMAP_WORD first_mask; 903169689Skan unsigned int last_word_to_mod; 904169689Skan BITMAP_WORD last_mask; 905169689Skan unsigned int i; 906169689Skan bool clear = true; 90750397Sobrien 908169689Skan if (elt_start_bit <= start) 909169689Skan { 910169689Skan /* The first bit to turn off is somewhere inside this 911169689Skan elt. */ 912169689Skan first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS; 91350397Sobrien 914169689Skan /* This mask should have 1s in all bits >= start position. */ 915169689Skan first_mask = 916169689Skan (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1; 917169689Skan first_mask = ~first_mask; 918169689Skan } 919169689Skan else 920169689Skan { 921169689Skan /* The first bit to turn off is below this start of this elt. */ 922169689Skan first_word_to_mod = 0; 923169689Skan first_mask = 0; 924169689Skan first_mask = ~first_mask; 925169689Skan } 92650397Sobrien 927169689Skan if (elt_end_bit_plus1 <= end_bit_plus1) 928169689Skan { 929169689Skan /* The last bit to turn off is beyond this elt. */ 930169689Skan last_word_to_mod = BITMAP_ELEMENT_WORDS - 1; 931169689Skan last_mask = 0; 932169689Skan last_mask = ~last_mask; 933169689Skan } 934169689Skan else 935169689Skan { 936169689Skan /* The last bit to turn off is inside to this elt. */ 937169689Skan last_word_to_mod = 938169689Skan (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS; 939169689Skan 940169689Skan /* The last mask should have 1s below the end bit. */ 941169689Skan last_mask = 942169689Skan (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1; 943169689Skan } 944169689Skan 945169689Skan 946169689Skan if (first_word_to_mod == last_word_to_mod) 947169689Skan { 948169689Skan BITMAP_WORD mask = first_mask & last_mask; 949169689Skan elt->bits[first_word_to_mod] &= ~mask; 950169689Skan } 951169689Skan else 952169689Skan { 953169689Skan elt->bits[first_word_to_mod] &= ~first_mask; 954169689Skan for (i = first_word_to_mod + 1; i < last_word_to_mod; i++) 955169689Skan elt->bits[i] = 0; 956169689Skan elt->bits[last_word_to_mod] &= ~last_mask; 957169689Skan } 958169689Skan for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) 959169689Skan if (elt->bits[i]) 960169689Skan { 961169689Skan clear = false; 962169689Skan break; 963169689Skan } 964169689Skan /* Check to see if there are any bits left. */ 965169689Skan if (clear) 966169689Skan bitmap_element_free (head, elt); 96750397Sobrien } 968169689Skan elt = next_elt; 969169689Skan } 97050397Sobrien 971169689Skan if (elt) 972169689Skan { 973169689Skan head->current = elt; 974169689Skan head->indx = head->current->indx; 975169689Skan } 976169689Skan} 977169689Skan 978169689Skan/* A = ~A & B. */ 979169689Skan 980169689Skanvoid 981169689Skanbitmap_compl_and_into (bitmap a, bitmap b) 982169689Skan{ 983169689Skan bitmap_element *a_elt = a->first; 984169689Skan bitmap_element *b_elt = b->first; 985169689Skan bitmap_element *a_prev = NULL; 986169689Skan bitmap_element *next; 987169689Skan 988169689Skan gcc_assert (a != b); 989169689Skan 990169689Skan if (bitmap_empty_p (a)) 991169689Skan { 992169689Skan bitmap_copy (a, b); 993169689Skan return; 994169689Skan } 995169689Skan if (bitmap_empty_p (b)) 996169689Skan { 997169689Skan bitmap_clear (a); 998169689Skan return; 999169689Skan } 1000169689Skan 1001169689Skan while (a_elt || b_elt) 1002169689Skan { 1003169689Skan if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) 100450397Sobrien { 1005169689Skan /* A is before B. Remove A */ 1006169689Skan next = a_elt->next; 1007169689Skan a_prev = a_elt->prev; 1008169689Skan bitmap_element_free (a, a_elt); 1009169689Skan a_elt = next; 101050397Sobrien } 1011169689Skan else if (!a_elt || b_elt->indx < a_elt->indx) 1012169689Skan { 1013169689Skan /* B is before A. Copy B. */ 1014169689Skan next = bitmap_elt_insert_after (a, a_prev, b_elt->indx); 1015169689Skan memcpy (next->bits, b_elt->bits, sizeof (next->bits)); 1016169689Skan a_prev = next; 1017169689Skan b_elt = b_elt->next; 1018169689Skan } 101990075Sobrien else 102090075Sobrien { 1021169689Skan /* Matching elts, generate A = ~A & B. */ 1022169689Skan unsigned ix; 1023169689Skan BITMAP_WORD ior = 0; 1024169689Skan 1025169689Skan for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1026169689Skan { 1027169689Skan BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; 1028169689Skan BITMAP_WORD r = b_elt->bits[ix] ^ cleared; 1029169689Skan 1030169689Skan a_elt->bits[ix] = r; 1031169689Skan ior |= r; 1032169689Skan } 1033169689Skan next = a_elt->next; 1034169689Skan if (!ior) 1035169689Skan bitmap_element_free (a, a_elt); 1036169689Skan else 1037169689Skan a_prev = a_elt; 1038169689Skan a_elt = next; 1039169689Skan b_elt = b_elt->next; 104090075Sobrien } 104150397Sobrien } 1042169689Skan gcc_assert (!a->current == !a->first); 1043169689Skan gcc_assert (!a->current || a->indx == a->current->indx); 1044169689Skan return; 1045169689Skan} 104650397Sobrien 1047169689Skan/* DST = A | B. Return true if DST changes. */ 1048169689Skan 1049169689Skanbool 1050169689Skanbitmap_ior (bitmap dst, bitmap a, bitmap b) 1051169689Skan{ 1052169689Skan bitmap_element *dst_elt = dst->first; 1053169689Skan bitmap_element *a_elt = a->first; 1054169689Skan bitmap_element *b_elt = b->first; 1055169689Skan bitmap_element *dst_prev = NULL; 1056169689Skan bool changed = false; 1057169689Skan 1058169689Skan gcc_assert (dst != a && dst != b); 1059169689Skan 1060169689Skan while (a_elt || b_elt) 106150397Sobrien { 1062169689Skan if (a_elt && b_elt && a_elt->indx == b_elt->indx) 1063117395Skan { 1064169689Skan /* Matching elts, generate A | B. */ 1065169689Skan unsigned ix; 1066169689Skan 1067169689Skan if (!changed && dst_elt && dst_elt->indx == a_elt->indx) 1068169689Skan { 1069169689Skan for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1070169689Skan { 1071169689Skan BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; 1072169689Skan 1073169689Skan if (r != dst_elt->bits[ix]) 1074169689Skan { 1075169689Skan dst_elt->bits[ix] = r; 1076169689Skan changed = true; 1077169689Skan } 1078169689Skan } 1079169689Skan } 1080169689Skan else 1081169689Skan { 1082169689Skan changed = true; 1083169689Skan if (!dst_elt) 1084169689Skan dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); 1085169689Skan else 1086169689Skan dst_elt->indx = a_elt->indx; 1087169689Skan for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1088169689Skan { 1089169689Skan BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; 1090169689Skan 1091169689Skan dst_elt->bits[ix] = r; 1092169689Skan } 1093169689Skan } 1094169689Skan a_elt = a_elt->next; 1095169689Skan b_elt = b_elt->next; 1096169689Skan dst_prev = dst_elt; 1097169689Skan dst_elt = dst_elt->next; 1098117395Skan } 1099117395Skan else 1100117395Skan { 1101169689Skan /* Copy a single element. */ 1102169689Skan bitmap_element *src; 1103169689Skan 1104169689Skan if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) 1105169689Skan { 1106169689Skan src = a_elt; 1107169689Skan a_elt = a_elt->next; 1108169689Skan } 1109169689Skan else 1110169689Skan { 1111169689Skan src = b_elt; 1112169689Skan b_elt = b_elt->next; 1113169689Skan } 1114169689Skan 1115169689Skan if (!changed && dst_elt && dst_elt->indx == src->indx) 1116169689Skan { 1117169689Skan unsigned ix; 1118169689Skan 1119169689Skan for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1120169689Skan if (src->bits[ix] != dst_elt->bits[ix]) 1121169689Skan { 1122169689Skan dst_elt->bits[ix] = src->bits[ix]; 1123169689Skan changed = true; 1124169689Skan } 1125169689Skan } 1126169689Skan else 1127169689Skan { 1128169689Skan changed = true; 1129169689Skan if (!dst_elt) 1130169689Skan dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx); 1131169689Skan else 1132169689Skan dst_elt->indx = src->indx; 1133169689Skan memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits)); 1134169689Skan } 1135169689Skan 1136169689Skan dst_prev = dst_elt; 1137169689Skan dst_elt = dst_elt->next; 1138117395Skan } 113950397Sobrien } 114050397Sobrien 1141169689Skan if (dst_elt) 1142169689Skan { 1143169689Skan changed = true; 1144169689Skan bitmap_elt_clear_from (dst, dst_elt); 1145169689Skan } 1146169689Skan gcc_assert (!dst->current == !dst->first); 1147169689Skan if (dst->current) 1148169689Skan dst->indx = dst->current->indx; 1149169689Skan return changed; 1150169689Skan} 115190075Sobrien 1152169689Skan/* A |= B. Return true if A changes. */ 1153169689Skan 1154169689Skanbool 1155169689Skanbitmap_ior_into (bitmap a, bitmap b) 1156169689Skan{ 1157169689Skan bitmap_element *a_elt = a->first; 1158169689Skan bitmap_element *b_elt = b->first; 1159169689Skan bitmap_element *a_prev = NULL; 1160169689Skan bool changed = false; 1161169689Skan 1162169689Skan if (a == b) 1163169689Skan return false; 1164169689Skan 1165169689Skan while (b_elt) 1166169689Skan { 1167169689Skan if (!a_elt || b_elt->indx < a_elt->indx) 1168169689Skan { 1169169689Skan /* Copy b_elt. */ 1170169689Skan bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx); 1171169689Skan memcpy (dst->bits, b_elt->bits, sizeof (dst->bits)); 1172169689Skan a_prev = dst; 1173169689Skan b_elt = b_elt->next; 1174169689Skan changed = true; 1175169689Skan } 1176169689Skan else if (a_elt->indx < b_elt->indx) 1177169689Skan { 1178169689Skan a_prev = a_elt; 1179169689Skan a_elt = a_elt->next; 1180169689Skan } 1181169689Skan else 1182169689Skan { 1183169689Skan /* Matching elts, generate A |= B. */ 1184169689Skan unsigned ix; 1185169689Skan 1186169689Skan if (changed) 1187169689Skan for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1188169689Skan { 1189169689Skan BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; 1190169689Skan 1191169689Skan a_elt->bits[ix] = r; 1192169689Skan } 1193169689Skan else 1194169689Skan for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1195169689Skan { 1196169689Skan BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; 1197169689Skan 1198169689Skan if (a_elt->bits[ix] != r) 1199169689Skan { 1200169689Skan changed = true; 1201169689Skan a_elt->bits[ix] = r; 1202169689Skan } 1203169689Skan } 1204169689Skan b_elt = b_elt->next; 1205169689Skan a_prev = a_elt; 1206169689Skan a_elt = a_elt->next; 1207169689Skan } 1208169689Skan } 1209169689Skan gcc_assert (!a->current == !a->first); 1210169689Skan if (a->current) 1211169689Skan a->indx = a->current->indx; 121290075Sobrien return changed; 121350397Sobrien} 121490075Sobrien 1215169689Skan/* DST = A ^ B */ 121690075Sobrien 1217169689Skanvoid 1218169689Skanbitmap_xor (bitmap dst, bitmap a, bitmap b) 121990075Sobrien{ 1220169689Skan bitmap_element *dst_elt = dst->first; 1221169689Skan bitmap_element *a_elt = a->first; 1222169689Skan bitmap_element *b_elt = b->first; 1223169689Skan bitmap_element *dst_prev = NULL; 122490075Sobrien 1225169689Skan gcc_assert (dst != a && dst != b); 1226169689Skan if (a == b) 1227169689Skan { 1228169689Skan bitmap_clear (dst); 1229169689Skan return; 1230169689Skan } 123190075Sobrien 1232169689Skan while (a_elt || b_elt) 1233169689Skan { 1234169689Skan if (a_elt && b_elt && a_elt->indx == b_elt->indx) 1235169689Skan { 1236169689Skan /* Matching elts, generate A ^ B. */ 1237169689Skan unsigned ix; 1238169689Skan BITMAP_WORD ior = 0; 1239169689Skan 1240169689Skan if (!dst_elt) 1241169689Skan dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); 1242169689Skan else 1243169689Skan dst_elt->indx = a_elt->indx; 1244169689Skan for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1245169689Skan { 1246169689Skan BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; 1247169689Skan 1248169689Skan ior |= r; 1249169689Skan dst_elt->bits[ix] = r; 1250169689Skan } 1251169689Skan a_elt = a_elt->next; 1252169689Skan b_elt = b_elt->next; 1253169689Skan if (ior) 1254169689Skan { 1255169689Skan dst_prev = dst_elt; 1256169689Skan dst_elt = dst_elt->next; 1257169689Skan } 1258169689Skan } 1259169689Skan else 1260169689Skan { 1261169689Skan /* Copy a single element. */ 1262169689Skan bitmap_element *src; 1263169689Skan 1264169689Skan if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) 1265169689Skan { 1266169689Skan src = a_elt; 1267169689Skan a_elt = a_elt->next; 1268169689Skan } 1269169689Skan else 1270169689Skan { 1271169689Skan src = b_elt; 1272169689Skan b_elt = b_elt->next; 1273169689Skan } 1274169689Skan 1275169689Skan if (!dst_elt) 1276169689Skan dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx); 1277169689Skan else 1278169689Skan dst_elt->indx = src->indx; 1279169689Skan memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits)); 1280169689Skan dst_prev = dst_elt; 1281169689Skan dst_elt = dst_elt->next; 1282169689Skan } 1283169689Skan } 1284169689Skan bitmap_elt_clear_from (dst, dst_elt); 1285169689Skan gcc_assert (!dst->current == !dst->first); 1286169689Skan if (dst->current) 1287169689Skan dst->indx = dst->current->indx; 128890075Sobrien} 128950397Sobrien 1290169689Skan/* A ^= B */ 1291169689Skan 129250397Sobrienvoid 1293169689Skanbitmap_xor_into (bitmap a, bitmap b) 129450397Sobrien{ 1295169689Skan bitmap_element *a_elt = a->first; 1296169689Skan bitmap_element *b_elt = b->first; 1297169689Skan bitmap_element *a_prev = NULL; 129850397Sobrien 1299169689Skan if (a == b) 1300169689Skan { 1301169689Skan bitmap_clear (a); 1302169689Skan return; 1303169689Skan } 130450397Sobrien 1305169689Skan while (b_elt) 1306169689Skan { 1307169689Skan if (!a_elt || b_elt->indx < a_elt->indx) 1308169689Skan { 1309169689Skan /* Copy b_elt. */ 1310169689Skan bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx); 1311169689Skan memcpy (dst->bits, b_elt->bits, sizeof (dst->bits)); 1312169689Skan a_prev = dst; 1313169689Skan b_elt = b_elt->next; 1314169689Skan } 1315169689Skan else if (a_elt->indx < b_elt->indx) 1316169689Skan { 1317169689Skan a_prev = a_elt; 1318169689Skan a_elt = a_elt->next; 1319169689Skan } 1320169689Skan else 1321169689Skan { 1322169689Skan /* Matching elts, generate A ^= B. */ 1323169689Skan unsigned ix; 1324169689Skan BITMAP_WORD ior = 0; 1325169689Skan bitmap_element *next = a_elt->next; 1326169689Skan 1327169689Skan for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1328169689Skan { 1329169689Skan BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; 1330169689Skan 1331169689Skan ior |= r; 1332169689Skan a_elt->bits[ix] = r; 1333169689Skan } 1334169689Skan b_elt = b_elt->next; 1335169689Skan if (ior) 1336169689Skan a_prev = a_elt; 1337169689Skan else 1338169689Skan bitmap_element_free (a, a_elt); 1339169689Skan a_elt = next; 1340169689Skan } 1341169689Skan } 1342169689Skan gcc_assert (!a->current == !a->first); 1343169689Skan if (a->current) 1344169689Skan a->indx = a->current->indx; 134550397Sobrien} 134690075Sobrien 1347169689Skan/* Return true if two bitmaps are identical. 1348169689Skan We do not bother with a check for pointer equality, as that never 1349169689Skan occurs in practice. */ 1350169689Skan 1351169689Skanbool 1352169689Skanbitmap_equal_p (bitmap a, bitmap b) 135390075Sobrien{ 1354169689Skan bitmap_element *a_elt; 1355169689Skan bitmap_element *b_elt; 1356169689Skan unsigned ix; 1357169689Skan 1358169689Skan for (a_elt = a->first, b_elt = b->first; 1359169689Skan a_elt && b_elt; 1360169689Skan a_elt = a_elt->next, b_elt = b_elt->next) 1361169689Skan { 1362169689Skan if (a_elt->indx != b_elt->indx) 1363169689Skan return false; 1364169689Skan for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1365169689Skan if (a_elt->bits[ix] != b_elt->bits[ix]) 1366169689Skan return false; 1367169689Skan } 1368169689Skan return !a_elt && !b_elt; 1369169689Skan} 1370169689Skan 1371169689Skan/* Return true if A AND B is not empty. */ 1372169689Skan 1373169689Skanbool 1374169689Skanbitmap_intersect_p (bitmap a, bitmap b) 1375169689Skan{ 1376169689Skan bitmap_element *a_elt; 1377169689Skan bitmap_element *b_elt; 1378169689Skan unsigned ix; 1379169689Skan 1380169689Skan for (a_elt = a->first, b_elt = b->first; 1381169689Skan a_elt && b_elt;) 1382169689Skan { 1383169689Skan if (a_elt->indx < b_elt->indx) 1384169689Skan a_elt = a_elt->next; 1385169689Skan else if (b_elt->indx < a_elt->indx) 1386169689Skan b_elt = b_elt->next; 1387169689Skan else 1388169689Skan { 1389169689Skan for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1390169689Skan if (a_elt->bits[ix] & b_elt->bits[ix]) 1391169689Skan return true; 1392169689Skan a_elt = a_elt->next; 1393169689Skan b_elt = b_elt->next; 1394169689Skan } 1395169689Skan } 1396169689Skan return false; 1397169689Skan} 1398169689Skan 1399169689Skan/* Return true if A AND NOT B is not empty. */ 1400169689Skan 1401169689Skanbool 1402169689Skanbitmap_intersect_compl_p (bitmap a, bitmap b) 1403169689Skan{ 1404169689Skan bitmap_element *a_elt; 1405169689Skan bitmap_element *b_elt; 1406169689Skan unsigned ix; 1407169689Skan for (a_elt = a->first, b_elt = b->first; 1408169689Skan a_elt && b_elt;) 1409169689Skan { 1410169689Skan if (a_elt->indx < b_elt->indx) 1411169689Skan return true; 1412169689Skan else if (b_elt->indx < a_elt->indx) 1413169689Skan b_elt = b_elt->next; 1414169689Skan else 1415169689Skan { 1416169689Skan for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1417169689Skan if (a_elt->bits[ix] & ~b_elt->bits[ix]) 1418169689Skan return true; 1419169689Skan a_elt = a_elt->next; 1420169689Skan b_elt = b_elt->next; 1421169689Skan } 1422169689Skan } 1423169689Skan return a_elt != NULL; 1424169689Skan} 1425169689Skan 1426169689Skan 1427169689Skan/* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */ 1428169689Skan 1429169689Skanbool 1430169689Skanbitmap_ior_and_compl (bitmap dst, bitmap a, bitmap from1, bitmap from2) 1431169689Skan{ 143290075Sobrien bitmap_head tmp; 1433169689Skan bool changed; 143490075Sobrien 1435169689Skan bitmap_initialize (&tmp, &bitmap_default_obstack); 1436169689Skan bitmap_and_compl (&tmp, from1, from2); 1437169689Skan changed = bitmap_ior (dst, a, &tmp); 143890075Sobrien bitmap_clear (&tmp); 143990075Sobrien 144090075Sobrien return changed; 144190075Sobrien} 144250397Sobrien 1443169689Skan/* A |= (FROM1 & ~FROM2). Return true if A changes. */ 1444169689Skan 1445169689Skanbool 1446169689Skanbitmap_ior_and_compl_into (bitmap a, bitmap from1, bitmap from2) 144750397Sobrien{ 1448169689Skan bitmap_head tmp; 1449169689Skan bool changed; 1450132718Skan 1451169689Skan bitmap_initialize (&tmp, &bitmap_default_obstack); 1452169689Skan bitmap_and_compl (&tmp, from1, from2); 1453169689Skan changed = bitmap_ior_into (a, &tmp); 1454169689Skan bitmap_clear (&tmp); 145550397Sobrien 1456169689Skan return changed; 145750397Sobrien} 145850397Sobrien 145950397Sobrien/* Debugging function to print out the contents of a bitmap. */ 146050397Sobrien 146150397Sobrienvoid 1462132718Skandebug_bitmap_file (FILE *file, bitmap head) 146350397Sobrien{ 146450397Sobrien bitmap_element *ptr; 146550397Sobrien 1466169689Skan fprintf (file, "\nfirst = %p current = %p indx = %u\n", 1467132718Skan (void *) head->first, (void *) head->current, head->indx); 146850397Sobrien 146950397Sobrien for (ptr = head->first; ptr; ptr = ptr->next) 147050397Sobrien { 1471117395Skan unsigned int i, j, col = 26; 147250397Sobrien 1473169689Skan fprintf (file, "\t%p next = %p prev = %p indx = %u\n\t\tbits = {", 1474132718Skan (void*) ptr, (void*) ptr->next, (void*) ptr->prev, ptr->indx); 147550397Sobrien 147650397Sobrien for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) 1477117395Skan for (j = 0; j < BITMAP_WORD_BITS; j++) 147890075Sobrien if ((ptr->bits[i] >> j) & 1) 147950397Sobrien { 148050397Sobrien if (col > 70) 148150397Sobrien { 148250397Sobrien fprintf (file, "\n\t\t\t"); 148350397Sobrien col = 24; 148450397Sobrien } 148550397Sobrien 148650397Sobrien fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS 1487117395Skan + i * BITMAP_WORD_BITS + j)); 148850397Sobrien col += 4; 148950397Sobrien } 149050397Sobrien 149150397Sobrien fprintf (file, " }\n"); 149250397Sobrien } 149350397Sobrien} 149490075Sobrien 149550397Sobrien/* Function to be called from the debugger to print the contents 149650397Sobrien of a bitmap. */ 149750397Sobrien 149850397Sobrienvoid 1499132718Skandebug_bitmap (bitmap head) 150050397Sobrien{ 150190075Sobrien debug_bitmap_file (stdout, head); 150250397Sobrien} 150390075Sobrien 150490075Sobrien/* Function to print out the contents of a bitmap. Unlike debug_bitmap_file, 150550397Sobrien it does not print anything but the bits. */ 150650397Sobrien 150750397Sobrienvoid 1508132718Skanbitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix) 150950397Sobrien{ 151052284Sobrien const char *comma = ""; 1511169689Skan unsigned i; 1512169689Skan bitmap_iterator bi; 151350397Sobrien 151450397Sobrien fputs (prefix, file); 1515169689Skan EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi) 1516169689Skan { 1517169689Skan fprintf (file, "%s%d", comma, i); 1518169689Skan comma = ", "; 1519169689Skan } 152050397Sobrien fputs (suffix, file); 152150397Sobrien} 1522117395Skan 1523169689Skan/* Compute hash of bitmap (for purposes of hashing). */ 1524169689Skanhashval_t 1525169689Skanbitmap_hash (bitmap head) 1526169689Skan{ 1527169689Skan bitmap_element *ptr; 1528169689Skan BITMAP_WORD hash = 0; 1529169689Skan int ix; 1530169689Skan 1531169689Skan for (ptr = head->first; ptr; ptr = ptr->next) 1532169689Skan { 1533169689Skan hash ^= ptr->indx; 1534169689Skan for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) 1535169689Skan hash ^= ptr->bits[ix]; 1536169689Skan } 1537169689Skan return (hashval_t)hash; 1538169689Skan} 1539169689Skan 1540117395Skan#include "gt-bitmap.h" 1541