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

Data Structures
struct	sparseset_def

Macros
#define	SPARSESET_ELT_TYPE unsigned int

#define	sparseset_free(MAP) 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 )

Value:

  for (sparseset_iter_init (SPARSESET);                                 \
       sparseset_iter_p (SPARSESET)                                     \
       && (((ITER) = sparseset_iter_elm (SPARSESET)) || 1);             \
       sparseset_iter_next (SPARSESET))

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-2024 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_ior(), sparseset_pop(), and sparseset_swap().

◆ sparseset_free

#define sparseset_free ( MAP ) free(MAP)

Referenced by build_conflict_bit_table(), finish_live_reload_and_inheritance_pseudos(), finish_lives(), ira_create_allocno_live_ranges(), ira_flattening(), and lra_create_live_ranges_1().

Typedef Documentation

◆ sparseset

typedef struct sparseset_def * sparseset

Function Documentation

◆ sparseset_alloc()

sparseset sparseset_alloc ( SPARSESET_ELT_TYPE n_elms )

extern

SparseSet implementation.
   Copyright (C) 2007-2024 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 ggc_alloc(), 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()

void sparseset_and	(	sparseset	d,
		sparseset	a,
		sparseset	b )

extern

Operation: D = A & B.
Restrictions: none.

References a, b, EXECUTE_IF_SET_IN_SPARSESET, ggc_alloc(), sparseset_bit_p(), sparseset_cardinality(), sparseset_clear(), sparseset_clear_bit(), sparseset_copy(), SPARSESET_ELT_TYPE, and sparseset_set_bit().

◆ sparseset_and_compl()

void sparseset_and_compl	(	sparseset	d,
		sparseset	a,
		sparseset	b )

extern

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()

bool sparseset_bit_p	(	sparseset	s,
		SPARSESET_ELT_TYPE	e )

inline

Return true if e is a member of the set S, otherwise return false.

References sparseset_def::dense, gcc_checking_assert, ggc_alloc(), 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()

SPARSESET_ELT_TYPE sparseset_cardinality ( sparseset s )

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()

void sparseset_clear ( sparseset s )

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()

void sparseset_clear_bit	(	sparseset	s,
		SPARSESET_ELT_TYPE	e )

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()

void sparseset_copy	(	sparseset	d,
		sparseset	s )

extern

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()

bool sparseset_equal_p	(	sparseset	a,
		sparseset	b )

extern

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()

void sparseset_insert_bit	(	sparseset	s,
		SPARSESET_ELT_TYPE	e,
		SPARSESET_ELT_TYPE	idx )

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, and sparseset_def::sparse.

Referenced by sparseset_clear_bit(), sparseset_copy(), sparseset_set_bit(), and sparseset_swap().

◆ sparseset_ior()

void sparseset_ior	(	sparseset	d,
		sparseset	a,
		sparseset	b )

extern

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()

SPARSESET_ELT_TYPE sparseset_iter_elm ( sparseset s )

inline

References sparseset_def::dense, and sparseset_def::iter.

◆ sparseset_iter_init()

void sparseset_iter_init ( sparseset s )

inline

References sparseset_def::iter, sparseset_def::iter_inc, and sparseset_def::iterating.

◆ sparseset_iter_next()

void sparseset_iter_next ( sparseset s )

inline

References sparseset_def::iter, and sparseset_def::iter_inc.

◆ sparseset_iter_p()

bool sparseset_iter_p ( sparseset s )

inline

References sparseset_def::iter, sparseset_def::iterating, and sparseset_def::members.

◆ sparseset_pop()

SPARSESET_ELT_TYPE sparseset_pop ( sparseset s )

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()

void sparseset_set_bit	(	sparseset	s,
		SPARSESET_ELT_TYPE	e )

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(), 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()

SPARSESET_ELT_TYPE sparseset_size ( sparseset s )

inline

Return the maximum number of elements this set can hold.

References sparseset_def::size.

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ EXECUTE_IF_SET_IN_SPARSESET

◆ SPARSESET_ELT_TYPE

◆ sparseset_free

Typedef Documentation

◆ sparseset

Function Documentation

◆ sparseset_alloc()

◆ sparseset_and()

◆ sparseset_and_compl()

◆ sparseset_bit_p()

◆ sparseset_cardinality()

◆ sparseset_clear()

◆ sparseset_clear_bit()

◆ sparseset_copy()

◆ sparseset_equal_p()

◆ sparseset_insert_bit()

◆ sparseset_ior()

◆ sparseset_iter_elm()

◆ sparseset_iter_init()

◆ sparseset_iter_next()

◆ sparseset_iter_p()

◆ sparseset_pop()

◆ sparseset_set_bit()

◆ sparseset_size()