1*c87b03e5Sespie /* Functions to support general ended bitmaps. 2*c87b03e5Sespie Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003 3*c87b03e5Sespie Free Software Foundation, Inc. 4*c87b03e5Sespie 5*c87b03e5Sespie This file is part of GCC. 6*c87b03e5Sespie 7*c87b03e5Sespie GCC is free software; you can redistribute it and/or modify it under 8*c87b03e5Sespie the terms of the GNU General Public License as published by the Free 9*c87b03e5Sespie Software Foundation; either version 2, or (at your option) any later 10*c87b03e5Sespie version. 11*c87b03e5Sespie 12*c87b03e5Sespie GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13*c87b03e5Sespie WARRANTY; without even the implied warranty of MERCHANTABILITY or 14*c87b03e5Sespie FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15*c87b03e5Sespie for more details. 16*c87b03e5Sespie 17*c87b03e5Sespie You should have received a copy of the GNU General Public License 18*c87b03e5Sespie along with GCC; see the file COPYING. If not, write to the Free 19*c87b03e5Sespie Software Foundation, 59 Temple Place - Suite 330, Boston, MA 20*c87b03e5Sespie 02111-1307, USA. */ 21*c87b03e5Sespie 22*c87b03e5Sespie #ifndef GCC_BITMAP_H 23*c87b03e5Sespie #define GCC_BITMAP_H 24*c87b03e5Sespie 25*c87b03e5Sespie /* Fundamental storage type for bitmap. */ 26*c87b03e5Sespie 27*c87b03e5Sespie /* typedef unsigned HOST_WIDE_INT BITMAP_WORD; */ 28*c87b03e5Sespie /* #define nBITMAP_WORD_BITS HOST_BITS_PER_WIDE_INT */ 29*c87b03e5Sespie typedef unsigned long BITMAP_WORD; 30*c87b03e5Sespie #define nBITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG) 31*c87b03e5Sespie #define BITMAP_WORD_BITS (unsigned) nBITMAP_WORD_BITS 32*c87b03e5Sespie 33*c87b03e5Sespie /* Number of words to use for each element in the linked list. */ 34*c87b03e5Sespie 35*c87b03e5Sespie #ifndef BITMAP_ELEMENT_WORDS 36*c87b03e5Sespie #define BITMAP_ELEMENT_WORDS ((128 + nBITMAP_WORD_BITS - 1) / nBITMAP_WORD_BITS) 37*c87b03e5Sespie #endif 38*c87b03e5Sespie 39*c87b03e5Sespie /* Number of bits in each actual element of a bitmap. We get slightly better 40*c87b03e5Sespie code for bit % BITMAP_ELEMENT_ALL_BITS and bit / BITMAP_ELEMENT_ALL_BITS if 41*c87b03e5Sespie bits is unsigned, assuming it is a power of 2. */ 42*c87b03e5Sespie 43*c87b03e5Sespie #define BITMAP_ELEMENT_ALL_BITS \ 44*c87b03e5Sespie ((unsigned) (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)) 45*c87b03e5Sespie 46*c87b03e5Sespie /* Bitmap set element. We use a linked list to hold only the bits that 47*c87b03e5Sespie are set. This allows for use to grow the bitset dynamically without 48*c87b03e5Sespie having to realloc and copy a giant bit array. The `prev' field is 49*c87b03e5Sespie undefined for an element on the free list. */ 50*c87b03e5Sespie 51*c87b03e5Sespie typedef struct bitmap_element_def GTY(()) 52*c87b03e5Sespie { 53*c87b03e5Sespie struct bitmap_element_def *next; /* Next element. */ 54*c87b03e5Sespie struct bitmap_element_def *prev; /* Previous element. */ 55*c87b03e5Sespie unsigned int indx; /* regno/BITMAP_ELEMENT_ALL_BITS. */ 56*c87b03e5Sespie BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */ 57*c87b03e5Sespie } bitmap_element; 58*c87b03e5Sespie 59*c87b03e5Sespie /* Head of bitmap linked list. */ 60*c87b03e5Sespie typedef struct bitmap_head_def GTY(()) { 61*c87b03e5Sespie bitmap_element *first; /* First element in linked list. */ 62*c87b03e5Sespie bitmap_element *current; /* Last element looked at. */ 63*c87b03e5Sespie unsigned int indx; /* Index of last element looked at. */ 64*c87b03e5Sespie int using_obstack; /* Are we using an obstack or ggc for 65*c87b03e5Sespie allocation? */ 66*c87b03e5Sespie } bitmap_head; 67*c87b03e5Sespie typedef struct bitmap_head_def *bitmap; 68*c87b03e5Sespie 69*c87b03e5Sespie /* Enumeration giving the various operations we support. */ 70*c87b03e5Sespie enum bitmap_bits { 71*c87b03e5Sespie BITMAP_AND, /* TO = FROM1 & FROM2 */ 72*c87b03e5Sespie BITMAP_AND_COMPL, /* TO = FROM1 & ~ FROM2 */ 73*c87b03e5Sespie BITMAP_IOR, /* TO = FROM1 | FROM2 */ 74*c87b03e5Sespie BITMAP_XOR, /* TO = FROM1 ^ FROM2 */ 75*c87b03e5Sespie BITMAP_IOR_COMPL /* TO = FROM1 | ~FROM2 */ 76*c87b03e5Sespie }; 77*c87b03e5Sespie 78*c87b03e5Sespie /* Global data */ 79*c87b03e5Sespie extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */ 80*c87b03e5Sespie 81*c87b03e5Sespie /* Clear a bitmap by freeing up the linked list. */ 82*c87b03e5Sespie extern void bitmap_clear PARAMS ((bitmap)); 83*c87b03e5Sespie 84*c87b03e5Sespie /* Copy a bitmap to another bitmap. */ 85*c87b03e5Sespie extern void bitmap_copy PARAMS ((bitmap, bitmap)); 86*c87b03e5Sespie 87*c87b03e5Sespie /* True if two bitmaps are identical. */ 88*c87b03e5Sespie extern int bitmap_equal_p PARAMS ((bitmap, bitmap)); 89*c87b03e5Sespie 90*c87b03e5Sespie /* Perform an operation on two bitmaps, yielding a third. */ 91*c87b03e5Sespie extern int bitmap_operation PARAMS ((bitmap, bitmap, bitmap, enum bitmap_bits)); 92*c87b03e5Sespie 93*c87b03e5Sespie /* `or' into one bitmap the `and' of a second bitmap witih the complement 94*c87b03e5Sespie of a third. */ 95*c87b03e5Sespie extern void bitmap_ior_and_compl PARAMS ((bitmap, bitmap, bitmap)); 96*c87b03e5Sespie 97*c87b03e5Sespie /* Clear a single register in a register set. */ 98*c87b03e5Sespie extern void bitmap_clear_bit PARAMS ((bitmap, int)); 99*c87b03e5Sespie 100*c87b03e5Sespie /* Set a single register in a register set. */ 101*c87b03e5Sespie extern void bitmap_set_bit PARAMS ((bitmap, int)); 102*c87b03e5Sespie 103*c87b03e5Sespie /* Return true if a register is set in a register set. */ 104*c87b03e5Sespie extern int bitmap_bit_p PARAMS ((bitmap, int)); 105*c87b03e5Sespie 106*c87b03e5Sespie /* Debug functions to print a bitmap linked list. */ 107*c87b03e5Sespie extern void debug_bitmap PARAMS ((bitmap)); 108*c87b03e5Sespie extern void debug_bitmap_file PARAMS ((FILE *, bitmap)); 109*c87b03e5Sespie 110*c87b03e5Sespie /* Print a bitmap */ 111*c87b03e5Sespie extern void bitmap_print PARAMS ((FILE *, bitmap, const char *, const char *)); 112*c87b03e5Sespie 113*c87b03e5Sespie /* Initialize a bitmap header. If HEAD is NULL, a new header will be 114*c87b03e5Sespie allocated. USING_OBSTACK indicates how elements should be allocated. */ 115*c87b03e5Sespie extern bitmap bitmap_initialize PARAMS ((bitmap head, 116*c87b03e5Sespie int using_obstack)); 117*c87b03e5Sespie 118*c87b03e5Sespie /* Release all memory used by the bitmap obstack. */ 119*c87b03e5Sespie extern void bitmap_release_memory PARAMS ((void)); 120*c87b03e5Sespie 121*c87b03e5Sespie /* A few compatibility/functions macros for compatibility with sbitmaps */ 122*c87b03e5Sespie #define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n") 123*c87b03e5Sespie #define bitmap_zero(a) bitmap_clear (a) 124*c87b03e5Sespie #define bitmap_a_or_b(a,b,c) bitmap_operation (a, b, c, BITMAP_IOR) 125*c87b03e5Sespie #define bitmap_a_and_b(a,b,c) bitmap_operation (a, b, c, BITMAP_AND) 126*c87b03e5Sespie extern int bitmap_union_of_diff PARAMS((bitmap, bitmap, bitmap, bitmap)); 127*c87b03e5Sespie extern int bitmap_first_set_bit PARAMS((bitmap)); 128*c87b03e5Sespie extern int bitmap_last_set_bit PARAMS((bitmap)); 129*c87b03e5Sespie 130*c87b03e5Sespie /* Allocate a bitmap with oballoc. */ 131*c87b03e5Sespie #define BITMAP_OBSTACK_ALLOC(OBSTACK) \ 132*c87b03e5Sespie bitmap_initialize ((bitmap) obstack_alloc (OBSTACK, sizeof (bitmap_head)), 1) 133*c87b03e5Sespie 134*c87b03e5Sespie /* Allocate a bitmap with ggc_alloc. */ 135*c87b03e5Sespie #define BITMAP_GGC_ALLOC() \ 136*c87b03e5Sespie bitmap_initialize (NULL, 0) 137*c87b03e5Sespie 138*c87b03e5Sespie /* Allocate a bitmap with xmalloc. */ 139*c87b03e5Sespie #define BITMAP_XMALLOC() \ 140*c87b03e5Sespie bitmap_initialize ((bitmap) xmalloc (sizeof (bitmap_head)), 1) 141*c87b03e5Sespie 142*c87b03e5Sespie /* Do any cleanup needed on a bitmap when it is no longer used. */ 143*c87b03e5Sespie #define BITMAP_FREE(BITMAP) \ 144*c87b03e5Sespie do { \ 145*c87b03e5Sespie if (BITMAP) \ 146*c87b03e5Sespie { \ 147*c87b03e5Sespie bitmap_clear (BITMAP); \ 148*c87b03e5Sespie (BITMAP) = 0; \ 149*c87b03e5Sespie } \ 150*c87b03e5Sespie } while (0) 151*c87b03e5Sespie 152*c87b03e5Sespie /* Do any cleanup needed on an xmalloced bitmap when it is no longer used. */ 153*c87b03e5Sespie #define BITMAP_XFREE(BITMAP) \ 154*c87b03e5Sespie do { \ 155*c87b03e5Sespie if (BITMAP) \ 156*c87b03e5Sespie { \ 157*c87b03e5Sespie bitmap_clear (BITMAP); \ 158*c87b03e5Sespie free (BITMAP); \ 159*c87b03e5Sespie (BITMAP) = 0; \ 160*c87b03e5Sespie } \ 161*c87b03e5Sespie } while (0) 162*c87b03e5Sespie 163*c87b03e5Sespie /* Do any one-time initializations needed for bitmaps. */ 164*c87b03e5Sespie #define BITMAP_INIT_ONCE() 165*c87b03e5Sespie 166*c87b03e5Sespie /* Loop over all bits in BITMAP, starting with MIN, setting BITNUM to the 167*c87b03e5Sespie bit number and executing CODE for all bits that are set. */ 168*c87b03e5Sespie 169*c87b03e5Sespie #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE) \ 170*c87b03e5Sespie do { \ 171*c87b03e5Sespie bitmap_element *ptr_ = (BITMAP)->first; \ 172*c87b03e5Sespie unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \ 173*c87b03e5Sespie unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \ 174*c87b03e5Sespie unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \ 175*c87b03e5Sespie \ 176*c87b03e5Sespie \ 177*c87b03e5Sespie /* Find the block the minimum bit is in. */ \ 178*c87b03e5Sespie while (ptr_ != 0 && ptr_->indx < indx_) \ 179*c87b03e5Sespie ptr_ = ptr_->next; \ 180*c87b03e5Sespie \ 181*c87b03e5Sespie if (ptr_ != 0 && ptr_->indx != indx_) \ 182*c87b03e5Sespie { \ 183*c87b03e5Sespie bit_num_ = 0; \ 184*c87b03e5Sespie word_num_ = 0; \ 185*c87b03e5Sespie } \ 186*c87b03e5Sespie \ 187*c87b03e5Sespie for (; ptr_ != 0; ptr_ = ptr_->next) \ 188*c87b03e5Sespie { \ 189*c87b03e5Sespie for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ 190*c87b03e5Sespie { \ 191*c87b03e5Sespie BITMAP_WORD word_ = ptr_->bits[word_num_]; \ 192*c87b03e5Sespie \ 193*c87b03e5Sespie if (word_ != 0) \ 194*c87b03e5Sespie { \ 195*c87b03e5Sespie for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \ 196*c87b03e5Sespie { \ 197*c87b03e5Sespie BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \ 198*c87b03e5Sespie \ 199*c87b03e5Sespie if ((word_ & mask_) != 0) \ 200*c87b03e5Sespie { \ 201*c87b03e5Sespie word_ &= ~ mask_; \ 202*c87b03e5Sespie (BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS \ 203*c87b03e5Sespie + word_num_ * BITMAP_WORD_BITS \ 204*c87b03e5Sespie + bit_num_); \ 205*c87b03e5Sespie CODE; \ 206*c87b03e5Sespie \ 207*c87b03e5Sespie if (word_ == 0) \ 208*c87b03e5Sespie break; \ 209*c87b03e5Sespie } \ 210*c87b03e5Sespie } \ 211*c87b03e5Sespie } \ 212*c87b03e5Sespie \ 213*c87b03e5Sespie bit_num_ = 0; \ 214*c87b03e5Sespie } \ 215*c87b03e5Sespie \ 216*c87b03e5Sespie word_num_ = 0; \ 217*c87b03e5Sespie } \ 218*c87b03e5Sespie } while (0) 219*c87b03e5Sespie 220*c87b03e5Sespie /* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting 221*c87b03e5Sespie BITNUM to the bit number and executing CODE for all bits that are set in 222*c87b03e5Sespie the first bitmap and not set in the second. */ 223*c87b03e5Sespie 224*c87b03e5Sespie #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \ 225*c87b03e5Sespie do { \ 226*c87b03e5Sespie bitmap_element *ptr1_ = (BITMAP1)->first; \ 227*c87b03e5Sespie bitmap_element *ptr2_ = (BITMAP2)->first; \ 228*c87b03e5Sespie unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \ 229*c87b03e5Sespie unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \ 230*c87b03e5Sespie unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \ 231*c87b03e5Sespie \ 232*c87b03e5Sespie /* Find the block the minimum bit is in in the first bitmap. */ \ 233*c87b03e5Sespie while (ptr1_ != 0 && ptr1_->indx < indx_) \ 234*c87b03e5Sespie ptr1_ = ptr1_->next; \ 235*c87b03e5Sespie \ 236*c87b03e5Sespie if (ptr1_ != 0 && ptr1_->indx != indx_) \ 237*c87b03e5Sespie { \ 238*c87b03e5Sespie bit_num_ = 0; \ 239*c87b03e5Sespie word_num_ = 0; \ 240*c87b03e5Sespie } \ 241*c87b03e5Sespie \ 242*c87b03e5Sespie for (; ptr1_ != 0 ; ptr1_ = ptr1_->next) \ 243*c87b03e5Sespie { \ 244*c87b03e5Sespie /* Advance BITMAP2 to the equivalent link, using an all \ 245*c87b03e5Sespie zero element if an equivalent link doesn't exist. */ \ 246*c87b03e5Sespie bitmap_element *tmp2_; \ 247*c87b03e5Sespie \ 248*c87b03e5Sespie while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx) \ 249*c87b03e5Sespie ptr2_ = ptr2_->next; \ 250*c87b03e5Sespie \ 251*c87b03e5Sespie tmp2_ = ((ptr2_ != 0 && ptr2_->indx == ptr1_->indx) \ 252*c87b03e5Sespie ? ptr2_ : &bitmap_zero_bits); \ 253*c87b03e5Sespie \ 254*c87b03e5Sespie for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ 255*c87b03e5Sespie { \ 256*c87b03e5Sespie BITMAP_WORD word_ = (ptr1_->bits[word_num_] \ 257*c87b03e5Sespie & ~ tmp2_->bits[word_num_]); \ 258*c87b03e5Sespie if (word_ != 0) \ 259*c87b03e5Sespie { \ 260*c87b03e5Sespie for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \ 261*c87b03e5Sespie { \ 262*c87b03e5Sespie BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \ 263*c87b03e5Sespie \ 264*c87b03e5Sespie if ((word_ & mask_) != 0) \ 265*c87b03e5Sespie { \ 266*c87b03e5Sespie word_ &= ~ mask_; \ 267*c87b03e5Sespie (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \ 268*c87b03e5Sespie + word_num_ * BITMAP_WORD_BITS \ 269*c87b03e5Sespie + bit_num_); \ 270*c87b03e5Sespie \ 271*c87b03e5Sespie CODE; \ 272*c87b03e5Sespie if (word_ == 0) \ 273*c87b03e5Sespie break; \ 274*c87b03e5Sespie } \ 275*c87b03e5Sespie } \ 276*c87b03e5Sespie } \ 277*c87b03e5Sespie \ 278*c87b03e5Sespie bit_num_ = 0; \ 279*c87b03e5Sespie } \ 280*c87b03e5Sespie \ 281*c87b03e5Sespie word_num_ = 0; \ 282*c87b03e5Sespie } \ 283*c87b03e5Sespie } while (0) 284*c87b03e5Sespie 285*c87b03e5Sespie /* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting 286*c87b03e5Sespie BITNUM to the bit number and executing CODE for all bits that are set in 287*c87b03e5Sespie the both bitmaps. */ 288*c87b03e5Sespie 289*c87b03e5Sespie #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \ 290*c87b03e5Sespie do { \ 291*c87b03e5Sespie bitmap_element *ptr1_ = (BITMAP1)->first; \ 292*c87b03e5Sespie bitmap_element *ptr2_ = (BITMAP2)->first; \ 293*c87b03e5Sespie unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \ 294*c87b03e5Sespie unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \ 295*c87b03e5Sespie unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \ 296*c87b03e5Sespie \ 297*c87b03e5Sespie /* Find the block the minimum bit is in in the first bitmap. */ \ 298*c87b03e5Sespie while (ptr1_ != 0 && ptr1_->indx < indx_) \ 299*c87b03e5Sespie ptr1_ = ptr1_->next; \ 300*c87b03e5Sespie \ 301*c87b03e5Sespie if (ptr1_ != 0 && ptr1_->indx != indx_) \ 302*c87b03e5Sespie { \ 303*c87b03e5Sespie bit_num_ = 0; \ 304*c87b03e5Sespie word_num_ = 0; \ 305*c87b03e5Sespie } \ 306*c87b03e5Sespie \ 307*c87b03e5Sespie for (; ptr1_ != 0 ; ptr1_ = ptr1_->next) \ 308*c87b03e5Sespie { \ 309*c87b03e5Sespie /* Advance BITMAP2 to the equivalent link */ \ 310*c87b03e5Sespie while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx) \ 311*c87b03e5Sespie ptr2_ = ptr2_->next; \ 312*c87b03e5Sespie \ 313*c87b03e5Sespie if (ptr2_ == 0) \ 314*c87b03e5Sespie { \ 315*c87b03e5Sespie /* If there are no more elements in BITMAP2, exit loop now. */ \ 316*c87b03e5Sespie ptr1_ = (bitmap_element *)0; \ 317*c87b03e5Sespie break; \ 318*c87b03e5Sespie } \ 319*c87b03e5Sespie else if (ptr2_->indx > ptr1_->indx) \ 320*c87b03e5Sespie { \ 321*c87b03e5Sespie bit_num_ = word_num_ = 0; \ 322*c87b03e5Sespie continue; \ 323*c87b03e5Sespie } \ 324*c87b03e5Sespie \ 325*c87b03e5Sespie for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ 326*c87b03e5Sespie { \ 327*c87b03e5Sespie BITMAP_WORD word_ = (ptr1_->bits[word_num_] \ 328*c87b03e5Sespie & ptr2_->bits[word_num_]); \ 329*c87b03e5Sespie if (word_ != 0) \ 330*c87b03e5Sespie { \ 331*c87b03e5Sespie for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \ 332*c87b03e5Sespie { \ 333*c87b03e5Sespie BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \ 334*c87b03e5Sespie \ 335*c87b03e5Sespie if ((word_ & mask_) != 0) \ 336*c87b03e5Sespie { \ 337*c87b03e5Sespie word_ &= ~ mask_; \ 338*c87b03e5Sespie (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \ 339*c87b03e5Sespie + word_num_ * BITMAP_WORD_BITS \ 340*c87b03e5Sespie + bit_num_); \ 341*c87b03e5Sespie \ 342*c87b03e5Sespie CODE; \ 343*c87b03e5Sespie if (word_ == 0) \ 344*c87b03e5Sespie break; \ 345*c87b03e5Sespie } \ 346*c87b03e5Sespie } \ 347*c87b03e5Sespie } \ 348*c87b03e5Sespie \ 349*c87b03e5Sespie bit_num_ = 0; \ 350*c87b03e5Sespie } \ 351*c87b03e5Sespie \ 352*c87b03e5Sespie word_num_ = 0; \ 353*c87b03e5Sespie } \ 354*c87b03e5Sespie } while (0) 355*c87b03e5Sespie 356*c87b03e5Sespie #endif /* GCC_BITMAP_H */ 357