#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "sbitmap.h"
#include "selftest.h"

Include dependency graph for sbitmap.cc:

Typedefs
typedef SBITMAP_ELT_TYPE *	sbitmap_ptr
typedef const SBITMAP_ELT_TYPE *	const_sbitmap_ptr

Functions
static unsigned int	sbitmap_size_bytes (const_sbitmap map)
sbitmap	sbitmap_alloc (unsigned int n_elms)
sbitmap	sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
sbitmap	sbitmap_realloc (sbitmap src, unsigned int n_elms)
sbitmap *	sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
void	bitmap_copy (sbitmap dst, const_sbitmap src)
bool	bitmap_equal_p (const_sbitmap a, const_sbitmap b)
bool	bitmap_empty_p (const_sbitmap bmap)
void	bitmap_clear_range (sbitmap bmap, unsigned int start, unsigned int count)
void	bitmap_set_range (sbitmap bmap, unsigned int start, unsigned int count)
static bool	bitmap_bit_in_range_p (const_sbitmap bmap, unsigned int start, unsigned int end, bool any_inverted)
bool	bitmap_all_bits_in_range_p (const_sbitmap bmap, unsigned int start, unsigned int end)
bool	bitmap_any_bit_in_range_p (const_sbitmap bmap, unsigned int start, unsigned int end)
static unsigned long	sbitmap_popcount (SBITMAP_ELT_TYPE a)
unsigned int	bitmap_count_bits (const_sbitmap bmap)
void	bitmap_clear (sbitmap bmap)
void	bitmap_ones (sbitmap bmap)
void	bitmap_vector_clear (sbitmap *bmap, unsigned int n_vecs)
void	bitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
bool	bitmap_ior_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
void	bitmap_not (sbitmap dst, const_sbitmap src)
void	bitmap_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b)
bool	bitmap_intersect_p (const_sbitmap a, const_sbitmap b)
bool	bitmap_and (sbitmap dst, const_sbitmap a, const_sbitmap b)
bool	bitmap_xor (sbitmap dst, const_sbitmap a, const_sbitmap b)
bool	bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b)
bool	bitmap_subset_p (const_sbitmap a, const_sbitmap b)
bool	bitmap_or_and (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
bool	bitmap_and_or (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
int	bitmap_first_set_bit (const_sbitmap bmap)
int	bitmap_last_set_bit (const_sbitmap bmap)
void	dump_bitmap (FILE *file, const_sbitmap bmap)
DEBUG_FUNCTION void	debug_raw (simple_bitmap_def &ref)
DEBUG_FUNCTION void	debug_raw (simple_bitmap_def *ptr)
void	dump_bitmap_file (FILE *file, const_sbitmap bmap)
DEBUG_FUNCTION void	debug_bitmap (const_sbitmap bmap)
DEBUG_FUNCTION void	debug (simple_bitmap_def &ref)
DEBUG_FUNCTION void	debug (simple_bitmap_def *ptr)
void	dump_bitmap_vector (FILE file, const char title, const char subtitle, sbitmap bmaps, int n_maps)

Variables
static const unsigned char	popcount_table []

Typedef Documentation

◆ const_sbitmap_ptr

typedef const SBITMAP_ELT_TYPE* const_sbitmap_ptr

◆ sbitmap_ptr

typedef SBITMAP_ELT_TYPE* sbitmap_ptr

Simple bitmaps.
   Copyright (C) 1999-2025 Free Software Foundation, Inc.

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/>.

Function Documentation

◆ bitmap_all_bits_in_range_p()

bool bitmap_all_bits_in_range_p	(	const_sbitmap	bmap,
		unsigned int	start,
		unsigned int	end )

Return TRUE if all bits between START and END inclusive are set within
the simple bitmap BMAP.  Return FALSE otherwise.

References bitmap_bit_in_range_p(), and end().

◆ bitmap_and()

bool bitmap_and	(	sbitmap	dst,
		const_sbitmap	a,
		const_sbitmap	b )

Set DST to be (A and B).
Return nonzero if any change is made.

References a, ap, b, bitmap_check_sizes(), changed, simple_bitmap_def::elms, i, SBITMAP_ELT_TYPE, and simple_bitmap_def::size.

◆ bitmap_and_compl()

void bitmap_and_compl	(	sbitmap	dst,
		const_sbitmap	a,
		const_sbitmap	b )

Set the bits in DST to be the difference between the bits
in A and the bits in B. i.e. dst = a & (~b).

References a, ap, b, bitmap_check_sizes(), simple_bitmap_def::elms, gcc_assert, i, and simple_bitmap_def::size.

◆ bitmap_and_or()

bool bitmap_and_or	(	sbitmap	dst,
		const_sbitmap	a,
		const_sbitmap	b,
		const_sbitmap	c )

Set DST to be (A and (B or C)).
Return nonzero if any change is made.

References a, ap, b, bitmap_check_sizes(), changed, simple_bitmap_def::elms, i, SBITMAP_ELT_TYPE, and simple_bitmap_def::size.

Referenced by compute_earliest(), and compute_farthest().

◆ bitmap_any_bit_in_range_p()

bool bitmap_any_bit_in_range_p	(	const_sbitmap	bmap,
		unsigned int	start,
		unsigned int	end )

Return TRUE if any bit between START and END inclusive is set within
the simple bitmap BMAP.  Return FALSE otherwise.

References bitmap_bit_in_range_p(), and end().

Referenced by live_bytes_read().

◆ bitmap_bit_in_range_p()

bool bitmap_bit_in_range_p	(	const_sbitmap	bmap,
		unsigned int	start,
		unsigned int	end,
		bool	any_inverted )

static

Helper function for bitmap_any_bit_in_range_p and
bitmap_all_bits_in_range_p.  If ANY_INVERTED is true, the function checks
if any bit in the range is unset.

References bitmap_check_index(), simple_bitmap_def::elms, end(), gcc_checking_assert, SBITMAP_ELT_BITS, and SBITMAP_ELT_TYPE.

Referenced by bitmap_all_bits_in_range_p(), and bitmap_any_bit_in_range_p().

◆ bitmap_clear()

void bitmap_clear ( sbitmap bmap )


Zero all elements in a bitmap.

References simple_bitmap_def::elms, and sbitmap_size_bytes().

◆ bitmap_clear_range()

void bitmap_clear_range	(	sbitmap	bmap,
		unsigned int	start,
		unsigned int	count )


Clear COUNT bits from START in BMAP.

References bitmap_check_index(), count, simple_bitmap_def::elms, SBITMAP_ELT_BITS, and SBITMAP_ELT_TYPE.

◆ bitmap_copy()

void bitmap_copy	(	sbitmap	dst,
		const_sbitmap	src )


Copy sbitmap SRC to DST.

References simple_bitmap_def::elms, gcc_checking_assert, SBITMAP_ELT_TYPE, and simple_bitmap_def::size.

◆ bitmap_count_bits()

unsigned int bitmap_count_bits ( const_sbitmap bmap )


Count and return the number of bits set in the bitmap BMAP.

References count, simple_bitmap_def::elms, i, sbitmap_popcount(), and simple_bitmap_def::size.

◆ bitmap_empty_p()

bool bitmap_empty_p ( const_sbitmap bmap )


Return true if the bitmap is empty.

References simple_bitmap_def::elms, i, and simple_bitmap_def::size.

◆ bitmap_equal_p()

bool bitmap_equal_p	(	const_sbitmap	a,
		const_sbitmap	b )


Determine if a == b.

References a, b, bitmap_check_sizes(), and SBITMAP_ELT_TYPE.

◆ bitmap_first_set_bit()

int bitmap_first_set_bit ( const_sbitmap bmap )


Return number of first bit set in the bitmap, -1 if none.

References EXECUTE_IF_SET_IN_BITMAP.

◆ bitmap_intersect_p()

bool bitmap_intersect_p	(	const_sbitmap	a,
		const_sbitmap	b )

Return true if there are any bits set in A are also set in B.
Return false otherwise.

References a, ap, b, bitmap_check_sizes(), i, and MIN.

◆ bitmap_ior()

bool bitmap_ior	(	sbitmap	dst,
		const_sbitmap	a,
		const_sbitmap	b )

Set DST to be (A or B)).
Return nonzero if any change is made.

References a, ap, b, bitmap_check_sizes(), changed, simple_bitmap_def::elms, i, SBITMAP_ELT_TYPE, and simple_bitmap_def::size.

◆ bitmap_ior_and_compl()

bool bitmap_ior_and_compl	(	sbitmap	dst,
		const_sbitmap	a,
		const_sbitmap	b,
		const_sbitmap	c )

Set DST to be A union (B - C).
DST = A | (B & ~C).
Returns true if any change is made.

References a, ap, b, bitmap_check_sizes(), changed, simple_bitmap_def::elms, i, SBITMAP_ELT_TYPE, and simple_bitmap_def::size.

◆ bitmap_last_set_bit()

int bitmap_last_set_bit ( const_sbitmap bmap )


Return number of last bit set in the bitmap, -1 if none.

References simple_bitmap_def::elms, i, SBITMAP_ELT_BITS, SBITMAP_ELT_TYPE, and simple_bitmap_def::size.

◆ bitmap_not()

void bitmap_not	(	sbitmap	dst,
		const_sbitmap	src )


Set bitmap DST to the bitwise negation of the bitmap SRC.

References bitmap_check_sizes(), simple_bitmap_def::elms, i, simple_bitmap_def::n_bits, SBITMAP_ELT_BITS, SBITMAP_ELT_TYPE, and simple_bitmap_def::size.

Referenced by compute_earliest(), compute_farthest(), and compute_pre_data().

◆ bitmap_ones()

void bitmap_ones ( sbitmap bmap )


Set all elements in a bitmap to ones.

References simple_bitmap_def::elms, simple_bitmap_def::n_bits, SBITMAP_ELT_BITS, SBITMAP_ELT_TYPE, sbitmap_size_bytes(), and simple_bitmap_def::size.

Referenced by bitmap_intersection_of_preds(), bitmap_intersection_of_succs(), bitmap_vector_ones(), compute_laterin(), compute_nearerout(), dse_step3(), init_live_subregs(), lra(), reload(), tree_transform_and_unroll_loop(), try_peel_loop(), try_unroll_loop_completely(), undistribute_bitref_for_vector(), unroll_loop_constant_iterations(), and unroll_loop_runtime_iterations().

◆ bitmap_or_and()

bool bitmap_or_and	(	sbitmap	dst,
		const_sbitmap	a,
		const_sbitmap	b,
		const_sbitmap	c )

Set DST to be (A or (B and C)).
Return nonzero if any change is made.

References a, ap, b, bitmap_check_sizes(), changed, simple_bitmap_def::elms, i, SBITMAP_ELT_TYPE, and simple_bitmap_def::size.

Referenced by compute_antinout_edge(), and compute_code_hoist_vbeinout().

◆ bitmap_set_range()

void bitmap_set_range	(	sbitmap	bmap,
		unsigned int	start,
		unsigned int	count )


Set COUNT bits from START in BMAP.

References bitmap_check_index(), count, simple_bitmap_def::elms, SBITMAP_ELT_BITS, and SBITMAP_ELT_TYPE.

◆ bitmap_subset_p()

bool bitmap_subset_p	(	const_sbitmap	a,
		const_sbitmap	b )


Return nonzero if A is a subset of B.

References a, ap, b, bitmap_check_sizes(), and i.

Referenced by disqualify_problematic_components().

◆ bitmap_vector_clear()

void bitmap_vector_clear	(	sbitmap *	bmap,
		unsigned int	n_vecs )


Zero a vector of N_VECS bitmaps.

References bitmap_clear(), and i.

Referenced by build_store_vectors(), compute_code_hoist_vbeinout(), compute_local_properties(), compute_local_properties(), compute_pre_data(), condcov::condcov(), oacc_do_neutering(), pre_edge_insert(), pre_edge_lcm_avs(), and pre_edge_rev_lcm().

◆ bitmap_vector_ones()

void bitmap_vector_ones	(	sbitmap *	bmap,
		unsigned int	n_vecs )


Set a vector of N_VECS bitmaps to ones.

References bitmap_ones(), and i.

Referenced by compute_antinout_edge(), compute_available(), compute_laterin(), compute_local_properties(), compute_nearerout(), and gcse_after_reload_main().

◆ bitmap_xor()

bool bitmap_xor	(	sbitmap	dst,
		const_sbitmap	a,
		const_sbitmap	b )

Set DST to be (A xor B)).
Return nonzero if any change is made.

References a, ap, b, bitmap_check_sizes(), changed, simple_bitmap_def::elms, i, SBITMAP_ELT_TYPE, and simple_bitmap_def::size.

◆ debug() [1/2]

DEBUG_FUNCTION void debug ( simple_bitmap_def & ref )

References dump_bitmap_file().

◆ debug() [2/2]

DEBUG_FUNCTION void debug ( simple_bitmap_def * ptr )

References debug.

◆ debug_bitmap()

DEBUG_FUNCTION void debug_bitmap ( const_sbitmap bmap )

References dump_bitmap_file().

◆ debug_raw() [1/2]

DEBUG_FUNCTION void debug_raw ( simple_bitmap_def & ref )

References dump_bitmap().

Referenced by debug_raw().

◆ debug_raw() [2/2]

DEBUG_FUNCTION void debug_raw ( simple_bitmap_def * ptr )

References debug_raw().

◆ dump_bitmap()

void dump_bitmap	(	FILE *	file,
		const_sbitmap	bmap )

References simple_bitmap_def::elms, i, simple_bitmap_def::n_bits, SBITMAP_ELT_BITS, SBITMAP_ELT_TYPE, and simple_bitmap_def::size.

Referenced by debug_raw(), and dump_bitmap_vector().

◆ dump_bitmap_file()

void dump_bitmap_file	(	FILE *	file,
		const_sbitmap	bmap )

References bitmap_bit_p, i, and simple_bitmap_def::n_bits.

Referenced by compute_code_hoist_vbeinout(), debug(), debug_bitmap(), and remove_unreachable_handlers().

◆ dump_bitmap_vector()

void dump_bitmap_vector	(	FILE *	file,
		const char *	title,
		const char *	subtitle,
		sbitmap *	bmaps,
		int	n_maps )

References dump_bitmap(), and i.

Referenced by build_store_vectors(), pre_edge_lcm_avs(), and pre_edge_rev_lcm().

◆ sbitmap_alloc()

sbitmap sbitmap_alloc ( unsigned int n_elms )


Bitmap manipulation routines.


Allocate a simple bitmap of N_ELMS bits.

References simple_bitmap_def::n_bits, SBITMAP_ELT_TYPE, SBITMAP_SET_SIZE, and simple_bitmap_def::size.

Referenced by auto_sbitmap::auto_sbitmap(), build_pred_graph(), cse_main(), expand_call(), init_alias_analysis(), init_dce(), init_live_subregs(), init_separate_shrink_wrap(), init_update_ssa(), lra(), make_edges(), mark_reachable_handlers(), multiplier_allowed_in_address_p(), perform_tree_ssa_dce(), should_hoist_expr_to_dom(), tail_duplicate(), tree_dce_init(), undistribute_bitref_for_vector(), and vt_find_locations().

◆ sbitmap_popcount()

unsigned long sbitmap_popcount ( SBITMAP_ELT_TYPE a )

static

References a, HOST_BITS_PER_WIDEST_FAST_INT, i, popcount_table, and SBITMAP_ELT_TYPE.

Referenced by bitmap_count_bits().

◆ sbitmap_realloc()

sbitmap sbitmap_realloc	(	sbitmap	src,
		unsigned int	n_elms )


Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized.

References simple_bitmap_def::n_bits, SBITMAP_ELT_TYPE, SBITMAP_SET_SIZE, sbitmap_size_bytes(), and simple_bitmap_def::size.

◆ sbitmap_resize()

sbitmap sbitmap_resize	(	sbitmap	bmap,
		unsigned int	n_elms,
		int	def )

Resize a simple bitmap BMAP to N_ELMS bits.  If increasing the
size of BMAP, clear the new bits to zero if the DEF argument
is zero, and set them to one otherwise.

References simple_bitmap_def::elms, simple_bitmap_def::n_bits, SBITMAP_ELT_BITS, SBITMAP_ELT_TYPE, SBITMAP_SET_SIZE, sbitmap_size_bytes(), and simple_bitmap_def::size.

Referenced by add_new_name_mapping(), lra_push_insn_1(), and mark_bb_seen().

◆ sbitmap_size_bytes()

unsigned int sbitmap_size_bytes ( const_sbitmap map )

inlinestatic


Return the size in bytes of a bitmap MAP.

References map, and SBITMAP_ELT_TYPE.

Referenced by bitmap_clear(), bitmap_ones(), sbitmap_realloc(), and sbitmap_resize().

◆ sbitmap_vector_alloc()

sbitmap * sbitmap_vector_alloc	(	unsigned int	n_vecs,
		unsigned int	n_elms )


Allocate a vector of N_VECS bitmaps of N_ELMS bits.

References b, i, SBITMAP_ELT_TYPE, SBITMAP_SET_SIZE, simple_bitmap_def::size, and y.

Referenced by alloc_code_hoist_mem(), alloc_cprop_mem(), alloc_pre_mem(), build_store_vectors(), condcov::condcov(), gcse_after_reload_main(), oacc_do_neutering(), pre_edge_insert(), pre_edge_lcm(), pre_edge_lcm_avs(), and pre_edge_rev_lcm().

Variable Documentation

◆ popcount_table

const unsigned char popcount_table[]

static

Initial value:

=
{
    0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
    3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
}


Table of number of set bits in a character, indexed by value of char.

Typedefs

Functions

Variables

Typedef Documentation

◆ const_sbitmap_ptr

◆ sbitmap_ptr

Function Documentation

◆ bitmap_all_bits_in_range_p()

◆ bitmap_and()

◆ bitmap_and_compl()

◆ bitmap_and_or()

◆ bitmap_any_bit_in_range_p()

◆ bitmap_bit_in_range_p()

◆ bitmap_clear()

◆ bitmap_clear_range()

◆ bitmap_copy()

◆ bitmap_count_bits()

◆ bitmap_empty_p()

◆ bitmap_equal_p()

◆ bitmap_first_set_bit()

◆ bitmap_intersect_p()

◆ bitmap_ior()

◆ bitmap_ior_and_compl()

◆ bitmap_last_set_bit()

◆ bitmap_not()

◆ bitmap_ones()

◆ bitmap_or_and()

◆ bitmap_set_range()

◆ bitmap_subset_p()

◆ bitmap_vector_clear()

◆ bitmap_vector_ones()

◆ bitmap_xor()

◆ debug() [1/2]

◆ debug() [2/2]

◆ debug_bitmap()

◆ debug_raw() [1/2]

◆ debug_raw() [2/2]

◆ dump_bitmap()

◆ dump_bitmap_file()

◆ dump_bitmap_vector()

◆ sbitmap_alloc()

◆ sbitmap_popcount()

◆ sbitmap_realloc()

◆ sbitmap_resize()

◆ sbitmap_size_bytes()

◆ sbitmap_vector_alloc()

Variable Documentation

◆ popcount_table