This graph shows which files directly or indirectly include this file:

Data Structures
struct	simple_bitmap_def
struct	sbitmap_iterator

Macros
#define	SBITMAP_ELT_BITS (HOST_BITS_PER_WIDEST_FAST_INT * 1u)
#define	SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
#define	SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS)
#define	SBITMAP_SIZE(BITMAP) ((BITMAP)->n_bits)
#define	EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER)

Functions
static SBITMAP_ELT_TYPE	bitmap_bit_p ()
static void	bitmap_set_bit ()
static void	bitmap_clear_bit ()
static void	bmp_iter_set_init (sbitmap_iterator i, const_sbitmap bmp, unsigned int min, unsigned bit_no)
static bool	bmp_iter_set ()
static void	bmp_iter_next ()
void	sbitmap_free (sbitmap map)
void	sbitmap_vector_free (sbitmap *vec)
void	dump_bitmap (FILE *, const_sbitmap)
void	debug_raw (const simple_bitmap_def &ref)
void	debug_raw (const simple_bitmap_def *ptr)
void	dump_bitmap_file (FILE *, const_sbitmap)
void	debug (const simple_bitmap_def &ref)
void	debug (const simple_bitmap_def *ptr)
void	dump_bitmap_vector (FILE , const char , const char , sbitmap , int)
sbitmap	sbitmap_alloc (unsigned int)
sbitmap	sbitmap_alloc_with_popcount (unsigned int)
sbitmap *	sbitmap_vector_alloc (unsigned int, unsigned int)
sbitmap	sbitmap_resize (sbitmap, unsigned int, int)
void	bitmap_copy (sbitmap, const_sbitmap)
int	bitmap_equal_p (const_sbitmap, const_sbitmap)
bool	bitmap_empty_p (const_sbitmap)
void	bitmap_clear (sbitmap)
void	bitmap_ones (sbitmap)
void	bitmap_vector_clear (sbitmap *, unsigned int)
void	bitmap_vector_ones (sbitmap *, unsigned int)
bool	bitmap_ior_and_compl (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap)
void	bitmap_and_compl (sbitmap, const_sbitmap, const_sbitmap)
void	bitmap_not (sbitmap, const_sbitmap)
bool	bitmap_or_and (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap)
bool	bitmap_and_or (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap)
bool	bitmap_intersect_p (const_sbitmap, const_sbitmap)
bool	bitmap_and (sbitmap, const_sbitmap, const_sbitmap)
bool	bitmap_ior (sbitmap, const_sbitmap, const_sbitmap)
bool	bitmap_xor (sbitmap, const_sbitmap, const_sbitmap)
bool	bitmap_subset_p (const_sbitmap, const_sbitmap)
int	bitmap_first_set_bit (const_sbitmap)
int	bitmap_last_set_bit (const_sbitmap)
void	debug_bitmap (const_sbitmap)
sbitmap	sbitmap_realloc (sbitmap, unsigned int)
unsigned long	sbitmap_popcount (const_sbitmap, unsigned long)

Macro Definition Documentation

#define EXECUTE_IF_SET_IN_BITMAP	(	BITMAP,
		MIN,
		BITNUM,
		ITER
	)

Value:

for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \
       bmp_iter_set (&(ITER), &(BITNUM));                       \
       bmp_iter_next (&(ITER), &(BITNUM)))

Loop over all elements of SBITMAP, starting with MIN. In each iteration, N is set to the index of the bit being visited. ITER is an instance of sbitmap_iterator used to iterate the bitmap. See bitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP.

#define SBITMAP_ELT_BITS (HOST_BITS_PER_WIDEST_FAST_INT * 1u)

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/. Implementation of sets using simple bitmap vectors.

This set representation is suitable for non-sparse sets with a known (a priori) universe. The set is represented as a simple array of the host's fastest unsigned integer. For a given member I in the set:

the element for I will be at sbitmap[I / (bits per element)]
the position for I within element is I % (bits per element)

This representation is very space-efficient for large non-sparse sets with random access patterns.

The following operations can be performed in O(1) time:

set_size                 : SBITMAP_SIZE
member_p                 : bitmap_bit_p
add_member               : bitmap_set_bit
remove_member            : bitmap_clear_bit

Most other operations on this set representation are O(U) where U is the size of the set universe:

clear                    : bitmap_clear
choose_one               : bitmap_first_set_bit /
                           bitmap_last_set_bit
forall                   : EXECUTE_IF_SET_IN_BITMAP
set_copy                 : bitmap_copy
set_intersection         : bitmap_and
set_union                : bitmap_ior
set_difference           : bitmap_and_compl
set_disjuction           : (not implemented)
set_compare              : bitmap_equal_p

Some operations on 3 sets that occur frequently in in data flow problems are also implemented:

 A | (B & C)             : bitmap_or_and
 A | (B & ~C)            : bitmap_ior_and_compl
 A & (B | C)             : bitmap_and_or

Most of the set functions have two variants: One that returns non-zero if members were added or removed from the target set, and one that just performs the operation without feedback. The former operations are a bit more expensive but the result can often be used to avoid iterations on other sets.

Allocating a bitmap is done with sbitmap_alloc, and resizing is performed with sbitmap_resize.

The storage requirements for simple bitmap sets is O(U) where U is the size of the set universe (colloquially the number of bits in the bitmap).

This set representation works well for relatively small data flow problems (there are special routines for that, see sbitmap_vector_*). The set operations can be vectorized and there is almost no computating overhead, so that even sparse simple bitmap sets outperform dedicated sparse set representations like linked-list bitmaps. For larger problems, the size overhead of simple bitmap sets gets too high and other set representations have to be used.

Referenced by bitmap_and_or(), bitmap_empty_p(), bitmap_ior_and_compl(), bitmap_set_bit(), and bmp_iter_set_init().

#define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT

Referenced by bitmap_and_or(), bitmap_clear_bit(), bitmap_ior_and_compl(), bitmap_set_bit(), compute_dominance_frontiers_1(), print_ldst_list(), and sbitmap_alloc_with_popcount().

#define SBITMAP_SET_SIZE ( N ) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS)

Return the set size needed for N elements.

Referenced by print_ldst_list(), and sbitmap_alloc_with_popcount().

#define SBITMAP_SIZE ( BITMAP ) ((BITMAP)->n_bits)

Return the number of bits in BITMAP.

Referenced by invalidate_insn_data_regno_info(), and setup_reg_equiv().

Function Documentation

bool bitmap_and	(	sbitmap	,
		const_sbitmap	,
		const_sbitmap
	)

void bitmap_and_compl	(	sbitmap	,
		const_sbitmap	,
		const_sbitmap
	)

bool bitmap_and_or	(	sbitmap	,
		const_sbitmap	,
		const_sbitmap	,
		const_sbitmap
	)

static SBITMAP_ELT_TYPE bitmap_bit_p ( )

inlinestatic

Test if bit number bitno in the bitmap is set.

void bitmap_clear ( sbitmap )

static void bitmap_clear_bit ( )

inlinestatic

Reset bit number BITNO in the sbitmap MAP.

References SBITMAP_ELT_TYPE.

void bitmap_copy	(	sbitmap	,
		const_sbitmap
	)

bool bitmap_empty_p ( const_sbitmap )

int bitmap_equal_p	(	const_sbitmap	,
		const_sbitmap
	)

int bitmap_first_set_bit ( const_sbitmap )

bool bitmap_intersect_p	(	const_sbitmap	,
		const_sbitmap
	)

bool bitmap_ior	(	sbitmap	,
		const_sbitmap	,
		const_sbitmap
	)

bool bitmap_ior_and_compl	(	sbitmap	,
		const_sbitmap	,
		const_sbitmap	,
		const_sbitmap
	)

int bitmap_last_set_bit ( const_sbitmap )

void bitmap_not	(	sbitmap	,
		const_sbitmap
	)

void bitmap_ones ( sbitmap )

bool bitmap_or_and	(	sbitmap	,
		const_sbitmap	,
		const_sbitmap	,
		const_sbitmap
	)

static void bitmap_set_bit ( )

inlinestatic

Set bit number BITNO in the sbitmap MAP.

References simple_bitmap_def::elms, gcc_checking_assert, simple_bitmap_def::popcount, SBITMAP_ELT_BITS, and SBITMAP_ELT_TYPE.

bool bitmap_subset_p	(	const_sbitmap	,
		const_sbitmap
	)

void bitmap_vector_clear	(	sbitmap *	,
		unsigned	int
	)

void bitmap_vector_ones	(	sbitmap *	,
		unsigned	int
	)

bool bitmap_xor	(	sbitmap	,
		const_sbitmap	,
		const_sbitmap
	)

static void bmp_iter_next ( )

inlinestatic

Advance to the next bit.

References simple_bitmap_def::popcount.

static bool bmp_iter_set ( )

inlinestatic

Return true if we have more bits to visit, in which case *N is set to the index of the bit to be visited. Otherwise, return false.

 Skip words that are zeros.

     If we have reached the end, break.

 Skip bits that are zero.

static void bmp_iter_set_init	(	sbitmap_iterator *	i,
		const_sbitmap	bmp,
		unsigned int	min,
		unsigned *	bit_no
	)

inlinestatic

Initialize the iterator I with sbitmap BMP and the initial index MIN.

References sbitmap_iterator::bit_num, sbitmap_iterator::ptr, SBITMAP_ELT_BITS, sbitmap_iterator::size, sbitmap_iterator::word, and sbitmap_iterator::word_num.

void debug ( const simple_bitmap_def & ref )

void debug ( const simple_bitmap_def * ptr )

void debug_bitmap ( const_sbitmap )

void debug_raw ( const simple_bitmap_def & ref )

void debug_raw ( const simple_bitmap_def * ptr )

void dump_bitmap	(	FILE *	,
		const_sbitmap
	)

void dump_bitmap_file	(	FILE *	,
		const_sbitmap
	)

void dump_bitmap_vector	(	FILE *	,
		const char *	,
		const char *	,
		sbitmap *	,
		int
	)

Referenced by compute_insert_delete().

sbitmap sbitmap_alloc ( unsigned int )

sbitmap sbitmap_alloc_with_popcount ( unsigned int )

void sbitmap_free ( sbitmap map )

inline

Referenced by build_and_add_sum(), compute_code_hoist_vbeinout(), insert_store(), memory_must_be_modified_in_insn_p(), ssa_prop_init(), and vect_supported_load_permutation_p().

unsigned long sbitmap_popcount	(	const_sbitmap	,
		unsigned	long
	)

sbitmap sbitmap_realloc	(	sbitmap	,
		unsigned	int
	)

sbitmap sbitmap_resize	(	sbitmap	,
		unsigned	int,
		int
	)

sbitmap* sbitmap_vector_alloc	(	unsigned	int,
		unsigned	int
	)

void sbitmap_vector_free ( sbitmap * vec )

inline

Referenced by compute_insert_delete(), and compute_transp().

Data Structures

Macros

Functions

Macro Definition Documentation

Function Documentation