Go to the source code of this file.
Data Structures | |
| struct | simple_bitmap_def |
| struct | sbitmap_iterator |
| class | auto_sbitmap |
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) |
Macro Definition Documentation
◆ EXECUTE_IF_SET_IN_BITMAP
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.
◆ SBITMAP_ELT_BITS
| #define SBITMAP_ELT_BITS (HOST_BITS_PER_WIDEST_FAST_INT * 1u) |
Simple bitmaps. Copyright (C) 1999-2024 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/>.
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
* bit_in_range_p : bitmap_bit_in_range_p
Some operations on 3 sets that occur frequently 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_bit_in_range_p(), bitmap_bit_p(), bitmap_clear_bit(), bitmap_clear_range(), bitmap_last_set_bit(), bitmap_not(), bitmap_ones(), bitmap_set_bit(), bitmap_set_range(), bmp_iter_set(), bmp_iter_set_init(), dump_bitmap(), pre_edge_insert(), and sbitmap_resize().
◆ SBITMAP_ELT_TYPE
| #define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT |
Referenced by bitmap_and(), bitmap_and_or(), bitmap_bit_in_range_p(), bitmap_bit_p(), bitmap_clear_bit(), bitmap_clear_range(), bitmap_copy(), bitmap_equal_p(), bitmap_intersection_of_preds(), bitmap_intersection_of_succs(), bitmap_ior(), bitmap_ior_and_compl(), bitmap_last_set_bit(), bitmap_not(), bitmap_ones(), bitmap_or_and(), bitmap_set_bit(), bitmap_set_range(), bitmap_union_of_preds(), bitmap_union_of_succs(), bitmap_xor(), dump_bitmap(), gcse_or_cprop_is_too_expensive(), pre_edge_insert(), sbitmap_alloc(), sbitmap_realloc(), sbitmap_resize(), sbitmap_size_bytes(), and sbitmap_vector_alloc().
◆ SBITMAP_SET_SIZE
| #define SBITMAP_SET_SIZE | ( | N | ) | (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS) |
Return the set size needed for N elements.
Referenced by gcse_or_cprop_is_too_expensive(), sbitmap_alloc(), sbitmap_realloc(), sbitmap_resize(), and sbitmap_vector_alloc().
◆ SBITMAP_SIZE
Return the number of bits in BITMAP.
Referenced by add_new_name_mapping(), build_insn_chain(), cached_can_duplicate_bb_p(), disqualify_problematic_components(), emit_common_heads_for_components(), emit_common_tails_for_components(), hoist_code(), init_separate_shrink_wrap(), insert_prologue_epilogue_for_components(), is_new_name(), is_old_name(), lra_push_insn_1(), mark_bb_seen(), mem_might_overlap_already_clobbered_arg_p(), and spread_components().
Function Documentation
◆ bitmap_and()
|
extern |
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, ggc_alloc(), i, SBITMAP_ELT_TYPE, and simple_bitmap_def::size.
◆ bitmap_and_compl()
|
extern |
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, ggc_alloc(), i, and simple_bitmap_def::size.
◆ bitmap_and_or()
|
extern |
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, ggc_alloc(), i, SBITMAP_ELT_TYPE, and simple_bitmap_def::size.
Referenced by compute_earliest(), and compute_farthest().
◆ bitmap_bit_in_range_p()
|
extern |
Return TRUE if any bit between START and END inclusive is set within the simple bitmap BMAP. Return FALSE otherwise.
References bitmap_check_index(), simple_bitmap_def::elms, end(), gcc_checking_assert, ggc_alloc(), SBITMAP_ELT_BITS, and SBITMAP_ELT_TYPE.
Referenced by live_bytes_read().
◆ bitmap_bit_p()
|
inline |
Test if bit number bitno in the bitmap is set.
References bitmap_check_index(), ggc_alloc(), i, map, SBITMAP_ELT_BITS, and SBITMAP_ELT_TYPE.
◆ bitmap_check_index()
|
inline |
Verify that access at INDEX in bitmap MAP is valid.
References gcc_checking_assert, and ggc_alloc().
Referenced by bitmap_bit_in_range_p(), bitmap_bit_p(), bitmap_clear_bit(), bitmap_clear_range(), bitmap_set_bit(), and bitmap_set_range().
◆ bitmap_check_sizes()
|
inline |
Verify that bitmaps A and B have same size.
References a, b, and gcc_checking_assert.
Referenced by bitmap_and(), bitmap_and_compl(), bitmap_and_or(), bitmap_equal_p(), bitmap_intersect_p(), bitmap_ior(), bitmap_ior_and_compl(), bitmap_not(), bitmap_or_and(), bitmap_subset_p(), and bitmap_xor().
◆ bitmap_clear()
Zero all elements in a bitmap.
References simple_bitmap_def::elms, ggc_alloc(), and sbitmap_size_bytes().
Referenced by bitmap_vector_clear().
◆ bitmap_clear_bit()
Reset bit number BITNO in the sbitmap MAP. Return true if the bit changed.
References bitmap_check_index(), ggc_alloc(), i, map, SBITMAP_ELT_BITS, and SBITMAP_ELT_TYPE.
◆ bitmap_clear_range()
◆ bitmap_copy()
|
extern |
Copy sbitmap SRC to DST.
References simple_bitmap_def::elms, gcc_checking_assert, ggc_alloc(), SBITMAP_ELT_TYPE, and simple_bitmap_def::size.
◆ bitmap_count_bits()
|
extern |
Count and return the number of bits set in the bitmap BMAP.
References count, simple_bitmap_def::elms, ggc_alloc(), i, sbitmap_popcount(), and simple_bitmap_def::size.
◆ bitmap_empty_p()
|
extern |
Return true if the bitmap is empty.
References simple_bitmap_def::elms, i, and simple_bitmap_def::size.
◆ bitmap_equal_p()
|
extern |
Determine if a == b.
References a, b, bitmap_check_sizes(), ggc_alloc(), and SBITMAP_ELT_TYPE.
◆ bitmap_first_set_bit()
|
extern |
Return number of first bit set in the bitmap, -1 if none.
References EXECUTE_IF_SET_IN_BITMAP, and ggc_alloc().
◆ bitmap_intersect_p()
|
extern |
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(), ggc_alloc(), i, and MIN.
◆ bitmap_ior()
|
extern |
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, ggc_alloc(), i, SBITMAP_ELT_TYPE, and simple_bitmap_def::size.
◆ bitmap_ior_and_compl()
|
extern |
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, ggc_alloc(), i, SBITMAP_ELT_TYPE, and simple_bitmap_def::size.
◆ bitmap_last_set_bit()
|
extern |
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()
|
extern |
Set bitmap DST to the bitwise negation of the bitmap SRC.
References bitmap_check_sizes(), simple_bitmap_def::elms, ggc_alloc(), 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()
Set all elements in a bitmap to ones.
References simple_bitmap_def::elms, ggc_alloc(), 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()
|
extern |
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, ggc_alloc(), i, SBITMAP_ELT_TYPE, and simple_bitmap_def::size.
Referenced by compute_antinout_edge(), and compute_code_hoist_vbeinout().
◆ bitmap_set_bit()
Set bit number BITNO in the sbitmap MAP. Return true if the bit changed.
References bitmap_check_index(), ggc_alloc(), i, map, SBITMAP_ELT_BITS, and SBITMAP_ELT_TYPE.
◆ bitmap_set_range()
◆ bitmap_subset_p()
|
extern |
Return nonzero if A is a subset of B.
References a, ap, b, bitmap_check_sizes(), ggc_alloc(), and i.
Referenced by disqualify_problematic_components().
◆ bitmap_vector_clear()
Zero a vector of N_VECS bitmaps.
References bitmap_clear(), ggc_alloc(), 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()
Set a vector of N_VECS bitmaps to ones.
References bitmap_ones(), ggc_alloc(), and i.
Referenced by compute_antinout_edge(), compute_available(), compute_laterin(), compute_local_properties(), compute_nearerout(), and gcse_after_reload_main().
◆ bitmap_xor()
|
extern |
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, ggc_alloc(), i, SBITMAP_ELT_TYPE, and simple_bitmap_def::size.
◆ bmp_iter_next()
|
inline |
Advance to the next bit.
References i.
◆ bmp_iter_set()
|
inline |
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.
References i, and SBITMAP_ELT_BITS.
◆ bmp_iter_set_init()
|
inline |
Initialize the iterator I with sbitmap BMP and the initial index MIN.
References ggc_alloc(), i, and SBITMAP_ELT_BITS.
◆ debug() [1/2]
|
extern |
◆ debug() [2/2]
|
extern |
◆ debug_bitmap()
|
extern |
References dump_bitmap_file(), and ggc_alloc().
◆ debug_raw() [1/2]
|
extern |
◆ debug_raw() [2/2]
|
extern |
◆ dump_bitmap()
|
extern |
References simple_bitmap_def::elms, ggc_alloc(), 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()
|
extern |
References bitmap_bit_p, ggc_alloc(), i, and simple_bitmap_def::n_bits.
Referenced by compute_code_hoist_vbeinout(), debug(), debug_bitmap(), and remove_unreachable_handlers().
◆ dump_bitmap_vector()
|
extern |
References dump_bitmap(), ggc_alloc(), and i.
Referenced by build_store_vectors(), pre_edge_lcm_avs(), and pre_edge_rev_lcm().
◆ sbitmap_alloc()
Bitmap manipulation routines.
Allocate a simple bitmap of N_ELMS bits.
References ggc_alloc(), simple_bitmap_def::n_bits, SBITMAP_ELT_TYPE, SBITMAP_SET_SIZE, and simple_bitmap_def::size.
Referenced by 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_free()
Referenced by build_insn_chain(), cse_main(), delete_update_ssa(), end_alias_analysis(), expand_call(), fini_dce(), fini_separate_shrink_wrap(), free_var_substitution_info(), init_alias_analysis(), lra(), make_edges(), remove_unreachable_handlers(), remove_unreachable_handlers_no_lp(), should_hoist_expr_to_dom(), tail_duplicate(), tree_dce_done(), try_shrink_wrapping_separate(), undistribute_bitref_for_vector(), vt_find_locations(), and auto_sbitmap::~auto_sbitmap().
◆ sbitmap_realloc()
Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized.
References ggc_alloc(), simple_bitmap_def::n_bits, SBITMAP_ELT_TYPE, SBITMAP_SET_SIZE, sbitmap_size_bytes(), and simple_bitmap_def::size.
◆ sbitmap_resize()
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, ggc_alloc(), 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_vector_alloc()
Allocate a vector of N_VECS bitmaps of N_ELMS bits.
References b, ggc_alloc(), i, offset, 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(), gcse_after_reload_main(), oacc_do_neutering(), pre_edge_insert(), pre_edge_lcm(), pre_edge_lcm_avs(), and pre_edge_rev_lcm().
◆ sbitmap_vector_free()
References free().
Referenced by compute_pre_data(), cov_free(), free_code_hoist_mem(), free_cprop_mem(), free_pre_mem(), free_store_memory(), gcse_after_reload_main(), oacc_do_neutering(), pre_edge_insert(), pre_edge_lcm(), pre_edge_lcm_avs(), and pre_edge_rev_lcm().
