bitmap.h revision 132718
150397Sobrien/* Functions to support general ended bitmaps. 2117395Skan Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003 390075Sobrien 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 1990075SobrienSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA 2090075Sobrien02111-1307, USA. */ 2150397Sobrien 2290075Sobrien#ifndef GCC_BITMAP_H 23117395Skan#define GCC_BITMAP_H 2490075Sobrien 25117395Skan/* Fundamental storage type for bitmap. */ 26117395Skan 27117395Skan/* typedef unsigned HOST_WIDE_INT BITMAP_WORD; */ 28117395Skan/* #define nBITMAP_WORD_BITS HOST_BITS_PER_WIDE_INT */ 29117395Skantypedef unsigned long BITMAP_WORD; 30117395Skan#define nBITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG) 31117395Skan#define BITMAP_WORD_BITS (unsigned) nBITMAP_WORD_BITS 32117395Skan 3350397Sobrien/* Number of words to use for each element in the linked list. */ 3450397Sobrien 3550397Sobrien#ifndef BITMAP_ELEMENT_WORDS 36117395Skan#define BITMAP_ELEMENT_WORDS ((128 + nBITMAP_WORD_BITS - 1) / nBITMAP_WORD_BITS) 3750397Sobrien#endif 3850397Sobrien 3950397Sobrien/* Number of bits in each actual element of a bitmap. We get slightly better 4050397Sobrien code for bit % BITMAP_ELEMENT_ALL_BITS and bit / BITMAP_ELEMENT_ALL_BITS if 4150397Sobrien bits is unsigned, assuming it is a power of 2. */ 4250397Sobrien 4350397Sobrien#define BITMAP_ELEMENT_ALL_BITS \ 44117395Skan ((unsigned) (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)) 4550397Sobrien 4650397Sobrien/* Bitmap set element. We use a linked list to hold only the bits that 4750397Sobrien are set. This allows for use to grow the bitset dynamically without 4850397Sobrien having to realloc and copy a giant bit array. The `prev' field is 4950397Sobrien undefined for an element on the free list. */ 5050397Sobrien 51117395Skantypedef struct bitmap_element_def GTY(()) 5250397Sobrien{ 5390075Sobrien struct bitmap_element_def *next; /* Next element. */ 5490075Sobrien struct bitmap_element_def *prev; /* Previous element. */ 5590075Sobrien unsigned int indx; /* regno/BITMAP_ELEMENT_ALL_BITS. */ 56117395Skan BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */ 5750397Sobrien} bitmap_element; 5850397Sobrien 5950397Sobrien/* Head of bitmap linked list. */ 60117395Skantypedef struct bitmap_head_def GTY(()) { 6190075Sobrien bitmap_element *first; /* First element in linked list. */ 6290075Sobrien bitmap_element *current; /* Last element looked at. */ 6390075Sobrien unsigned int indx; /* Index of last element looked at. */ 64117395Skan int using_obstack; /* Are we using an obstack or ggc for 65117395Skan allocation? */ 66117395Skan} bitmap_head; 67117395Skantypedef struct bitmap_head_def *bitmap; 6890075Sobrien 6950397Sobrien/* Enumeration giving the various operations we support. */ 7050397Sobrienenum bitmap_bits { 7150397Sobrien BITMAP_AND, /* TO = FROM1 & FROM2 */ 7250397Sobrien BITMAP_AND_COMPL, /* TO = FROM1 & ~ FROM2 */ 7390075Sobrien BITMAP_IOR, /* TO = FROM1 | FROM2 */ 7490075Sobrien BITMAP_XOR, /* TO = FROM1 ^ FROM2 */ 7590075Sobrien BITMAP_IOR_COMPL /* TO = FROM1 | ~FROM2 */ 7650397Sobrien}; 7750397Sobrien 7850397Sobrien/* Global data */ 7990075Sobrienextern bitmap_element bitmap_zero_bits; /* Zero bitmap element */ 8050397Sobrien 8150397Sobrien/* Clear a bitmap by freeing up the linked list. */ 82132718Skanextern void bitmap_clear (bitmap); 8350397Sobrien 8490075Sobrien/* Copy a bitmap to another bitmap. */ 85132718Skanextern void bitmap_copy (bitmap, bitmap); 8650397Sobrien 8790075Sobrien/* True if two bitmaps are identical. */ 88132718Skanextern int bitmap_equal_p (bitmap, bitmap); 8990075Sobrien 9050397Sobrien/* Perform an operation on two bitmaps, yielding a third. */ 91132718Skanextern int bitmap_operation (bitmap, bitmap, bitmap, enum bitmap_bits); 9250397Sobrien 9350397Sobrien/* `or' into one bitmap the `and' of a second bitmap witih the complement 9450397Sobrien of a third. */ 95132718Skanextern void bitmap_ior_and_compl (bitmap, bitmap, bitmap); 9650397Sobrien 9750397Sobrien/* Clear a single register in a register set. */ 98132718Skanextern void bitmap_clear_bit (bitmap, int); 9950397Sobrien 10050397Sobrien/* Set a single register in a register set. */ 101132718Skanextern void bitmap_set_bit (bitmap, int); 10250397Sobrien 10350397Sobrien/* Return true if a register is set in a register set. */ 104132718Skanextern int bitmap_bit_p (bitmap, int); 10550397Sobrien 10650397Sobrien/* Debug functions to print a bitmap linked list. */ 107132718Skanextern void debug_bitmap (bitmap); 108132718Skanextern void debug_bitmap_file (FILE *, bitmap); 10950397Sobrien 110132718Skan/* Print a bitmap. */ 111132718Skanextern void bitmap_print (FILE *, bitmap, const char *, const char *); 11250397Sobrien 113117395Skan/* Initialize a bitmap header. If HEAD is NULL, a new header will be 114117395Skan allocated. USING_OBSTACK indicates how elements should be allocated. */ 115132718Skanextern bitmap bitmap_initialize (bitmap head, int using_obstack); 11650397Sobrien 117117395Skan/* Release all memory used by the bitmap obstack. */ 118132718Skanextern void bitmap_release_memory (void); 11950397Sobrien 12090075Sobrien/* A few compatibility/functions macros for compatibility with sbitmaps */ 12190075Sobrien#define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n") 12290075Sobrien#define bitmap_zero(a) bitmap_clear (a) 12390075Sobrien#define bitmap_a_or_b(a,b,c) bitmap_operation (a, b, c, BITMAP_IOR) 12490075Sobrien#define bitmap_a_and_b(a,b,c) bitmap_operation (a, b, c, BITMAP_AND) 125132718Skanextern int bitmap_union_of_diff (bitmap, bitmap, bitmap, bitmap); 126132718Skanextern int bitmap_first_set_bit (bitmap); 127132718Skanextern int bitmap_last_set_bit (bitmap); 12850397Sobrien 12950397Sobrien/* Allocate a bitmap with oballoc. */ 13050397Sobrien#define BITMAP_OBSTACK_ALLOC(OBSTACK) \ 131132718Skan bitmap_initialize (obstack_alloc (OBSTACK, sizeof (bitmap_head)), 1) 13250397Sobrien 133117395Skan/* Allocate a bitmap with ggc_alloc. */ 134117395Skan#define BITMAP_GGC_ALLOC() \ 135117395Skan bitmap_initialize (NULL, 0) 136117395Skan 13790075Sobrien/* Allocate a bitmap with xmalloc. */ 13890075Sobrien#define BITMAP_XMALLOC() \ 139132718Skan bitmap_initialize (xmalloc (sizeof (bitmap_head)), 1) 14050397Sobrien 14150397Sobrien/* Do any cleanup needed on a bitmap when it is no longer used. */ 14290075Sobrien#define BITMAP_FREE(BITMAP) \ 14390075Sobriendo { \ 14490075Sobrien if (BITMAP) \ 14590075Sobrien { \ 14690075Sobrien bitmap_clear (BITMAP); \ 14790075Sobrien (BITMAP) = 0; \ 14890075Sobrien } \ 14950397Sobrien} while (0) 15050397Sobrien 15190075Sobrien/* Do any cleanup needed on an xmalloced bitmap when it is no longer used. */ 15290075Sobrien#define BITMAP_XFREE(BITMAP) \ 15390075Sobriendo { \ 15490075Sobrien if (BITMAP) \ 15590075Sobrien { \ 15690075Sobrien bitmap_clear (BITMAP); \ 15790075Sobrien free (BITMAP); \ 15890075Sobrien (BITMAP) = 0; \ 15990075Sobrien } \ 16090075Sobrien} while (0) 16190075Sobrien 16250397Sobrien/* Do any one-time initializations needed for bitmaps. */ 16350397Sobrien#define BITMAP_INIT_ONCE() 16450397Sobrien 16550397Sobrien/* Loop over all bits in BITMAP, starting with MIN, setting BITNUM to the 16690075Sobrien bit number and executing CODE for all bits that are set. */ 16750397Sobrien 16850397Sobrien#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE) \ 16950397Sobriendo { \ 17050397Sobrien bitmap_element *ptr_ = (BITMAP)->first; \ 17150397Sobrien unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \ 172117395Skan unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \ 173117395Skan unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \ 17450397Sobrien \ 17550397Sobrien \ 17650397Sobrien /* Find the block the minimum bit is in. */ \ 17750397Sobrien while (ptr_ != 0 && ptr_->indx < indx_) \ 17850397Sobrien ptr_ = ptr_->next; \ 17950397Sobrien \ 18050397Sobrien if (ptr_ != 0 && ptr_->indx != indx_) \ 18150397Sobrien { \ 18250397Sobrien bit_num_ = 0; \ 18350397Sobrien word_num_ = 0; \ 18450397Sobrien } \ 18550397Sobrien \ 18650397Sobrien for (; ptr_ != 0; ptr_ = ptr_->next) \ 18750397Sobrien { \ 18850397Sobrien for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ 18950397Sobrien { \ 190117395Skan BITMAP_WORD word_ = ptr_->bits[word_num_]; \ 19150397Sobrien \ 19250397Sobrien if (word_ != 0) \ 19350397Sobrien { \ 194117395Skan for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \ 19550397Sobrien { \ 196117395Skan BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \ 19750397Sobrien \ 19850397Sobrien if ((word_ & mask_) != 0) \ 19950397Sobrien { \ 20050397Sobrien word_ &= ~ mask_; \ 20150397Sobrien (BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS \ 202117395Skan + word_num_ * BITMAP_WORD_BITS \ 20350397Sobrien + bit_num_); \ 20450397Sobrien CODE; \ 20550397Sobrien \ 20650397Sobrien if (word_ == 0) \ 20750397Sobrien break; \ 20850397Sobrien } \ 20950397Sobrien } \ 21050397Sobrien } \ 21150397Sobrien \ 21250397Sobrien bit_num_ = 0; \ 21350397Sobrien } \ 21450397Sobrien \ 21550397Sobrien word_num_ = 0; \ 21650397Sobrien } \ 21750397Sobrien} while (0) 21850397Sobrien 21950397Sobrien/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting 22050397Sobrien BITNUM to the bit number and executing CODE for all bits that are set in 22190075Sobrien the first bitmap and not set in the second. */ 22250397Sobrien 22350397Sobrien#define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \ 22450397Sobriendo { \ 22550397Sobrien bitmap_element *ptr1_ = (BITMAP1)->first; \ 22650397Sobrien bitmap_element *ptr2_ = (BITMAP2)->first; \ 22750397Sobrien unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \ 228117395Skan unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \ 229117395Skan unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \ 23050397Sobrien \ 23150397Sobrien /* Find the block the minimum bit is in in the first bitmap. */ \ 23250397Sobrien while (ptr1_ != 0 && ptr1_->indx < indx_) \ 23350397Sobrien ptr1_ = ptr1_->next; \ 23450397Sobrien \ 23550397Sobrien if (ptr1_ != 0 && ptr1_->indx != indx_) \ 23650397Sobrien { \ 23750397Sobrien bit_num_ = 0; \ 23850397Sobrien word_num_ = 0; \ 23950397Sobrien } \ 24050397Sobrien \ 24150397Sobrien for (; ptr1_ != 0 ; ptr1_ = ptr1_->next) \ 24250397Sobrien { \ 24350397Sobrien /* Advance BITMAP2 to the equivalent link, using an all \ 24450397Sobrien zero element if an equivalent link doesn't exist. */ \ 24550397Sobrien bitmap_element *tmp2_; \ 24650397Sobrien \ 24750397Sobrien while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx) \ 24850397Sobrien ptr2_ = ptr2_->next; \ 24950397Sobrien \ 25050397Sobrien tmp2_ = ((ptr2_ != 0 && ptr2_->indx == ptr1_->indx) \ 251132718Skan ? ptr2_ : &bitmap_zero_bits); \ 25250397Sobrien \ 25350397Sobrien for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ 25450397Sobrien { \ 255117395Skan BITMAP_WORD word_ = (ptr1_->bits[word_num_] \ 256117395Skan & ~ tmp2_->bits[word_num_]); \ 25750397Sobrien if (word_ != 0) \ 25850397Sobrien { \ 259117395Skan for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \ 26050397Sobrien { \ 261117395Skan BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \ 26250397Sobrien \ 26350397Sobrien if ((word_ & mask_) != 0) \ 26450397Sobrien { \ 26550397Sobrien word_ &= ~ mask_; \ 26650397Sobrien (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \ 267117395Skan + word_num_ * BITMAP_WORD_BITS \ 26850397Sobrien + bit_num_); \ 26950397Sobrien \ 27050397Sobrien CODE; \ 27150397Sobrien if (word_ == 0) \ 27250397Sobrien break; \ 27350397Sobrien } \ 27450397Sobrien } \ 27550397Sobrien } \ 27650397Sobrien \ 27750397Sobrien bit_num_ = 0; \ 27850397Sobrien } \ 27950397Sobrien \ 28050397Sobrien word_num_ = 0; \ 28150397Sobrien } \ 28250397Sobrien} while (0) 28350397Sobrien 28450397Sobrien/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting 28550397Sobrien BITNUM to the bit number and executing CODE for all bits that are set in 28690075Sobrien the both bitmaps. */ 28750397Sobrien 28850397Sobrien#define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \ 28950397Sobriendo { \ 29050397Sobrien bitmap_element *ptr1_ = (BITMAP1)->first; \ 29150397Sobrien bitmap_element *ptr2_ = (BITMAP2)->first; \ 29250397Sobrien unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \ 293117395Skan unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \ 294117395Skan unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \ 29550397Sobrien \ 29650397Sobrien /* Find the block the minimum bit is in in the first bitmap. */ \ 29750397Sobrien while (ptr1_ != 0 && ptr1_->indx < indx_) \ 29850397Sobrien ptr1_ = ptr1_->next; \ 29950397Sobrien \ 30050397Sobrien if (ptr1_ != 0 && ptr1_->indx != indx_) \ 30150397Sobrien { \ 30250397Sobrien bit_num_ = 0; \ 30350397Sobrien word_num_ = 0; \ 30450397Sobrien } \ 30550397Sobrien \ 30650397Sobrien for (; ptr1_ != 0 ; ptr1_ = ptr1_->next) \ 30750397Sobrien { \ 308132718Skan /* Advance BITMAP2 to the equivalent link. */ \ 30950397Sobrien while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx) \ 31050397Sobrien ptr2_ = ptr2_->next; \ 31150397Sobrien \ 31250397Sobrien if (ptr2_ == 0) \ 31350397Sobrien { \ 31490075Sobrien /* If there are no more elements in BITMAP2, exit loop now. */ \ 31550397Sobrien ptr1_ = (bitmap_element *)0; \ 31650397Sobrien break; \ 31750397Sobrien } \ 31850397Sobrien else if (ptr2_->indx > ptr1_->indx) \ 31950397Sobrien { \ 32050397Sobrien bit_num_ = word_num_ = 0; \ 32150397Sobrien continue; \ 32250397Sobrien } \ 32350397Sobrien \ 32450397Sobrien for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ 32550397Sobrien { \ 326117395Skan BITMAP_WORD word_ = (ptr1_->bits[word_num_] \ 327117395Skan & ptr2_->bits[word_num_]); \ 32850397Sobrien if (word_ != 0) \ 32950397Sobrien { \ 330117395Skan for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \ 33150397Sobrien { \ 332117395Skan BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \ 33350397Sobrien \ 33450397Sobrien if ((word_ & mask_) != 0) \ 33550397Sobrien { \ 33650397Sobrien word_ &= ~ mask_; \ 33750397Sobrien (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \ 338117395Skan + word_num_ * BITMAP_WORD_BITS \ 33950397Sobrien + bit_num_); \ 34050397Sobrien \ 34150397Sobrien CODE; \ 34250397Sobrien if (word_ == 0) \ 34350397Sobrien break; \ 34450397Sobrien } \ 34550397Sobrien } \ 34650397Sobrien } \ 34750397Sobrien \ 34850397Sobrien bit_num_ = 0; \ 34950397Sobrien } \ 35050397Sobrien \ 35150397Sobrien word_num_ = 0; \ 35250397Sobrien } \ 35350397Sobrien} while (0) 35490075Sobrien 35590075Sobrien#endif /* GCC_BITMAP_H */ 356