sbitmap.h revision 90075
140006Sphk/* Simple bitmaps. 240006Sphk Copyright (C) 1999, 2000, 2002 Free Software Foundation, Inc. 366830Sobrien 466830SobrienThis file is part of GCC. 540006Sphk 666830SobrienGCC is free software; you can redistribute it and/or modify it under 766830Sobrienthe terms of the GNU General Public License as published by the Free 866830SobrienSoftware Foundation; either version 2, or (at your option) any later 966830Sobrienversion. 1066830Sobrien 1166830SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1266830SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1366830SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1466830Sobrienfor more details. 1566830Sobrien 1666830SobrienYou should have received a copy of the GNU General Public License 1766830Sobrienalong with GCC; see the file COPYING. If not, write to the Free 1866830SobrienSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA 1966830Sobrien02111-1307, USA. */ 2066830Sobrien 2166830Sobrien#ifndef GCC_SBITMAP_H 2266830Sobrien#define GCC_SBITMAP_H 2366830Sobrien 2466830Sobrien/* It's not clear yet whether using bitmap.[ch] will be a win. 2566830Sobrien It should be straightforward to convert so for now we keep things simple 2666830Sobrien while more important issues are dealt with. */ 2750472Speter 2866830Sobrien#define SBITMAP_ELT_BITS ((unsigned) HOST_BITS_PER_WIDE_INT) 2940006Sphk#define SBITMAP_ELT_TYPE unsigned HOST_WIDE_INT 3040006Sphk 3166830Sobrientypedef struct simple_bitmap_def 3266830Sobrien{ 3340006Sphk unsigned int n_bits; /* Number of bits. */ 3440006Sphk unsigned int size; /* Size in elements. */ 3540006Sphk unsigned int bytes; /* Size in bytes. */ 3640006Sphk SBITMAP_ELT_TYPE elms[1]; /* The elements. */ 3751231Ssheldonh} *sbitmap; 3851231Ssheldonh 3951231Ssheldonhtypedef SBITMAP_ELT_TYPE *sbitmap_ptr; 4051231Ssheldonh 4151231Ssheldonh/* Return the set size needed for N elements. */ 4251231Ssheldonh#define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS) 4351231Ssheldonh 4451231Ssheldonh/* Set bit number bitno in the bitmap. */ 4551231Ssheldonh#define SET_BIT(BITMAP, BITNO) \ 4651231Ssheldonh ((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS] \ 4751231Ssheldonh |= (SBITMAP_ELT_TYPE) 1 << (BITNO) % SBITMAP_ELT_BITS) 4851231Ssheldonh 4951231Ssheldonh/* Test if bit number bitno in the bitmap is set. */ 5051231Ssheldonh#define TEST_BIT(BITMAP, BITNO) \ 5140006Sphk((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS] >> (BITNO) % SBITMAP_ELT_BITS & 1) 5251231Ssheldonh 5351231Ssheldonh/* Reset bit number bitno in the bitmap. */ 5451231Ssheldonh#define RESET_BIT(BITMAP, BITNO) \ 5540006Sphk ((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS] \ 5640006Sphk &= ~((SBITMAP_ELT_TYPE) 1 << (BITNO) % SBITMAP_ELT_BITS)) 5751231Ssheldonh 5851231Ssheldonh/* Loop over all elements of SBITSET, starting with MIN. */ 5957230Sphk#define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, CODE) \ 6040006Sphkdo { \ 6140006Sphk unsigned int word_num_; \ 6251231Ssheldonh unsigned int bit_num_ = (MIN) % (unsigned int) SBITMAP_ELT_BITS; \ 6351231Ssheldonh unsigned int size_ = (SBITMAP)->size; \ 6451231Ssheldonh SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms; \ 6551231Ssheldonh \ 6640006Sphk for (word_num_ = (MIN) / (unsigned int) SBITMAP_ELT_BITS; \ 6751231Ssheldonh word_num_ < size_; word_num_++, bit_num_ = 0) \ 6851231Ssheldonh { \ 6951231Ssheldonh SBITMAP_ELT_TYPE word_ = ptr_[word_num_]; \ 7051231Ssheldonh \ 7151231Ssheldonh if (word_ != 0) \ 7251231Ssheldonh for (; bit_num_ < SBITMAP_ELT_BITS; bit_num_++) \ 7340006Sphk { \ 7440006Sphk SBITMAP_ELT_TYPE _mask = (SBITMAP_ELT_TYPE) 1 << bit_num_; \ 7551231Ssheldonh \ 7651231Ssheldonh if ((word_ & _mask) != 0) \ 7751231Ssheldonh { \ 7851231Ssheldonh word_ &= ~ _mask; \ 7951231Ssheldonh (N) = word_num_ * SBITMAP_ELT_BITS + bit_num_; \ 8051231Ssheldonh CODE; \ 8151231Ssheldonh if (word_ == 0) \ 8251231Ssheldonh break; \ 8351231Ssheldonh } \ 8451231Ssheldonh } \ 8551231Ssheldonh } \ 8651231Ssheldonh} while (0) 8751231Ssheldonh 8851231Ssheldonh#define sbitmap_free(MAP) free(MAP) 8951231Ssheldonh#define sbitmap_vector_free(VEC) free(VEC) 9051231Ssheldonh 9151231Ssheldonhstruct int_list; 9240006Sphk 9351231Ssheldonhextern void dump_sbitmap PARAMS ((FILE *, sbitmap)); 9451231Ssheldonhextern void dump_sbitmap_vector PARAMS ((FILE *, const char *, 9540006Sphk const char *, sbitmap *, 9640006Sphk int)); 9751231Ssheldonhextern sbitmap sbitmap_alloc PARAMS ((unsigned int)); 9851231Ssheldonhextern sbitmap *sbitmap_vector_alloc PARAMS ((unsigned int, unsigned int)); 9951231Ssheldonhextern void sbitmap_copy PARAMS ((sbitmap, sbitmap)); 10051231Ssheldonhextern int sbitmap_equal PARAMS ((sbitmap, sbitmap)); 10151231Ssheldonhextern void sbitmap_zero PARAMS ((sbitmap)); 10251231Ssheldonhextern void sbitmap_ones PARAMS ((sbitmap)); 10351231Ssheldonhextern void sbitmap_vector_zero PARAMS ((sbitmap *, unsigned int)); 10440006Sphkextern void sbitmap_vector_ones PARAMS ((sbitmap *, unsigned int)); 10551231Ssheldonh 10651231Ssheldonhextern int sbitmap_union_of_diff PARAMS ((sbitmap, sbitmap, sbitmap, 10751231Ssheldonh sbitmap)); 10851231Ssheldonhextern void sbitmap_difference PARAMS ((sbitmap, sbitmap, sbitmap)); 10951231Ssheldonhextern void sbitmap_not PARAMS ((sbitmap, sbitmap)); 11051231Ssheldonhextern int sbitmap_a_or_b_and_c PARAMS ((sbitmap, sbitmap, sbitmap, 11151231Ssheldonh sbitmap)); 11251231Ssheldonhextern int sbitmap_a_and_b_or_c PARAMS ((sbitmap, sbitmap, sbitmap, 11351231Ssheldonh sbitmap)); 11440006Sphkextern int sbitmap_a_and_b PARAMS ((sbitmap, sbitmap, sbitmap)); 11551231Ssheldonhextern int sbitmap_a_or_b PARAMS ((sbitmap, sbitmap, sbitmap)); 11651231Ssheldonhextern int sbitmap_a_xor_b PARAMS ((sbitmap, sbitmap, sbitmap)); 11751231Ssheldonhextern int sbitmap_a_subset_b_p PARAMS ((sbitmap, sbitmap)); 11851231Ssheldonh 11951231Ssheldonhextern int sbitmap_first_set_bit PARAMS ((sbitmap)); 12051231Ssheldonhextern int sbitmap_last_set_bit PARAMS ((sbitmap)); 12151231Ssheldonh 12251231Ssheldonhextern void sbitmap_intersect_of_predsucc PARAMS ((sbitmap, sbitmap *, 12351231Ssheldonh int, struct int_list **)); 12451231Ssheldonh#define sbitmap_intersect_of_predecessors sbitmap_intersect_of_predsucc 12551231Ssheldonh#define sbitmap_intersect_of_successors sbitmap_intersect_of_predsucc 12651231Ssheldonh 12751231Ssheldonhextern void sbitmap_union_of_predsucc PARAMS ((sbitmap, sbitmap *, int, 12851231Ssheldonh struct int_list **)); 12951231Ssheldonh#define sbitmap_union_of_predecessors sbitmap_union_of_predsucc 13040006Sphk#define sbitmap_union_of_successors sbitmap_union_of_predsucc 13140006Sphk 13240006Sphk/* Intersection and Union of preds/succs using the new flow graph 13340006Sphk structure instead of the pred/succ arrays. */ 13440006Sphk 13540006Sphkextern void sbitmap_intersection_of_succs PARAMS ((sbitmap, sbitmap *, int)); 13640006Sphkextern void sbitmap_intersection_of_preds PARAMS ((sbitmap, sbitmap *, int)); 13751231Ssheldonhextern void sbitmap_union_of_succs PARAMS ((sbitmap, sbitmap *, int)); 13840006Sphkextern void sbitmap_union_of_preds PARAMS ((sbitmap, sbitmap *, int)); 13951231Ssheldonh 14051231Ssheldonhextern void debug_sbitmap PARAMS ((sbitmap)); 14140006Sphk#endif /* ! GCC_SBITMAP_H */ 14251231Ssheldonh