From d5345cf5d4a4886677d36e4501708a1c5126e5c2 Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Mon, 19 Mar 2007 16:31:00 +0000 Subject: [PATCH] - Added raw_bitset.h it contains routines for handling "raw" bitsets, which are plain unsigned arrays, the length of the bitset must be known from elsewhere. "Raw" bitsets can easily be constructed as const data and waste less space because no length information is explicitely saved. [r8715] --- ir/adt/bitset_std.h | 10 ++- ir/adt/raw_bitset.h | 189 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 197 insertions(+), 2 deletions(-) create mode 100644 ir/adt/raw_bitset.h diff --git a/ir/adt/bitset_std.h b/ir/adt/bitset_std.h index 789fa6c63..7075daf3e 100644 --- a/ir/adt/bitset_std.h +++ b/ir/adt/bitset_std.h @@ -1,3 +1,7 @@ +#ifndef _BITSET_STD_H +#define _BITSET_STD_H + +#include "bitfiddle.h" /** Use ordinary ints as unit types. */ typedef unsigned int bitset_unit_t; @@ -84,10 +88,10 @@ typedef unsigned int bitset_unit_t; * @return The Number of leading zeroes. */ #define _bitset_inside_ntz(unit_ptr) _bitset_std_inside_ntz(unit_ptr) -static INLINE bitset_pos_t _bitset_std_inside_ntz(bitset_unit_t *unit_ptr) +static INLINE unsigned _bitset_std_inside_ntz(bitset_unit_t *unit_ptr) { unsigned long data = *unit_ptr; - return 32 - (bitset_pos_t) nlz(~data & (data - 1)); + return 32 - (unsigned) nlz(~data & (data - 1)); } /** @@ -120,3 +124,5 @@ static INLINE bitset_pos_t _bitset_std_inside_ntz(bitset_unit_t *unit_ptr) #define _bitset_inside_binop_andnot(tgt,src) ((*tgt) &= ~(*src)) #define _bitset_inside_binop_or(tgt,src) ((*tgt) |= (*src)) #define _bitset_inside_binop_xor(tgt,src) ((*tgt) ^= (*src)) + +#endif diff --git a/ir/adt/raw_bitset.h b/ir/adt/raw_bitset.h new file mode 100644 index 000000000..d58c2f158 --- /dev/null +++ b/ir/adt/raw_bitset.h @@ -0,0 +1,189 @@ +/** + * @file bitset.h + * @date 15.10.2004 + * @author Matthias Braun + * @brief helper functions for working with raw bitsets + * @summary + * Raw bitsets are constructed from int arrays. Additional information + * like the size of the bitset or the used memory aren't saved for + * efficiency reasons. + * + * These bitsets need less space than bitset_t and their representation + * as int arrays allows having constant bitsets in the ro data segment. + * They should for smaller bitset, whose length is known through other means + * (a typical usage case is a set of cpu registers) + * + * The bitset is built as an array of unsigned integers. It is assumed that + * exactly 32 bits may be put into each element of the array. If there are + * remaining bits, then they should be 0 + */ +#ifndef __FIRM_RAW_BITSET_H +#define __FIRM_RAW_BITSET_H + +#include +#include "bitset.h" +#include "bitset_std.h" +#include "obst.h" + +#define BITS_PER_ELEM 32 +#define BITSET_SIZE_ELEMS(size_bits) ((size_bits)/32 + 1) +#define BITSET_SIZE_BYTES(size_bits) (BITSET_SIZE_ELEMS(size_bits)*4) +#define BITSET_ELEM(bitset,pos) bitset[pos / 32] + +static INLINE unsigned *rbitset_alloca(unsigned size) +{ + unsigned size_bytes = BITSET_SIZE_BYTES(size); + unsigned *res = alloca(size_bytes); + memset(res, 0, size_bytes); + + return res; +} + +static INLINE unsigned *rbitset_obstack_alloc(struct obstack *obst, unsigned size) +{ + unsigned size_bytes = BITSET_SIZE_BYTES(size); + unsigned *res = obstack_alloc(obst, size_bytes); + memset(res, 0, size_bytes); + + return res; +} + +static INLINE +unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst, + const unsigned *old_bitset, + unsigned size) +{ + unsigned size_bytes = BITSET_SIZE_BYTES(size); + unsigned *res = obstack_alloc(obst, size_bytes); + memcpy(res, old_bitset, size_bytes); + + return res; +} + +static INLINE void rbitset_set(unsigned *bitset, unsigned pos) +{ + BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM); +} + +static INLINE void rbitset_clear(unsigned *bitset, unsigned pos) +{ + BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM)); +} + +static INLINE int rbitset_is_set(const unsigned *bitset, unsigned pos) +{ + return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM)); +} + +static INLINE unsigned rbitset_popcnt(const unsigned *bitset, unsigned size) +{ + unsigned pos; + unsigned n = BITSET_SIZE_ELEMS(size); + unsigned res = 0; + const unsigned *elem = bitset; + + for(pos = 0; pos < n; ++pos) { + res += _bitset_inside_pop(elem); + elem++; + } + + return res; +} + +static INLINE unsigned rbitset_next(const unsigned *bitset, unsigned pos, int set) +{ + unsigned p; + unsigned elem_pos = pos / BITS_PER_ELEM; + unsigned bit_pos = pos % BITS_PER_ELEM; + + unsigned elem = bitset[elem_pos]; + + /* + * Mask out the bits smaller than pos in the current unit. + * We are only interested in bits set higher than pos. + */ + unsigned in_elem_mask = (1 << bit_pos) - 1; + + if(!set) + elem = ~elem; + p = _bitset_inside_ntz_value(elem & ~in_elem_mask); + + /* If there is a bit set in the current elem, exit. */ + if(p < BITS_PER_ELEM) { + return elem_pos * BITS_PER_ELEM + p; + } + + /* Else search for set bits in the next units. */ + while(1) { + elem_pos++; + elem = bitset[elem_pos]; + if(!set) + elem = ~elem; + + p = _bitset_inside_ntz_value(elem); + if(p < BITS_PER_ELEM) { + return elem_pos * BITS_PER_ELEM + p; + } + } + + assert(0); + return 0xdeadbeef; +} + +static INLINE void rbitset_and(unsigned *bitset1, const unsigned *bitset2, + unsigned size) +{ + unsigned i = 0; + unsigned n = BITSET_SIZE_ELEMS(size); + + for(i = 0; i < n; ++i) { + bitset1[i] &= bitset2[i]; + } +} + +static INLINE void rbitset_or(unsigned *bitset1, const unsigned *bitset2, + unsigned size) +{ + unsigned i = 0; + unsigned n = BITSET_SIZE_ELEMS(size); + + for(i = 0; i < n; ++i) { + bitset1[i] |= bitset2[i]; + } +} + +static INLINE void rbitset_andnot(unsigned *bitset1, const unsigned *bitset2, + unsigned size) +{ + unsigned i = 0; + unsigned n = BITSET_SIZE_ELEMS(size); + + for(i = 0; i < n; ++i) { + bitset1[i] &= ~bitset2[i]; + } +} + +static INLINE void rbitset_xor(unsigned *bitset1, const unsigned *bitset2, + unsigned size) +{ + unsigned i = 0; + unsigned n = BITSET_SIZE_ELEMS(size); + + for(i = 0; i < n; ++i) { + bitset1[i] ^= bitset2[i]; + } +} + +/** @deprecated */ +static INLINE void rbitset_copy_to_bitset(const unsigned *rbitset, bitset_t *bitset) +{ + // TODO optimize me (or remove me) + unsigned i; + unsigned n = bitset_size(bitset); + for(i = 0; i < n; ++i) { + if(rbitset_is_set(rbitset, i)) + bitset_set(bitset, i); + } +} + +#endif -- 2.20.1