#include "config.h"#include "system.h"#include "coretypes.h"#include "bitmap.h"#include "selftest.h"#include "gt-bitmap.h"
Macros | |
| #define | __alignof__(type) |
Variables | |
| mem_alloc_description< bitmap_usage > | bitmap_mem_desc |
| bitmap_element | bitmap_zero_bits |
| bitmap_obstack | bitmap_default_obstack |
| static int | bitmap_default_obstack_depth |
| static bitmap_element * | bitmap_ggc_free |
| static const unsigned char | popcount_table [] |
Macro Definition Documentation
◆ __alignof__
| #define __alignof__ | ( | type | ) |
Referenced by bitmap_obstack_initialize().
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()
| void bitmap_and | ( | bitmap | dst, |
| const_bitmap | a, | ||
| const_bitmap | b ) |
DST = A & B.
References a, b, bitmap_copy(), BITMAP_ELEMENT_WORDS, bitmap_elt_clear_from(), bitmap_list_insert_element_after(), bitmap_element::bits, gcc_assert, gcc_checking_assert, bitmap_element::indx, bitmap_element::next, NULL, and r.
Referenced by add_ranges_and_copies(), compute_laterin(), compute_nearerout(), copy_fixed_regs(), df_live_init(), df_live_transfer_function(), df_md_transfer_function(), do_remat(), emit_common_heads_for_components(), emit_common_tails_for_components(), insert_prologue_epilogue_for_components(), move_insn_for_shrink_wrap(), spread_components(), and update_ebb_live_info().
◆ bitmap_and_compl()
| bool bitmap_and_compl | ( | bitmap | dst, |
| const_bitmap | a, | ||
| const_bitmap | b ) |
DST = A & ~B
References a, b, bitmap_clear(), BITMAP_ELEMENT_WORDS, bitmap_elt_clear_from(), bitmap_elt_copy(), bitmap_empty_p(), bitmap_list_insert_element_after(), bitmap_list_unlink_element(), bitmap_element::bits, changed, gcc_assert, gcc_checking_assert, bitmap_element::indx, bitmap_element::next, NULL, and r.
Referenced by bitmap_ior_and_compl(), bitmap_ior_and_compl_into(), bitmap_set_subtract_expressions(), change_loop(), compute_earliest(), compute_farthest(), compute_insert_delete(), compute_rev_insert_delete(), df_rd_confluence_n(), df_rd_transfer_function(), df_set_blocks(), disqualify_problematic_components(), do_hoist_insertion(), emit_common_heads_for_components(), emit_common_tails_for_components(), find_split_points(), hoist_memory_references(), insert_prologue_epilogue_for_components(), live_trans_fun(), propagate_pseudo_copies(), prune_expressions(), prune_unused_phi_nodes(), sm_seq_valid_bb(), solve_graph(), spread_components(), and try_shrink_wrapping_separate().
◆ bitmap_and_compl_into()
| bool bitmap_and_compl_into | ( | bitmap | a, |
| const_bitmap | b ) |
A &= ~B. Returns true if A changes
References a, b, bitmap_clear(), BITMAP_ELEMENT_WORDS, bitmap_empty_p(), bitmap_list_unlink_element(), bitmap_element::bits, changed, gcc_checking_assert, bitmap_element::indx, bitmap_element::next, and r.
Referenced by bitmap_set_subtract_values(), build_insn_chain(), calculate_gen_cands(), can_move_insns_across(), combine_and_move_insns(), decompose_multiword_subregs(), determine_group_iv_costs(), do_remat(), gimple_lower_bitint(), hoist_memory_references(), insert_phi_nodes_for(), prune_unused_phi_nodes(), scan_reads(), spill_pseudos(), store_motion_loop(), update_live_info(), and update_worklist().
◆ bitmap_and_into()
| bool bitmap_and_into | ( | bitmap | a, |
| const_bitmap | b ) |
A &= B. Return true if A changed.
References a, b, BITMAP_ELEMENT_WORDS, bitmap_elt_clear_from(), bitmap_list_unlink_element(), bitmap_element::bits, changed, gcc_checking_assert, bitmap_element::indx, bitmap_element::next, and r.
Referenced by can_move_insns_across(), cand_av_con_fun_n(), compute_antic_aux(), compute_live_loop_exits(), dead_or_predicable(), df_analyze(), df_live_finalize(), df_live_transfer_function(), df_md_transfer_function(), df_mir_confluence_n(), df_rd_dump_defs_set(), df_rd_transfer_function(), loop_distribution::distribute_loop(), do_hoist_insertion(), dse_confluence_n(), find_moveable_pseudos(), live_con_fun_0(), replace_read(), tm_memopt_compute_antin(), and tm_memopt_compute_avin().
◆ bitmap_bit_p()
| bool bitmap_bit_p | ( | const_bitmap | head, |
| int | bit ) |
Return whether a bit is set within a bitmap.
References BITMAP_ELEMENT_ALL_BITS, BITMAP_ELEMENT_WORDS, bitmap_list_find_element(), bitmap_tree_find_element(), BITMAP_WORD_BITS, bitmap_element::bits, and bitmap_head::indx.
◆ 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(), add_store_equivs(), 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(), canonicalize_induction_variables(), 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(), crc_optimization::is_crc_checked(), 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(), sarif_location_relationship::sarif_location_relationship(), 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(), crc_optimization::xor_calculates_crc(), and auto_bitmap::~auto_bitmap().
◆ bitmap_clear_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_local_properties(), 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_hardreg_uses(), 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()
| void bitmap_clear_range | ( | bitmap | head, |
| unsigned int | start, | ||
| unsigned int | count ) |
Clear COUNT bits from START in HEAD.
References bitmap_clear_bit(), BITMAP_ELEMENT_ALL_BITS, BITMAP_ELEMENT_WORDS, bitmap_list_find_element(), bitmap_list_unlink_element(), BITMAP_WORD_BITS, bitmap_element::bits, count, gcc_checking_assert, i, bitmap_element::indx, and bitmap_element::next.
Referenced by clear_live_bytes_for_ref(), df_rd_bb_local_compute_process_def(), df_rd_confluence_n(), df_rd_simulate_artificial_defs_at_top(), df_rd_simulate_one_insn(), df_rd_transfer_function(), df_simulate_one_insn_forwards(), ext_dce_process_sets(), lra_create_live_ranges_1(), mark_effect(), and remove_preds_and_fake_succs().
◆ bitmap_compl_and_into()
| void bitmap_compl_and_into | ( | bitmap | a, |
| const_bitmap | b ) |
◆ 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()
| unsigned long bitmap_count_bits | ( | const_bitmap | a | ) |
Count the number of bits set in the bitmap, and return it.
References a, bitmap_count_bits_in_word(), bitmap_element::bits, count, gcc_checking_assert, and bitmap_element::next.
Referenced by add_exit_phis(), add_to_worklist(), alloc_use_cost_map(), loop_distribution::break_alias_scc_partitions(), path_range_query::compute_exit_dependencies(), compute_partial_antic_aux(), consider_split(), create_new_ivs(), determine_group_iv_cost_cond(), df_rd_dump_defs_set(), dse_step2_init(), initialize_conflict_count(), instrument_decisions(), tree_switch_conversion::bit_test_cluster::is_beneficial(), partition_view_fini(), phi_translate_set(), prune_unused_phi_nodes(), release_defs_bitset(), sorted_array_from_bitmap_set(), and ipa_icf::sem_item_optimizer::traverse_congruence_split().
◆ bitmap_count_bits_in_word()
|
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()
|
inlinestatic |
Bitmap memory management.
Add ELT to the appropriate freelist.
References bitmap_ggc_free, bitmap_obstack::elements, bitmap_element::indx, bitmap_element::next, NULL, bitmap_element::prev, and release_overhead().
Referenced by bitmap_list_unlink_element(), and bitmap_tree_unlink_element().
◆ bitmap_element_allocate()
|
inlinestatic |
Allocate a bitmap element. The bits are cleared, but nothing else is.
References bitmap_ggc_free, bitmap_element::bits, bitmap_obstack::elements, ggc_alloc(), bitmap_element::next, bitmap_obstack::obstack, bitmap_element::prev, and register_overhead().
Referenced by bitmap_copy(), bitmap_list_insert_element_after(), bitmap_set_aligned_chunk(), bitmap_set_bit(), and bitmap_set_range().
◆ bitmap_element_zerop()
|
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 ) |
Remove ELT and all following elements from bitmap HEAD. Put the released elements in the freelist for HEAD.
References bitmap_ggc_free, bitmap_tree_listify_from(), bitmap_obstack::elements, head::first, bitmap_element::indx, bitmap_element::next, NULL, bitmap_element::prev, and release_overhead().
Referenced by bitmap_and(), bitmap_and_compl(), bitmap_and_into(), bitmap_clear(), bitmap_ior(), bitmap_ior_and_compl(), and bitmap_xor().
◆ bitmap_elt_copy()
|
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()
|
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()
| bool bitmap_equal_p | ( | const_bitmap | a, |
| const_bitmap | b ) |
Return true if two bitmaps are identical. We do not bother with a check for pointer equality, as that never occurs in practice.
References a, b, BITMAP_ELEMENT_WORDS, bitmap_element::bits, gcc_checking_assert, bitmap_element::indx, and bitmap_element::next.
Referenced by bitmap_ior_and_compl(), bitmap_set_equal(), dce_process_block(), df_entry_block_bitmap_verify(), df_exit_block_bitmap_verify(), df_live_verify_solution_end(), df_live_verify_transfer_functions(), df_lr_verify_solution_end(), df_lr_verify_transfer_functions(), df_mir_verify_solution_end(), df_rd_transfer_function(), df_scan_verify(), df_update_entry_block_defs(), df_update_exit_block_uses(), dump_varinfo(), equiv_class_hasher::equal(), same_succ::equal(), shared_bitmap_hasher::equal(), ext_dce_rd_transfer_n(), propagate(), dom_oracle::query(), equiv_oracle::query(), path_oracle::query(), path_oracle::register_equiv(), spread_components(), union_static_var_sets(), and word_dce_process_block().
◆ bitmap_first_set_bit()
| unsigned bitmap_first_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, and bitmap_first_set_bit_worker().
Referenced by compute_trims(), same_succ::equal(), kill_expr(), nearest_common_dominator_for_set(), nearest_common_dominator_of_uses(), pt_solution_singleton_or_null_p(), same_succ_hash(), scc_visit(), set_livein_block(), ssa_propagation_engine::ssa_propagate(), and undistribute_ops_list().
◆ bitmap_first_set_bit_worker()
Return the bit number of the first set bit in the bitmap. The bitmap must be non-empty. When CLEAR is true it clears the bit.
References a, BITMAP_ELEMENT_ALL_BITS, BITMAP_ELEMENT_WORDS, bitmap_element_zerop(), bitmap_list_unlink_element(), bitmap_tree_unlink_element(), BITMAP_WORD_BITS, bitmap_element::bits, gcc_assert, gcc_checking_assert, gcc_unreachable, bitmap_element::indx, and bitmap_element::prev.
Referenced by bitmap_clear_first_set_bit(), and bitmap_first_set_bit().
◆ 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()
| hashval_t bitmap_hash | ( | const_bitmap | head | ) |
Compute hash of bitmap (for purposes of hashing).
References BITMAP_ELEMENT_WORDS, bitmap_element::bits, head::first, gcc_checking_assert, bitmap_element::indx, and bitmap_element::next.
Referenced by equiv_class_lookup_or_add(), same_succ_hash(), shared_bitmap_add(), and shared_bitmap_lookup().
◆ bitmap_intersect_compl_p()
| bool bitmap_intersect_compl_p | ( | const_bitmap | a, |
| const_bitmap | b ) |
Return true if A AND NOT B is not empty.
References a, b, BITMAP_ELEMENT_WORDS, bitmap_element::bits, gcc_checking_assert, bitmap_element::indx, bitmap_element::next, and NULL.
Referenced by assign_spill_hard_regs(), df_live_verify_transfer_functions(), df_lr_verify_transfer_functions(), and discover_loops().
◆ bitmap_intersect_p()
| bool bitmap_intersect_p | ( | const_bitmap | a, |
| const_bitmap | b ) |
Return true if A AND B is not empty.
References a, b, BITMAP_ELEMENT_WORDS, bitmap_element::bits, gcc_checking_assert, bitmap_element::indx, and bitmap_element::next.
Referenced by bb_valid_for_noce_process_p(), can_move_insns_across(), dead_or_predicable(), range_def_chain::def_chain_in_bitmap_p(), discover_loops(), doloop_optimize(), relation_chain_head::find_relation(), pt_solution_set(), pt_solutions_intersect_1(), dom_oracle::query(), path_oracle::query(), dom_oracle::register_transitives(), verify_ssaname_freelists(), and visit_loadstore().
◆ bitmap_ior()
| bool bitmap_ior | ( | bitmap | dst, |
| const_bitmap | a, | ||
| const_bitmap | b ) |
DST = A | B. Return true if DST changes.
References a, b, bitmap_elt_clear_from(), bitmap_elt_ior(), changed, gcc_assert, gcc_checking_assert, bitmap_element::indx, bitmap_element::next, and NULL.
Referenced by assign_by_spills(), bitmap_ior_and_compl(), compute_code_hoist_vbeinout(), compute_pre_data(), emit_common_heads_for_components(), emit_common_tails_for_components(), label_visit(), lra_split_hard_reg_for(), oacc_do_neutering(), prune_unused_phi_nodes(), remove_some_program_points_and_update_live_ranges(), remove_some_program_points_and_update_live_ranges(), and spread_components().
◆ bitmap_ior_and_compl()
| bool bitmap_ior_and_compl | ( | bitmap | dst, |
| const_bitmap | a, | ||
| const_bitmap | b, | ||
| const_bitmap | kill ) |
DST = A | (FROM1 & ~FROM2). Return true if DST changes.
References a, b, bitmap_and_compl(), bitmap_copy(), BITMAP_ELEMENT_WORDS, bitmap_elt_clear_from(), bitmap_elt_ior(), bitmap_empty_p(), bitmap_equal_p(), bitmap_ior(), bitmap_element::bits, changed, gcc_assert, gcc_checking_assert, bitmap_element::indx, kill, bitmap_element::next, NULL, and r.
Referenced by cand_trans_fun(), compute_available(), compute_laterin(), compute_nearerout(), df_live_transfer_function(), df_lr_transfer_function(), df_md_transfer_function(), df_mir_transfer_function(), df_rd_transfer_function(), df_word_lr_transfer_function(), dse_transfer_function(), find_removable_extensions(), and live_trans_fun().
◆ bitmap_ior_and_compl_into()
| bool bitmap_ior_and_compl_into | ( | bitmap | a, |
| const_bitmap | b, | ||
| const_bitmap | c ) |
A |= (B & ~C). Return true if A changes.
References a, b, bitmap_and_compl(), BITMAP_ELEMENT_WORDS, bitmap_elt_copy(), bitmap_elt_ior(), bitmap_empty_p(), bitmap_ior_into(), bitmap_element::bits, changed, gcc_checking_assert, bitmap_element::indx, bitmap_head::indx, bitmap_element::next, and NULL.
Referenced by df_lr_confluence_n(), df_md_confluence_n(), live_con_fun_n(), loe_visit_block(), and propagate_pseudo_copies().
◆ bitmap_ior_and_into()
| bool bitmap_ior_and_into | ( | bitmap | a, |
| const_bitmap | b, | ||
| const_bitmap | c ) |
A |= (B & C). Return true if A changes.
References a, b, BITMAP_ELEMENT_WORDS, bitmap_elt_copy(), bitmap_elt_ior(), bitmap_empty_p(), bitmap_ior_into(), bitmap_element::bits, changed, gcc_checking_assert, bitmap_element::indx, bitmap_element::next, and NULL.
Referenced by df_md_local_compute(), and do_hoist_insertion().
◆ 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(), vars_ssa_cache::update(), update_live_info(), update_reg_eliminate(), and verify_ssaname_freelists().
◆ bitmap_ior_into_and_free()
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()
|
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 |
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()
|
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()
|
inlinestatic |
Unlink the bitmap element from the current bitmap linked list, and return it to the freelist.
References bitmap_elem_to_freelist(), head::first, gcc_checking_assert, bitmap_element::next, and bitmap_element::prev.
Referenced by bitmap_and_compl(), bitmap_and_compl_into(), bitmap_and_into(), bitmap_clear_bit(), bitmap_clear_range(), bitmap_compl_and_into(), bitmap_first_set_bit_worker(), bitmap_ior_into_and_free(), and bitmap_xor_into().
◆ 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()
Move a bitmap to another bitmap.
References bitmap_clear(), gcc_assert, bitmap_element::next, 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(), symbol_table::process_new_functions(), 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(), symbol_table::process_new_functions(), 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 |
References a, BITMAP_WORD_BITS, i, and popcount_table.
Referenced by bitmap_count_bits_in_word(), bitmap_last_set_bit(), and bitmap_single_bit_set_p().
◆ bitmap_print()
| DEBUG_FUNCTION void bitmap_print | ( | FILE * | file, |
| const_bitmap | head, | ||
| const char * | prefix, | ||
| const char * | suffix ) |
Function to print out the contents of a bitmap. Unlike debug_bitmap_file, it does not print anything but the bits.
References BITMAP_ELEMENT_ALL_BITS, BITMAP_ELEMENT_WORDS, bitmap_tree_to_vec(), BITMAP_WORD_BITS, EXECUTE_IF_SET_IN_BITMAP, i, and bitmap_head::indx.
Referenced by debug_ter(), debug_var_infos_r(), determine_group_iv_costs(), df_set_blocks(), dse_step2_init(), dse_step4(), dse_step5(), dump_bitmap(), find_always_executed_bbs(), iv_ca_dump(), print_cluster(), print_insn_chain(), loop_distribution::rdg_build_partitions(), and same_succ_print().
◆ bitmap_register()
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()
Set a single bit in a bitmap. Return true if the bit changed.
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, bitmap_element::indx, and bitmap_head::indx.
◆ bitmap_set_range()
| void bitmap_set_range | ( | bitmap | head, |
| unsigned int | start, | ||
| unsigned int | count ) |
Set COUNT bits from START in HEAD.
References BITMAP_ELEMENT_ALL_BITS, bitmap_element_allocate(), BITMAP_ELEMENT_WORDS, bitmap_list_find_element(), bitmap_list_insert_element_after(), bitmap_list_link_element(), bitmap_set_bit, BITMAP_WORD_BITS, bitmap_element::bits, count, gcc_checking_assert, i, bitmap_element::indx, bitmap_element::next, and bitmap_element::prev.
Referenced by add_used_regs(), loop_distribution::break_alias_scc_partitions(), df_mark_reg(), df_rd_bb_local_compute_process_def(), df_rd_dump_defs_set(), df_rd_local_compute(), df_rd_transfer_function(), ext_dce_process_bb(), ext_dce_process_uses(), initiate_live_solver(), look_for_hardregs(), mark_effect(), relate_compare_use_with_all_cands(), set_all_positions_unneeded(), setup_live_bytes_from_ref(), solution_set_expand(), loop_distribution::transform_reduction_loop(), and verify_ssaname_freelists().
◆ bitmap_single_bit_set_p()
| bool bitmap_single_bit_set_p | ( | const_bitmap | a | ) |
Return true if the bitmap has a single bit set. Otherwise return false.
References a, BITMAP_ELEMENT_WORDS, bitmap_empty_p(), bitmap_popcount(), bitmap_element::bits, count, bitmap_element::next, NULL, and bitmap_element::prev.
Referenced by curr_insn_transform(), pt_solution_singleton_or_null_p(), and same_succ_flush_bb().
◆ bitmap_tree_find_element()
|
inlinestatic |
Return the element for INDX, or NULL if the element doesn't exist.
References bitmap_mem_desc, bitmap_tree_splay(), head::first, gcc_checking_assert, bitmap_element::indx, bitmap_usage::m_nsearches, NULL, and usage().
Referenced by bitmap_bit_p(), bitmap_clear_bit(), bitmap_get_aligned_chunk(), bitmap_set_aligned_chunk(), and bitmap_set_bit().
◆ bitmap_tree_link_element()
|
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()
|
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()
|
inlinestatic |
References bitmap_element::prev, and r.
Referenced by bitmap_tree_splay().
◆ bitmap_tree_listify_from()
|
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()
|
inlinestatic |
References bitmap_element::next, and bitmap_element::prev.
Referenced by bitmap_tree_splay().
◆ bitmap_tree_rotate_right()
|
inlinestatic |
References bitmap_element::next, and bitmap_element::prev.
Referenced by bitmap_list_view(), and bitmap_tree_splay().
◆ bitmap_tree_splay()
|
static |
References bitmap_mem_desc, bitmap_tree_link_left(), bitmap_tree_link_right(), bitmap_tree_rotate_left(), bitmap_tree_rotate_right(), bitmap_element::indx, N, bitmap_element::next, NULL, bitmap_element::prev, r, and usage().
Referenced by bitmap_clear(), bitmap_tree_find_element(), bitmap_tree_link_element(), bitmap_tree_listify_from(), and bitmap_tree_unlink_element().
◆ bitmap_tree_to_vec()
|
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 |
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(), df_worklist_dataflow_doublequeue(), dom_jt_state::dom_jt_state(), equiv_oracle::equiv_oracle(), find_always_executed_bbs(), ifcombine_replace_cond(), 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()
| void bitmap_xor | ( | bitmap | dst, |
| const_bitmap | a, | ||
| const_bitmap | b ) |
DST = A ^ B
References a, b, bitmap_clear(), BITMAP_ELEMENT_WORDS, bitmap_elt_clear_from(), bitmap_list_insert_element_after(), bitmap_element::bits, gcc_assert, gcc_checking_assert, bitmap_element::indx, bitmap_element::next, NULL, and r.
◆ bitmap_xor_into()
| void bitmap_xor_into | ( | bitmap | a, |
| const_bitmap | b ) |
◆ 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 |
Account the overhead.
References b, and bitmap_mem_desc.
Referenced by bitmap_alloc(), bitmap_element_allocate(), bitmap_gc_alloc(), and bitmap_move().
◆ release_overhead()
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_obstack bitmap_default_obstack |
Referenced by auto_bitmap::auto_bitmap(), bitmap_alloc(), bitmap_obstack_initialize(), bitmap_obstack_release(), compute_live_vars(), create_new_chain(), df_chain_create_bb(), df_live_verify_transfer_functions(), df_lr_verify_transfer_functions(), df_md_local_compute(), ext_dce_init(), init_rename_info(), regrename_analyze(), and update_ssa().
◆ bitmap_default_obstack_depth
|
static |
Referenced by bitmap_alloc(), bitmap_obstack_initialize(), and bitmap_obstack_release().
◆ bitmap_ggc_free
|
static |
Referenced by bitmap_elem_to_freelist(), bitmap_element_allocate(), and bitmap_elt_clear_from().
◆ bitmap_mem_desc
| mem_alloc_description<bitmap_usage> bitmap_mem_desc |
Functions to support general ended bitmaps. Copyright (C) 1997-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/>.
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 |
Global data
Referenced by bmp_iter_and_compl_init(), bmp_iter_and_init(), and bmp_iter_set_init().
◆ popcount_table
|
static |
Table of number of set bits in a character, indexed by value of char.
Referenced by bitmap_popcount().
