GCC Middle and Back End API Reference
bitmap.cc File Reference
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "bitmap.h"
#include "selftest.h"
#include "gt-bitmap.h"
Include dependency graph for bitmap.cc:

Macros

#define __alignof__(type)   0
 

Functions

static bitmap_elementbitmap_tree_listify_from (bitmap, bitmap_element *)
 
void bitmap_register (bitmap b MEM_STAT_DECL)
 
static void register_overhead (bitmap b, size_t amount)
 
static void release_overhead (bitmap b, size_t amount, bool remove_from_map)
 
static void bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
 
static bitmap_elementbitmap_element_allocate (bitmap head)
 
void bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
 
static void bitmap_list_link_element (bitmap head, bitmap_element *element)
 
static void bitmap_list_unlink_element (bitmap head, bitmap_element *element, bool to_freelist=true)
 
static bitmap_elementbitmap_list_insert_element_after (bitmap head, bitmap_element *elt, unsigned int indx, bitmap_element *node=NULL)
 
static bitmap_elementbitmap_list_find_element (bitmap head, unsigned int indx)
 
static void bitmap_tree_link_left (bitmap_element *&t, bitmap_element *&l)
 
static void bitmap_tree_link_right (bitmap_element *&t, bitmap_element *&r)
 
static void bitmap_tree_rotate_left (bitmap_element *&t)
 
static void bitmap_tree_rotate_right (bitmap_element *&t)
 
static bitmap_elementbitmap_tree_splay (bitmap head, bitmap_element *t, unsigned int indx)
 
static void bitmap_tree_link_element (bitmap head, bitmap_element *e)
 
static void bitmap_tree_unlink_element (bitmap head, bitmap_element *e)
 
static bitmap_elementbitmap_tree_find_element (bitmap head, unsigned int indx)
 
void bitmap_list_view (bitmap head)
 
void bitmap_tree_view (bitmap head)
 
void bitmap_clear (bitmap head)
 
void bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
 
void bitmap_obstack_release (bitmap_obstack *bit_obstack)
 
bitmap bitmap_alloc (bitmap_obstack *bit_obstack MEM_STAT_DECL)
 
bitmap bitmap_gc_alloc (ALONE_MEM_STAT_DECL)
 
void bitmap_obstack_free (bitmap map)
 
static int bitmap_element_zerop (const bitmap_element *element)
 
void bitmap_copy (bitmap to, const_bitmap from)
 
void bitmap_move (bitmap to, bitmap from)
 
bool bitmap_clear_bit (bitmap head, int bit)
 
bool bitmap_set_bit (bitmap head, int bit)
 
bool bitmap_bit_p (const_bitmap head, int bit)
 
void bitmap_set_aligned_chunk (bitmap head, unsigned int chunk, unsigned int chunk_size, BITMAP_WORD chunk_value)
 
BITMAP_WORD bitmap_get_aligned_chunk (const_bitmap head, unsigned int chunk, unsigned int chunk_size)
 
static unsigned long bitmap_popcount (BITMAP_WORD a)
 
static unsigned long bitmap_count_bits_in_word (const BITMAP_WORD *bits)
 
unsigned long bitmap_count_bits (const_bitmap a)
 
unsigned long bitmap_count_unique_bits (const_bitmap a, const_bitmap b)
 
bool bitmap_single_bit_set_p (const_bitmap a)
 
static unsigned bitmap_first_set_bit_worker (bitmap a, bool clear)
 
unsigned bitmap_first_set_bit (const_bitmap a)
 
unsigned bitmap_clear_first_set_bit (bitmap a)
 
unsigned bitmap_last_set_bit (const_bitmap a)
 
void bitmap_and (bitmap dst, const_bitmap a, const_bitmap b)
 
bool bitmap_and_into (bitmap a, const_bitmap b)
 
static bool bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, const bitmap_element *src_elt, bool changed)
 
bool bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b)
 
bool bitmap_and_compl_into (bitmap a, const_bitmap b)
 
void bitmap_set_range (bitmap head, unsigned int start, unsigned int count)
 
void bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
 
void bitmap_compl_and_into (bitmap a, const_bitmap b)
 
static bool bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, const bitmap_element *a_elt, const bitmap_element *b_elt, bool changed)
 
bool bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b)
 
bool bitmap_ior_into (bitmap a, const_bitmap b)
 
bool bitmap_ior_into_and_free (bitmap a, bitmap *b_)
 
void bitmap_xor (bitmap dst, const_bitmap a, const_bitmap b)
 
void bitmap_xor_into (bitmap a, const_bitmap b)
 
bool bitmap_equal_p (const_bitmap a, const_bitmap b)
 
bool bitmap_intersect_p (const_bitmap a, const_bitmap b)
 
bool bitmap_intersect_compl_p (const_bitmap a, const_bitmap b)
 
bool bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill)
 
bool bitmap_ior_and_compl_into (bitmap a, const_bitmap b, const_bitmap c)
 
bool bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c)
 
hashval_t bitmap_hash (const_bitmap head)
 
static void bitmap_tree_to_vec (vec< bitmap_element * > &elts, const_bitmap head)
 
DEBUG_FUNCTION void debug_bitmap_elt_file (FILE *file, const bitmap_element *ptr)
 
DEBUG_FUNCTION void debug_bitmap_file (FILE *file, const_bitmap head)
 
DEBUG_FUNCTION void debug_bitmap (const_bitmap head)
 
DEBUG_FUNCTION void bitmap_print (FILE *file, const_bitmap head, const char *prefix, const char *suffix)
 
void dump_bitmap_statistics (void)
 
DEBUG_FUNCTION void debug (const bitmap_head &ref)
 
DEBUG_FUNCTION void debug (const bitmap_head *ptr)
 
DEBUG_FUNCTION void debug (const auto_bitmap &ref)
 
DEBUG_FUNCTION void debug (const auto_bitmap *ptr)
 

Variables

mem_alloc_description< bitmap_usagebitmap_mem_desc
 
bitmap_element bitmap_zero_bits
 
bitmap_obstack bitmap_default_obstack
 
static int bitmap_default_obstack_depth
 
static bitmap_elementbitmap_ggc_free
 
static const unsigned char popcount_table []
 

Macro Definition Documentation

◆ __alignof__

#define __alignof__ ( type)    0

Function Documentation

◆ bitmap_alloc()

bitmap bitmap_alloc ( bitmap_obstack *bit_obstack MEM_STAT_DECL)
Create a new bitmap on an obstack.  If BIT_OBSTACK is NULL, create
it on the default bitmap obstack.   

References bitmap_default_obstack, bitmap_default_obstack_depth, bitmap_initialize(), gcc_assert, map, PASS_MEM_STAT, and register_overhead().

◆ bitmap_and()

◆ bitmap_and_compl()

◆ bitmap_and_compl_into()

◆ bitmap_and_into()

◆ bitmap_bit_p()

◆ bitmap_clear()

void bitmap_clear ( bitmap head)
Clear a bitmap by freeing all its elements.   

References bitmap_elt_clear_from(), bitmap_tree_splay(), head::first, gcc_checking_assert, bitmap_element::indx, NULL, and bitmap_element::prev.

Referenced by add_candidate_1(), add_dependence(), add_exit_phis(), add_partitioned_vars_to_ptset(), add_scope_conflicts_1(), analyze_function(), assign_by_spills(), mark_def_dom_walker::before_dom_children(), bitmap_and_compl(), bitmap_and_compl_into(), bitmap_compl_and_into(), bitmap_copy(), bitmap_ior_into_and_free(), bitmap_move(), bitmap_obstack_free(), bitmap_release(), bitmap_set_free(), bitmap_union_of_preds(), bitmap_union_of_succs(), bitmap_xor(), bitmap_xor_into(), break_superblocks(), build_insn_chain(), build_pred_graph(), calculate_equiv_gains(), calculate_gen_cands(), calculate_live_on_exit(), cand_av_con_fun_0(), cand_pav_con_fun_0(), cand_trans_fun(), cleanup_control_flow_pre(), ssa_lazy_cache::clear(), control_dependences::clear_control_dependence_bitmap(), update_list::clear_failures(), clear_modify_mem_tables(), coalesced_allocno_conflict_p(), compute_antic(), compute_antinout_edge(), compute_available(), compute_builtin_object_size(), compute_earliest(), compute_farthest(), compute_live_vars_1(), compute_topo_order(), cse_main(), dce_process_block(), dead_debug_global_init(), dead_debug_local_init(), decompose_multiword_subregs(), destroy_live_vars(), determine_group_iv_cost_cond(), determine_group_iv_costs(), df_chain_create_bb(), df_chain_remove_problem(), df_compact_blocks(), df_get_eh_block_artificial_uses(), df_get_entry_block_def_set(), df_get_exit_block_use_set(), df_get_regular_block_artificial_uses(), df_insn_rescan_all(), df_live_alloc(), df_live_free_bb_info(), df_live_init(), df_live_local_compute(), df_live_reset(), df_live_verify_solution_end(), df_live_verify_transfer_functions(), df_lr_alloc(), df_lr_free_bb_info(), df_lr_init(), df_lr_local_compute(), df_lr_reset(), df_lr_verify_solution_end(), df_lr_verify_transfer_functions(), df_md_alloc(), df_md_bb_local_compute_process_def(), df_md_free_bb_info(), df_md_local_compute(), df_md_reset(), df_mir_alloc(), df_mir_confluence_0(), df_mir_free_bb_info(), df_mir_reset(), df_mir_verify_solution_end(), df_note_bb_compute(), df_note_compute(), df_process_deferred_rescans(), df_rd_alloc(), df_rd_bb_local_compute(), df_rd_dump_defs_set(), df_rd_free_bb_info(), df_rd_init_solution(), df_rd_transfer_function(), df_scan_free_internal(), df_set_blocks(), df_word_lr_alloc(), df_word_lr_free_bb_info(), df_word_lr_init(), df_word_lr_local_compute(), df_word_lr_reset(), df_worklist_dataflow(), do_hoist_insertion(), do_remat(), draw_cfg_nodes_no_loops(), dse_step2(), dse_step3(), dse_step3_scan(), dse_step5(), phi_analyzer::dump(), eh_region_outermost(), eliminate_phi(), eliminate_unnecessary_stmts(), emit_common_heads_for_components(), emit_common_tails_for_components(), expand_call(), ext_dce_finish(), ext_dce_rd_transfer_n(), fast_dce(), fill_always_executed_in(), find_call_stack_args(), find_moveable_pseudos(), find_removable_extensions(), find_replaceable_in_bb(), find_what_var_points_to(), fini_reassoc(), finish_live_solver(), finish_reg_info(), finish_remat_bb_data(), fix_bb_placements(), fold_marked_statements(), free_chain_data(), free_loop_data(), free_loop_data(), get_address_cost(), get_computation_cost(), get_live_on_other_edges(), get_nonnull_args(), hoist_code(), hoist_memory_references(), inherit_in_ebb(), init_alias_analysis(), init_dce(), init_live_subregs(), init_rename_info(), init_separate_shrink_wrap(), init_update_ssa(), initialize_uninitialized_regs(), inline_small_functions(), inverted_rev_post_order_compute(), ira_restore_scratches(), live_track_add_partition(), live_track_clear_base_vars(), live_worklist(), lra(), lra_assign(), lra_coalesce(), lra_eliminate(), lra_inheritance(), lra_live_ranges_finish(), lra_remat(), lra_split_hard_reg_for(), make_edges(), mark_dfs_back_edges(), mark_reachable_handlers(), vect_optimize_slp_pass::materialize(), back_threader::maybe_thread_block(), multiplier_allowed_in_address_p(), oacc_entry_exit_ok(), perform_tree_ssa_dce(), perform_var_substitution(), post_order_compute(), prescan_insns_for_dce(), process_bb_lives(), phi_analyzer::process_phi(), propagate_necessity(), propagate_pseudo_copies(), prune_clobbered_mems(), prune_expressions(), prune_insertions_deletions(), prune_unused_phi_nodes(), ana::reachability< GraphTraits >::reachability(), reachable_at_most_once(), equiv_oracle::register_equiv(), regrename_analyze(), remove_path(), remove_reachable_equiv_notes(), remove_some_program_points_and_update_live_ranges(), remove_some_program_points_and_update_live_ranges(), path_oracle::reset_path(), same_succ_reset(), sarif_artifact::sarif_artifact(), scc_info::scc_info(), setup_live_bytes_from_ref(), setup_try_hard_regno_pseudos(), should_hoist_expr_to_dom(), single_pred_before_succ_order(), spill_for(), spill_pseudos(), split_all_insns(), spread_components(), vect_optimize_slp_pass::start_choosing_layouts(), tail_duplicate(), jump_threader::thread_across_edge(), thread_prologue_and_epilogue_insns(), tree_dce_init(), tree_unroll_loops_completely(), tree_unroll_loops_completely_1(), try_peel_loop(), try_unroll_loop_completely(), undistribute_ops_list(), unroll_loop_runtime_iterations(), unroll_loop_stupid(), update_bad_spill_attribute(), update_dominators_in_loop(), update_live_info(), update_ssa(), update_worklist(), vect_slp_check_for_roots(), vect_transform_slp_perm_load_1(), verify_loop_structure(), verify_ssa(), vt_find_locations(), word_dce_process_block(), and auto_bitmap::~auto_bitmap().

◆ bitmap_clear_bit()

bool bitmap_clear_bit ( bitmap head,
int bit )
Clear a single bit in a bitmap.  Return true if the bit changed.   

References BITMAP_ELEMENT_ALL_BITS, BITMAP_ELEMENT_WORDS, bitmap_element_zerop(), bitmap_list_find_element(), bitmap_list_unlink_element(), bitmap_tree_find_element(), bitmap_tree_unlink_element(), BITMAP_WORD_BITS, bitmap_element::bits, and bitmap_head::indx.

Referenced by add_range_and_copies_from_move_list(), add_scope_conflicts_1(), dom_opt_dom_walker::after_dom_children(), apply_clusters(), assign_by_spills(), assign_temporarily(), bitmap_clear_range(), bitmap_set_subtract_values(), bitmap_value_replace_in_set(), loop_distribution::break_alias_scc_partitions(), build_insn_chain(), build_pred_graph(), calculate_bb_reg_pressure(), calculate_gen_cands(), check_argument_store(), check_for_plus_in_loops_1(), clean(), cleanup_control_flow_pre(), ssa_lazy_cache::clear_range(), collect_object_sizes_for(), color_pass(), compute_antic(), compute_antic_aux(), compute_live_vars_1(), compute_transp(), condense_visit(), create_variable_info_for_1(), cse_extended_basic_block(), cselib_expand_value_rtx_1(), dead_debug_insert_temp(), dead_debug_reset_uses(), df_clear_bb_dirty(), df_insn_delete(), df_insn_info_delete(), df_insn_rescan(), df_insn_rescan_debug_internal(), df_lr_bb_local_compute(), df_md_bb_local_compute_process_def(), df_md_simulate_artificial_defs_at_top(), df_md_simulate_one_insn(), df_mir_simulate_one_insn(), df_note_bb_compute(), df_notes_rescan(), df_simulate_defs(), df_simulate_finalize_backwards(), df_simulate_initialize_backwards(), df_word_lr_mark_ref(), disqualify_candidate(), do_remat(), find_moveable_pseudos(), back_threader::find_paths_to_names(), fix_bb_live_info(), fix_bb_placements(), gimplify_size_expressions(), hoist_memory_references(), insert_store(), insert_updated_phi_nodes_for(), invalidate_insn_data_regno_info(), iv_ca_set_no_cp(), path_oracle::killing_def(), ssa_name_limit_t::leave_phi(), live_track_remove_partition(), loe_visit_block(), lra_create_live_ranges_1(), lra_pop_insn(), make_hard_regno_dead(), mark_elimination(), mark_reachable_blocks(), mark_regno_dead(), mark_regno_death(), prepare_names_to_update(), propagate_freq(), prune_clobbered_mems(), prune_insertions_deletions(), uninit_analysis::prune_phi_opnds(), regstat_bb_compute_calls_crossed(), regstat_bb_compute_ri(), release_defs_bitset(), reload(), remove_unreachable::remove_and_update_globals(), remove_edge_and_dominated_blocks(), remove_from_partition_kill_list(), same_succ_flush_bb(), scan_reads(), scan_rtx_reg(), scan_stores(), gori_map::set_range_invariant(), set_reg_known_equiv_p(), ssa_propagation_engine::simulate_stmt(), sm_seq_valid_bb(), solve_graph(), spread_components(), ssa_conflicts_merge(), ssa_propagation_engine::ssa_propagate(), tree_transform_and_unroll_loop(), try_peel_loop(), try_unroll_loop_completely(), undistribute_bitref_for_vector(), undo_optional_reloads(), unify_nodes(), unroll_loop_constant_iterations(), unroll_loop_runtime_iterations(), update_bb_reg_pressure(), update_ebb_live_info(), update_lives(), update_worklist(), and vt_find_locations().

◆ bitmap_clear_first_set_bit()

unsigned bitmap_clear_first_set_bit ( bitmap a)
Return and clear the bit number of the first set bit in the bitmap.  The
bitmap must be non-empty.   

References a, and bitmap_first_set_bit_worker().

Referenced by cleanup_tree_cfg_noloop(), compute_idf(), df_worklist_dataflow_doublequeue(), do_rpo_vn_1(), rewrite_blocks(), and simple_dce_from_worklist().

◆ bitmap_clear_range()

◆ bitmap_compl_and_into()

◆ bitmap_copy()

void bitmap_copy ( bitmap to,
const_bitmap from )
Copy a bitmap to another bitmap.   

References bitmap_clear(), bitmap_element_allocate(), bitmap_element::bits, gcc_checking_assert, bitmap_element::indx, bitmap_element::next, and bitmap_element::prev.

Referenced by equiv_oracle::add_equiv_to_block(), add_ranges_and_copies(), analyze_all_variable_accesses(), bitmap_and(), bitmap_compl_and_into(), bitmap_intersection_of_preds(), bitmap_intersection_of_succs(), bitmap_ior_and_compl(), bitmap_set_copy(), bitmap_union_of_preds(), bitmap_union_of_succs(), build_insn_chain(), calculate_bb_reg_pressure(), calculate_global_remat_bb_data(), calculate_loop_reg_pressure(), can_move_insns_across(), color_pass(), combine_stack_adjustments_for_block(), compute_builtin_object_size(), compute_earliest(), hybrid_jt_simplifier::compute_exit_dependencies(), path_range_query::compute_exit_dependencies(), compute_farthest(), compute_idf(), compute_laterin(), compute_nearerout(), path_range_query::compute_ranges(), consider_split(), convert_local_omp_clauses(), convert_nonlocal_omp_clauses(), copy_static_var_set(), create_new_chain(), dce_process_block(), dead_debug_local_init(), df_chain_create_bb(), df_compact_blocks(), df_insn_rescan_all(), df_live_verify_solution_start(), df_live_verify_transfer_functions(), df_lr_confluence_0(), df_lr_init(), df_lr_local_compute(), df_lr_verify_solution_start(), df_lr_verify_transfer_functions(), df_md_confluence_0(), df_md_init(), df_mir_confluence_n(), df_mir_verify_solution_start(), df_note_bb_compute(), df_process_deferred_rescans(), df_rd_init_solution(), df_set_blocks(), df_update_entry_block_defs(), df_update_exit_block_uses(), df_word_lr_init(), loop_distribution::distribute_loop(), do_remat(), dse_confluence_0(), dse_confluence_n(), dse_step1(), dse_step3(), dse_transfer_function(), emit_common_heads_for_components(), emit_common_tails_for_components(), ext_dce_rd_transfer_n(), find_moveable_pseudos(), find_removable_extensions(), gen_call_used_regs_seq(), gimplify_size_expressions(), hoist_code(), hoist_memory_references(), init_separate_shrink_wrap(), label_visit(), fwd_jt_path_registry::mark_threaded_blocks(), back_threader::maybe_thread_block(), peephole2_optimize(), process_bb_lives(), propagate(), propagate_pseudo_copies(), prune_unused_phi_nodes(), regrename_analyze(), regstat_bb_compute_calls_crossed(), regstat_bb_compute_ri(), remove_unreachable::remove_and_update_globals(), should_hoist_expr_to_dom(), simulate_backwards_to_point(), sm_seq_valid_bb(), solve_graph(), spill_for(), spread_components(), tm_memopt_compute_antin(), tm_memopt_compute_avin(), tree_unswitch_single_loop(), try_shrink_wrapping(), undo_optional_reloads(), and word_dce_process_block().

◆ bitmap_count_bits()

◆ bitmap_count_bits_in_word()

static unsigned long bitmap_count_bits_in_word ( const BITMAP_WORD * bits)
static
Count and return the number of bits set in the bitmap word BITS.   

References BITMAP_ELEMENT_WORDS, bitmap_popcount(), and count.

Referenced by bitmap_count_bits(), and bitmap_count_unique_bits().

◆ bitmap_count_unique_bits()

unsigned long bitmap_count_unique_bits ( const_bitmap a,
const_bitmap b )
Count the number of unique bits set in A and B and return it.   

References a, b, bitmap_count_bits_in_word(), BITMAP_ELEMENT_WORDS, bitmap_element::bits, count, bitmap_element::indx, and bitmap_element::next.

Referenced by initialize_conflict_count().

◆ bitmap_elem_to_freelist()

static void bitmap_elem_to_freelist ( bitmap head,
bitmap_element * elt )
inlinestatic

◆ bitmap_element_allocate()

static bitmap_element * bitmap_element_allocate ( bitmap head)
inlinestatic

◆ bitmap_element_zerop()

static int bitmap_element_zerop ( const bitmap_element * element)
inlinestatic
Return nonzero if all bits in an element are zero.   

References BITMAP_ELEMENT_WORDS, bitmap_element::bits, and i.

Referenced by bitmap_clear_bit(), and bitmap_first_set_bit_worker().

◆ bitmap_elt_clear_from()

void bitmap_elt_clear_from ( bitmap head,
bitmap_element * elt )

◆ bitmap_elt_copy()

static bool bitmap_elt_copy ( bitmap dst,
bitmap_element * dst_elt,
bitmap_element * dst_prev,
const bitmap_element * src_elt,
bool changed )
inlinestatic
Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
if non-NULL.  CHANGED is true if the destination bitmap had already been
changed; the new value of CHANGED is returned.   

References BITMAP_ELEMENT_WORDS, bitmap_list_insert_element_after(), bitmap_element::bits, changed, and bitmap_element::indx.

Referenced by bitmap_and_compl(), bitmap_elt_ior(), bitmap_ior_and_compl_into(), bitmap_ior_and_into(), and bitmap_ior_into().

◆ bitmap_elt_ior()

static bool bitmap_elt_ior ( bitmap dst,
bitmap_element * dst_elt,
bitmap_element * dst_prev,
const bitmap_element * a_elt,
const bitmap_element * b_elt,
bool changed )
inlinestatic
Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
overwriting DST_ELT if non-NULL.  CHANGED is true if the destination bitmap
had already been changed; the new value of CHANGED is returned.   

References BITMAP_ELEMENT_WORDS, bitmap_elt_copy(), bitmap_list_insert_element_after(), bitmap_element::bits, changed, gcc_assert, gcc_checking_assert, bitmap_element::indx, and r.

Referenced by bitmap_ior(), bitmap_ior_and_compl(), bitmap_ior_and_compl_into(), bitmap_ior_and_into(), bitmap_ior_into(), and bitmap_ior_into_and_free().

◆ bitmap_equal_p()

◆ bitmap_first_set_bit()

◆ bitmap_first_set_bit_worker()

static unsigned bitmap_first_set_bit_worker ( bitmap a,
bool clear )
static

◆ bitmap_gc_alloc()

bitmap bitmap_gc_alloc ( ALONE_MEM_STAT_DECL )
Create a new GCd bitmap.   

References bitmap_initialize(), ggc_alloc(), map, NULL, PASS_MEM_STAT, and register_overhead().

◆ bitmap_get_aligned_chunk()

BITMAP_WORD bitmap_get_aligned_chunk ( const_bitmap head,
unsigned int chunk,
unsigned int chunk_size )
This is the get routine for viewing bitmap as a multi-bit sparse array.
Return a set of CHUNK_SIZE consecutive bits from HEAD, starting at bit
CHUNK * chunk_size.    

References BITMAP_ELEMENT_ALL_BITS, BITMAP_ELEMENT_WORDS, bitmap_list_find_element(), bitmap_tree_find_element(), BITMAP_WORD_BITS, bitmap_element::bits, CHAR_BIT, gcc_checking_assert, bitmap_head::indx, and pow2p_hwi().

Referenced by sbr_sparse_bitmap::bitmap_get_quad().

◆ bitmap_hash()

◆ bitmap_intersect_compl_p()

◆ bitmap_intersect_p()

◆ bitmap_ior()

◆ bitmap_ior_and_compl()

◆ bitmap_ior_and_compl_into()

◆ bitmap_ior_and_into()

◆ bitmap_ior_into()

bool bitmap_ior_into ( bitmap a,
const_bitmap b )
A |= B.  Return true if A changes.   

References a, b, bitmap_elt_copy(), bitmap_elt_ior(), changed, gcc_checking_assert, bitmap_element::indx, bitmap_element::next, and NULL.

Referenced by range_def_chain::add_def_chain_to_bitmap(), add_dependence(), equiv_oracle::add_equiv_to_block(), add_new_name_mapping(), add_partitioned_vars_to_ptset(), add_scope_conflicts(), add_scope_conflicts_1(), analyze_memory_references(), assign_by_spills(), bitmap_ior_and_compl_into(), bitmap_ior_and_into(), gori_map::calculate_gori(), calculate_live_on_exit(), calculate_loop_reg_pressure(), cand_pav_con_fun_n(), coalesce_ssa_name(), compute_antic_aux(), compute_live_vars(), compute_live_vars_1(), compute_partial_antic_aux(), df_live_confluence_n(), df_lr_confluence_n(), df_md_confluence_n(), df_rd_bb_local_compute(), df_rd_confluence_n(), df_rd_transfer_function(), df_scan_blocks(), df_scan_verify(), df_simulate_fixup_sets(), df_word_lr_confluence_n(), ipa_icf::sem_item_optimizer::do_congruence_step(), do_ds_constraint(), do_hoist_insertion(), dse_step2_init(), dse_step3(), dse_step3_exit_block_scan(), phi_analyzer::dump(), ext_dce_rd_transfer_n(), find_split_points(), get_live_on_other_edges(), get_tm_region_blocks(), ipa_tm_scan_irr_function(), label_visit(), lra_assign(), lra_coalesce(), lra_constraints(), lra_eliminate(), lra_inheritance(), lra_split_hard_reg_for(), mark_replaceable(), gori_map::maybe_add_gori(), merge_chains(), merge_clusters(), merge_graph_nodes(), loop_distribution::partition_merge_into(), phi_analyzer::process_phi(), process_replaceable(), propagate_modified_regnos(), propagate_pseudo_copies(), pt_solution_ior_into(), loop_distribution::rdg_build_partitions(), record_important_candidates(), range_def_chain::register_dependency(), equiv_oracle::register_equiv(), path_oracle::register_equiv(), remove_unreachable::remove_and_update_globals(), remove_edge_and_dominated_blocks(), scan_reads(), set_bb_regs(), range_def_chain::set_import(), set_union_with_increment(), sm_seq_valid_bb(), solution_set_expand(), solve_add_graph_edge(), solve_graph(), spill_for(), spill_pseudos(), spill_pseudos(), ssa_conflicts_merge(), store_motion_loop(), tm_memopt_compute_antic(), tm_memopt_compute_available(), tree_unroll_loops_completely_1(), unify_nodes(), union_static_var_sets(), update_live_info(), update_reg_eliminate(), and verify_ssaname_freelists().

◆ bitmap_ior_into_and_free()

bool bitmap_ior_into_and_free ( bitmap a,
bitmap * b_ )
A |= B.  Return true if A changes.  Free B (re-using its storage
for the result).   

References a, b, bitmap_clear(), bitmap_elt_ior(), BITMAP_FREE, bitmap_list_insert_element_after(), bitmap_list_unlink_element(), changed, gcc_assert, gcc_checking_assert, bitmap_element::indx, bitmap_element::next, and NULL.

Referenced by condense_visit().

◆ bitmap_last_set_bit()

unsigned bitmap_last_set_bit ( const_bitmap a)
Return the bit number of the first set bit in the bitmap.  The
bitmap must be non-empty.   

References a, BITMAP_ELEMENT_ALL_BITS, BITMAP_ELEMENT_WORDS, bitmap_popcount(), BITMAP_WORD_BITS, bitmap_element::bits, gcc_assert, gcc_checking_assert, bitmap_element::indx, and bitmap_element::next.

Referenced by compute_trims().

◆ bitmap_list_find_element()

static bitmap_element * bitmap_list_find_element ( bitmap head,
unsigned int indx )
inlinestatic
Return the element for INDX, or NULL if the element doesn't exist.
Update the `current' field even if we can't find an element that  
would hold the bitmap's bit to make eventual allocation
faster.   

References bitmap_mem_desc, head::first, gcc_checking_assert, bitmap_element::indx, bitmap_usage::m_nsearches, bitmap_element::next, id::next, NULL, bitmap_element::prev, and usage().

Referenced by bitmap_bit_p(), bitmap_clear_bit(), bitmap_clear_range(), bitmap_get_aligned_chunk(), bitmap_set_aligned_chunk(), bitmap_set_bit(), and bitmap_set_range().

◆ bitmap_list_insert_element_after()

static bitmap_element * bitmap_list_insert_element_after ( bitmap head,
bitmap_element * elt,
unsigned int indx,
bitmap_element * node = NULL )
static
Insert a new uninitialized element (or NODE if not NULL) into bitmap
HEAD after element ELT.  If ELT is NULL, insert the element at the start.
Return the new element.   

References bitmap_element_allocate(), head::first, gcc_checking_assert, bitmap_element::next, id::next, NULL, and bitmap_element::prev.

Referenced by bitmap_and(), bitmap_and_compl(), bitmap_compl_and_into(), bitmap_elt_copy(), bitmap_elt_ior(), bitmap_ior_into_and_free(), bitmap_set_range(), bitmap_xor(), and bitmap_xor_into().

◆ bitmap_list_link_element()

static void bitmap_list_link_element ( bitmap head,
bitmap_element * element )
inlinestatic
Linked-list view of bitmaps.

In this representation, the bitmap elements form a double-linked list
with elements sorted by increasing index.   
Link the bitmap element into the current bitmap linked list.   

References head::first, gcc_checking_assert, bitmap_element::indx, bitmap_element::next, and bitmap_element::prev.

Referenced by bitmap_set_aligned_chunk(), bitmap_set_bit(), and bitmap_set_range().

◆ bitmap_list_unlink_element()

static void bitmap_list_unlink_element ( bitmap head,
bitmap_element * element,
bool to_freelist = true )
inlinestatic

◆ bitmap_list_view()

void bitmap_list_view ( bitmap head)
Convert bitmap HEAD from splay-tree view to linked-list view.   

References bitmap_tree_listify_from(), bitmap_tree_rotate_right(), head::first, gcc_assert, and bitmap_element::prev.

Referenced by coalesce_ssa_name(), release_defs_bitset(), and update_ssa().

◆ bitmap_move()

void bitmap_move ( bitmap to,
bitmap from )
Move a bitmap to another bitmap.   

References bitmap_clear(), gcc_assert, register_overhead(), and release_overhead().

Referenced by df_rd_transfer_function(), and do_hoist_insertion().

◆ bitmap_obstack_free()

void bitmap_obstack_free ( bitmap map)
Release an obstack allocated bitmap.   

References bitmap_clear(), map, and release_overhead().

◆ bitmap_obstack_initialize()

void bitmap_obstack_initialize ( bitmap_obstack * bit_obstack)
Initialize a bitmap obstack.  If BIT_OBSTACK is NULL, initialize
the default bitmap obstack.   

References __alignof__, bitmap_default_obstack, bitmap_default_obstack_depth, bitmap_obstack::elements, bitmap_obstack::heads, NULL, bitmap_obstack::obstack, obstack_chunk_alloc, obstack_chunk_free, and OBSTACK_CHUNK_SIZE.

Referenced by cgraph_node::add_new_function(), cgraph_node::analyze(), analyze_functions(), block_range_cache::block_range_cache(), symtab_node::check_ifunc_callee_symtab_nodes(), symbol_table::compile(), control_dependences::control_dependences(), df_live_alloc(), df_lr_alloc(), df_md_alloc(), df_mir_alloc(), df_mir_verify_solution_start(), df_rd_alloc(), df_scan_alloc(), df_word_lr_alloc(), dom_ranger::dom_ranger(), dse_step0(), equiv_oracle::equiv_oracle(), execute_tm_memopt(), cgraph_node::expand(), expand_thunk(), find_replaceable_exprs(), gate_tm_init(), infer_range_manager::infer_range_manager(), init_alias_vars(), init_dce(), init_live_reload_and_inheritance_pseudos(), init_lives(), init_pre(), init_ssa_renamer(), init_update_ssa(), init_vars_expansion(), ipa_init(), ipa_passes(), ipa_reference_read_optimization_summary(), ipa_tm_execute(), ira(), lang_dependent_init(), lower_nested_functions(), lto_output(), new_live_track(), new_tree_live_info(), path_oracle::path_oracle(), perform_var_substitution(), phi_analyzer::phi_analyzer(), range_def_chain::range_def_chain(), reorg_loops(), rest_of_handle_df_initialize(), rewrite_into_loop_closed_ssa_1(), run_rtl_passes(), toplev::run_self_tests(), ipa_icf::sem_item_optimizer::sem_item_optimizer(), solve_graph(), ssa_conflicts_new(), ssa_lazy_cache::ssa_lazy_cache(), pair_fusion_bb_info::track_tombstone(), tree_ssa_lim_initialize(), and update_list::update_list().

◆ bitmap_obstack_release()

void bitmap_obstack_release ( bitmap_obstack * bit_obstack)
Release the memory from a bitmap obstack.  If BIT_OBSTACK is NULL,
release the default bitmap obstack.   

References bitmap_default_obstack, bitmap_default_obstack_depth, bitmap_obstack::elements, gcc_assert, bitmap_obstack::heads, NULL, and bitmap_obstack::obstack.

Referenced by cgraph_node::add_new_function(), cgraph_node::analyze(), analyze_functions(), calculate_live_ranges(), symtab_node::check_ifunc_callee_symtab_nodes(), symbol_table::compile(), compute_transaction_bits(), delete_live_track(), delete_points_to_sets(), delete_tree_live_info(), df_live_free(), df_lr_free(), df_md_free(), df_mir_free(), df_mir_verify_solution_end(), df_rd_free(), df_scan_free_internal(), df_word_lr_free(), do_reload(), dse_step7(), execute_tm_memopt(), cgraph_node::expand(), expand_thunk(), finalize(), find_replaceable_exprs(), fini_dce(), fini_pre(), fini_ssa_renamer(), fini_vars_expansion(), finish_live_reload_and_inheritance_pseudos(), finish_lives(), free_var_substitution_info(), gate_tm_init(), ipa_passes(), ipa_reference_cc_finalize(), ipa_tm_execute(), lower_nested_functions(), lto_output(), propagate(), remove_preds_and_fake_succs(), reorg_loops(), rest_of_handle_df_finish(), rewrite_into_loop_closed_ssa_1(), run_rtl_passes(), toplev::run_self_tests(), solve_graph(), ssa_conflicts_delete(), tree_ssa_lim_finalize(), block_range_cache::~block_range_cache(), control_dependences::~control_dependences(), dom_ranger::~dom_ranger(), equiv_oracle::~equiv_oracle(), infer_range_manager::~infer_range_manager(), pair_fusion_bb_info::~pair_fusion_bb_info(), path_oracle::~path_oracle(), phi_analyzer::~phi_analyzer(), range_def_chain::~range_def_chain(), ipa_icf::sem_item_optimizer::~sem_item_optimizer(), ssa_lazy_cache::~ssa_lazy_cache(), and update_list::~update_list().

◆ bitmap_popcount()

static unsigned long bitmap_popcount ( BITMAP_WORD a)
static

◆ bitmap_print()

DEBUG_FUNCTION void bitmap_print ( FILE * file,
const_bitmap head,
const char * prefix,
const char * suffix )

◆ bitmap_register()

void bitmap_register ( bitmap b MEM_STAT_DECL)
Register new bitmap.   

References b, bitmap_mem_desc, BITMAP_ORIGIN, FINAL_PASS_MEM_STAT, and gcc_assert.

◆ bitmap_set_aligned_chunk()

void bitmap_set_aligned_chunk ( bitmap head,
unsigned int chunk,
unsigned int chunk_size,
BITMAP_WORD chunk_value )
Set CHUNK_SIZE bits at a time in bitmap HEAD.
Store CHUNK_VALUE starting at bits CHUNK * chunk_size.
This is the set routine for viewing bitmap as a multi-bit sparse array.   

References BITMAP_ELEMENT_ALL_BITS, bitmap_element_allocate(), BITMAP_ELEMENT_WORDS, bitmap_list_find_element(), bitmap_list_link_element(), bitmap_tree_find_element(), bitmap_tree_link_element(), BITMAP_WORD_BITS, bitmap_element::bits, CHAR_BIT, gcc_checking_assert, bitmap_element::indx, bitmap_head::indx, and pow2p_hwi().

Referenced by sbr_sparse_bitmap::bitmap_set_quad().

◆ bitmap_set_bit()

◆ bitmap_set_range()

◆ bitmap_single_bit_set_p()

bool bitmap_single_bit_set_p ( const_bitmap a)

◆ bitmap_tree_find_element()

static bitmap_element * bitmap_tree_find_element ( bitmap head,
unsigned int indx )
inlinestatic

◆ bitmap_tree_link_element()

static void bitmap_tree_link_element ( bitmap head,
bitmap_element * e )
inlinestatic
Link bitmap element E into the current bitmap splay tree.   

References bitmap_tree_splay(), head::first, gcc_unreachable, bitmap_element::indx, bitmap_element::next, NULL, and bitmap_element::prev.

Referenced by bitmap_set_aligned_chunk(), and bitmap_set_bit().

◆ bitmap_tree_link_left()

static void bitmap_tree_link_left ( bitmap_element *& t,
bitmap_element *& l )
inlinestatic
Splay-tree view of bitmaps.

This is an almost one-to-one the implementatin of the simple top-down
splay tree in Sleator and Tarjan's "Self-adjusting Binary Search Trees".
It is probably not the most efficient form of splay trees, but it should
be good enough to experiment with this idea of bitmaps-as-trees.

For all functions below, the variable or function argument "t" is a node
in the tree, and "e" is a temporary or new node in the tree.  The rest
is sufficiently straigh-forward (and very well explained in the paper)
that comment would only clutter things.   

References bitmap_element::next.

Referenced by bitmap_tree_splay().

◆ bitmap_tree_link_right()

static void bitmap_tree_link_right ( bitmap_element *& t,
bitmap_element *& r )
inlinestatic

References bitmap_element::prev, and r.

Referenced by bitmap_tree_splay().

◆ bitmap_tree_listify_from()

static bitmap_element * bitmap_tree_listify_from ( bitmap head,
bitmap_element * e )
static
Converting bitmap views from linked-list to tree and vice versa.   
Splice element E and all elements with a larger index from
bitmap HEAD, convert the spliced elements to the linked-list
view, and return the head of the list (which should be E again),   

References bitmap_tree_splay(), head::first, FOR_EACH_VEC_ELT, gcc_assert, gcc_checking_assert, bitmap_element::indx, bitmap_element::next, NULL, and bitmap_element::prev.

Referenced by bitmap_elt_clear_from(), and bitmap_list_view().

◆ bitmap_tree_rotate_left()

static void bitmap_tree_rotate_left ( bitmap_element *& t)
inlinestatic

◆ bitmap_tree_rotate_right()

static void bitmap_tree_rotate_right ( bitmap_element *& t)
inlinestatic

◆ bitmap_tree_splay()

◆ bitmap_tree_to_vec()

static void bitmap_tree_to_vec ( vec< bitmap_element * > & elts,
const_bitmap head )
static
Function to obtain a vector of bitmap elements in bit order from
HEAD in tree view.   

References head::first, gcc_checking_assert, bitmap_element::next, NULL, and bitmap_element::prev.

Referenced by bitmap_print(), and debug_bitmap_file().

◆ bitmap_tree_unlink_element()

static void bitmap_tree_unlink_element ( bitmap head,
bitmap_element * e )
static
Unlink bitmap element E from the current bitmap splay tree,
and return it to the freelist.   

References bitmap_elem_to_freelist(), bitmap_tree_splay(), head::first, gcc_checking_assert, bitmap_element::indx, bitmap_element::next, NULL, and bitmap_element::prev.

Referenced by bitmap_clear_bit(), and bitmap_first_set_bit_worker().

◆ bitmap_tree_view()

void bitmap_tree_view ( bitmap head)
Convert bitmap HEAD from linked-list view to splay-tree view.
This is simply a matter of dropping the prev or next pointers
and setting the tree_form flag.  The tree will balance itself
if and when it is used.   

References head::first, gcc_assert, bitmap_element::next, NULL, and bitmap_element::prev.

Referenced by coalesce_ssa_name(), compute_idf(), dom_jt_state::dom_jt_state(), maybe_skip_until(), release_defs_bitset(), sbr_sparse_bitmap::sbr_sparse_bitmap(), sorted_array_from_bitmap_set(), ssa_prop_init(), update_ssa(), and walk_aliased_vdefs_1().

◆ bitmap_xor()

◆ bitmap_xor_into()

◆ debug() [1/4]

DEBUG_FUNCTION void debug ( const auto_bitmap & ref)

References debug.

◆ debug() [2/4]

DEBUG_FUNCTION void debug ( const auto_bitmap * ptr)

References debug.

◆ debug() [3/4]

DEBUG_FUNCTION void debug ( const bitmap_head & ref)

References dump_bitmap().

◆ debug() [4/4]

DEBUG_FUNCTION void debug ( const bitmap_head * ptr)

References debug.

◆ debug_bitmap()

DEBUG_FUNCTION void debug_bitmap ( const_bitmap head)
Function to be called from the debugger to print the contents
of a bitmap.   

References debug_bitmap_file().

◆ debug_bitmap_elt_file()

DEBUG_FUNCTION void debug_bitmap_elt_file ( FILE * file,
const bitmap_element * ptr )
Debugging function to print out the contents of a bitmap element.   

References BITMAP_ELEMENT_ALL_BITS, BITMAP_ELEMENT_WORDS, BITMAP_WORD_BITS, bitmap_element::bits, HOST_PTR_PRINTF, i, bitmap_element::indx, bitmap_element::next, and bitmap_element::prev.

Referenced by debug_bitmap_file().

◆ debug_bitmap_file()

DEBUG_FUNCTION void debug_bitmap_file ( FILE * file,
const_bitmap head )
Debugging function to print out the contents of a bitmap.   

References bitmap_tree_to_vec(), debug_bitmap_elt_file(), head::first, HOST_PTR_PRINTF, i, and bitmap_element::next.

Referenced by debug_bitmap(), and dump_rdg_partitions().

◆ dump_bitmap_statistics()

void dump_bitmap_statistics ( void )
Output per-bitmap memory usage statistics.   

References bitmap_mem_desc, and BITMAP_ORIGIN.

Referenced by dump_memory_report().

◆ register_overhead()

static void register_overhead ( bitmap b,
size_t amount )
static
Account the overhead.   

References b, and bitmap_mem_desc.

Referenced by bitmap_alloc(), bitmap_element_allocate(), bitmap_gc_alloc(), and bitmap_move().

◆ release_overhead()

static void release_overhead ( bitmap b,
size_t amount,
bool remove_from_map )
static
Release the overhead.   

References b, and bitmap_mem_desc.

Referenced by bitmap_elem_to_freelist(), bitmap_elt_clear_from(), bitmap_move(), and bitmap_obstack_free().

Variable Documentation

◆ bitmap_default_obstack

◆ bitmap_default_obstack_depth

int bitmap_default_obstack_depth
static

◆ bitmap_ggc_free

◆ bitmap_mem_desc

Functions to support general ended bitmaps.
   Copyright (C) 1997-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/>.   
Memory allocation statistics purpose instance.   

Referenced by bitmap_list_find_element(), bitmap_register(), bitmap_tree_find_element(), bitmap_tree_splay(), dump_bitmap_statistics(), register_overhead(), and release_overhead().

◆ bitmap_zero_bits

bitmap_element bitmap_zero_bits

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

Referenced by bitmap_popcount().