Go to the source code of this file.
Data Structures | |
| struct | sparseset_def |
Macros | |
| #define | SPARSESET_ELT_TYPE unsigned int |
| #define | sparseset_free(MAP) |
| #define | EXECUTE_IF_SET_IN_SPARSESET(SPARSESET, ITER) |
Typedefs | |
| typedef struct sparseset_def * | sparseset |
Functions | |
| sparseset | sparseset_alloc (SPARSESET_ELT_TYPE n_elms) |
| void | sparseset_clear_bit (sparseset, SPARSESET_ELT_TYPE) |
| void | sparseset_copy (sparseset, sparseset) |
| void | sparseset_and (sparseset, sparseset, sparseset) |
| void | sparseset_and_compl (sparseset, sparseset, sparseset) |
| void | sparseset_ior (sparseset, sparseset, sparseset) |
| bool | sparseset_equal_p (sparseset, sparseset) |
| void | sparseset_clear (sparseset s) |
| SPARSESET_ELT_TYPE | sparseset_cardinality (sparseset s) |
| SPARSESET_ELT_TYPE | sparseset_size (sparseset s) |
| bool | sparseset_bit_p (sparseset s, SPARSESET_ELT_TYPE e) |
| void | sparseset_insert_bit (sparseset s, SPARSESET_ELT_TYPE e, SPARSESET_ELT_TYPE idx) |
| void | sparseset_set_bit (sparseset s, SPARSESET_ELT_TYPE e) |
| SPARSESET_ELT_TYPE | sparseset_pop (sparseset s) |
| void | sparseset_iter_init (sparseset s) |
| bool | sparseset_iter_p (sparseset s) |
| SPARSESET_ELT_TYPE | sparseset_iter_elm (sparseset s) |
| void | sparseset_iter_next (sparseset s) |
Macro Definition Documentation
◆ EXECUTE_IF_SET_IN_SPARSESET
| #define EXECUTE_IF_SET_IN_SPARSESET | ( | SPARSESET, | |
| ITER ) |
Referenced by assign_by_spills(), build_conflict_bit_table(), dec_register_pressure(), find_hard_regno_for_1(), ira_flattening(), make_hard_regno_dead(), make_hard_regno_dead(), process_bb_lives(), process_bb_node_lives(), process_single_reg_class_operands(), setup_live_pseudos_and_spill_after_risky_transforms(), sparseset_and(), sparseset_and_compl(), sparseset_contains_pseudos_p(), sparseset_equal_p(), sparseset_ior(), and spill_for().
◆ SPARSESET_ELT_TYPE
| #define SPARSESET_ELT_TYPE unsigned int |
SparseSet implementation. Copyright (C) 2007-2025 Free Software Foundation, Inc. Contributed by Peter Bergner <bergner@vnet.ibm.com> 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 the Briggs and Torczon sparse set representation. The sparse set representation was first published in: "An Efficient Representation for Sparse Sets", ACM LOPLAS, Vol. 2, Nos. 1-4, March-December 1993, Pages 59-69. The sparse set representation is suitable for integer sets with a fixed-size universe. Two vectors are used to store the members of the set. If an element I is in the set, then sparse[I] is the index of I in the dense vector, and dense[sparse[I]] == I. The dense vector works like a stack. The size of the stack is the cardinality of the set. The following operations can be performed in O(1) time: * clear : sparseset_clear * cardinality : sparseset_cardinality * set_size : sparseset_size * member_p : sparseset_bit_p * add_member : sparseset_set_bit * remove_member : sparseset_clear_bit * choose_one : sparseset_pop Additionally, the sparse set representation supports enumeration of the members in O(N) time, where n is the number of members in the set. The members of the set are stored cache-friendly in the dense vector. This makes it a competitive choice for iterating over relatively sparse sets requiring operations: * forall : EXECUTE_IF_SET_IN_SPARSESET * set_copy : sparseset_copy * set_intersection : sparseset_and * set_union : sparseset_ior * set_difference : sparseset_and_compl * set_disjuction : (not implemented) * set_compare : sparseset_equal_p NB: It is OK to use remove_member during EXECUTE_IF_SET_IN_SPARSESET. The iterator is updated for it. Based on the efficiency of these operations, this representation of sparse sets will often be superior to alternatives such as simple bitmaps, linked-list bitmaps, array bitmaps, balanced binary trees, hash tables, linked lists, etc., if the set is sufficiently sparse. In the LOPLAS paper the cut-off point where sparse sets became faster than simple bitmaps (see sbitmap.h) when N / U < 64 (where U is the size of the universe of the set). Because the set universe is fixed, the set cannot be resized. For sparse sets with initially unknown size, linked-list bitmaps are a better choice, see bitmap.h. Sparse sets storage requirements are relatively large: O(U) with a larger constant than sbitmaps (if the storage requirement for an sbitmap with universe U is S, then the storage required for a sparse set for the same universe are 2 * sizeof (SPARSESET_ELT_TYPE) * 8 * S). Accessing the sparse vector is not very cache-friendly, but iterating over the members in the set is cache-friendly because only the dense vector is used.
Data Structure used for the SparseSet representation.
Referenced by sparseset_alloc(), sparseset_and(), sparseset_and_compl(), sparseset_bit_p(), sparseset_clear_bit(), sparseset_copy(), sparseset_equal_p(), sparseset_insert_bit(), sparseset_ior(), sparseset_pop(), sparseset_set_bit(), and sparseset_swap().
◆ sparseset_free
| #define sparseset_free | ( | MAP | ) |
Typedef Documentation
◆ sparseset
| typedef struct sparseset_def * sparseset |
Function Documentation
◆ sparseset_alloc()
|
extern |
SparseSet implementation. Copyright (C) 2007-2025 Free Software Foundation, Inc. Contributed by Peter Bergner <bergner@vnet.ibm.com> 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/>.
Allocate and clear a n_elms SparseSet.
References sparseset_clear(), SPARSESET_ELT_TYPE, and VALGRIND_DISCARD.
Referenced by build_conflict_bit_table(), init_live_reload_and_inheritance_pseudos(), init_lives(), ira_create_allocno_live_ranges(), ira_flattening(), and lra_create_live_ranges_1().
◆ sparseset_and()
Operation: D = A & B. Restrictions: none.
References a, b, EXECUTE_IF_SET_IN_SPARSESET, sparseset_bit_p(), sparseset_cardinality(), sparseset_clear(), sparseset_clear_bit(), sparseset_copy(), SPARSESET_ELT_TYPE, and sparseset_set_bit().
◆ sparseset_and_compl()
Operation: D = A & ~B. Restrictions: D != B, unless D == A == B.
References a, b, EXECUTE_IF_SET_IN_SPARSESET, gcc_assert, sparseset_bit_p(), sparseset_cardinality(), sparseset_clear(), sparseset_clear_bit(), SPARSESET_ELT_TYPE, and sparseset_set_bit().
Referenced by process_bb_lives().
◆ sparseset_bit_p()
|
inline |
Return true if e is a member of the set S, otherwise return false.
References sparseset_def::dense, gcc_checking_assert, sparseset_def::members, sparseset_def::sparse, and SPARSESET_ELT_TYPE.
Referenced by check_pseudos_live_through_calls(), find_all_spills_for(), mark_pseudo_dead(), mark_pseudo_live(), mark_pseudo_regno_dead(), mark_pseudo_regno_live(), mark_pseudo_regno_subword_dead(), mark_pseudo_regno_subword_live(), process_bb_lives(), process_bb_node_lives(), pseudo_regno_single_word_and_live_p(), regnos_in_sparseset_p(), sparseset_and(), sparseset_and_compl(), sparseset_clear_bit(), sparseset_equal_p(), sparseset_set_bit(), and update_pseudo_point().
◆ sparseset_cardinality()
|
inline |
Return the number of elements currently in the set.
References sparseset_def::members.
Referenced by process_bb_lives(), sparseset_and(), sparseset_and_compl(), sparseset_equal_p(), and spill_for().
◆ sparseset_clear()
|
inline |
Operation: S = {}
Clear the set of all elements.
References sparseset_def::iterating, and sparseset_def::members.
Referenced by assign_by_spills(), find_hard_regno_for_1(), process_bb_lives(), process_bb_node_lives(), setup_live_pseudos_and_spill_after_risky_transforms(), sparseset_alloc(), sparseset_and(), sparseset_and_compl(), sparseset_copy(), and spill_for().
◆ sparseset_clear_bit()
|
extern |
Operation: S = S - {e}
Delete e from the set S if it is a member of S.
References sparseset_def::dense, sparseset_def::iter, sparseset_def::iter_inc, sparseset_def::iterating, sparseset_def::members, sparseset_def::sparse, sparseset_bit_p(), SPARSESET_ELT_TYPE, sparseset_insert_bit(), and sparseset_swap().
Referenced by build_conflict_bit_table(), check_pseudos_live_through_calls(), clear_sparseset_regnos(), find_hard_regno_for_1(), ira_flattening(), make_object_dead(), mark_pseudo_dead(), process_bb_lives(), sparseset_and(), and sparseset_and_compl().
◆ sparseset_copy()
Operation: D = S Restrictions: none.
References sparseset_def::dense, i, sparseset_def::members, sparseset_clear(), SPARSESET_ELT_TYPE, and sparseset_insert_bit().
Referenced by process_bb_lives(), sparseset_and(), and sparseset_ior().
◆ sparseset_equal_p()
Operation: A == B Restrictions: none.
References a, b, EXECUTE_IF_SET_IN_SPARSESET, sparseset_bit_p(), sparseset_cardinality(), and SPARSESET_ELT_TYPE.
◆ sparseset_insert_bit()
|
inline |
Low level insertion routine not meant for use outside of sparseset.[ch]. Assumes E is valid and not already a member of the set S.
References sparseset_def::dense, sparseset_def::sparse, and SPARSESET_ELT_TYPE.
Referenced by sparseset_clear_bit(), sparseset_copy(), sparseset_set_bit(), and sparseset_swap().
◆ sparseset_ior()
Operation: D = A | B. Restrictions: none.
References a, b, EXECUTE_IF_SET_IN_SPARSESET, sparseset_copy(), SPARSESET_ELT_TYPE, and sparseset_set_bit().
Referenced by process_bb_lives().
◆ sparseset_iter_elm()
|
inline |
References sparseset_def::dense, and sparseset_def::iter.
◆ sparseset_iter_init()
|
inline |
References sparseset_def::iter, sparseset_def::iter_inc, and sparseset_def::iterating.
◆ sparseset_iter_next()
|
inline |
References sparseset_def::iter, and sparseset_def::iter_inc.
◆ sparseset_iter_p()
References sparseset_def::iter, sparseset_def::iterating, and sparseset_def::members.
◆ sparseset_pop()
|
inline |
Return and remove the last member added to the set S.
References sparseset_def::dense, gcc_checking_assert, sparseset_def::members, and SPARSESET_ELT_TYPE.
◆ sparseset_set_bit()
|
inline |
Operation: S = S + {e}
Insert E into the set S, if it isn't already a member.
References sparseset_def::members, sparseset_bit_p(), SPARSESET_ELT_TYPE, and sparseset_insert_bit().
Referenced by build_conflict_bit_table(), find_all_spills_for(), find_hard_regno_for_1(), ira_flattening(), make_hard_regno_dead(), make_hard_regno_live(), make_object_live(), mark_pseudo_dead(), mark_pseudo_live(), process_bb_lives(), process_bb_node_lives(), setup_live_pseudos_and_spill_after_risky_transforms(), sparseset_and(), sparseset_and_compl(), sparseset_ior(), and spill_for().
◆ sparseset_size()
|
inline |
Return the maximum number of elements this set can hold.
References sparseset_def::size.
