GCC Middle and Back End API Reference
|
#include <hash-table.h>
Data Structures | |
class | iterator |
Public Member Functions | |
hash_table (size_t, bool ggc=false, bool sanitize_eq_and_hash=true, bool gather_mem_stats=GATHER_STATISTICS, mem_alloc_origin origin=HASH_TABLE_ORIGIN CXX_MEM_STAT_INFO) | |
hash_table (const hash_table &, bool ggc=false, bool sanitize_eq_and_hash=true, bool gather_mem_stats=GATHER_STATISTICS, mem_alloc_origin origin=HASH_TABLE_ORIGIN CXX_MEM_STAT_INFO) | |
~hash_table () | |
size_t | size () const |
size_t | elements () const |
size_t | elements_with_deleted () const |
void | empty () |
bool | is_empty () const |
void | clear_slot (value_type *) |
value_type & | find_with_hash (const compare_type &, hashval_t) |
value_type & | find (const value_type &value) |
value_type * | find_slot (const value_type &value, insert_option insert) |
value_type * | find_slot_with_hash (const compare_type &comparable, hashval_t hash, enum insert_option insert) |
void | remove_elt_with_hash (const compare_type &, hashval_t) |
void | remove_elt (const value_type &value) |
template<typename Argument, int(*)(value_type *slot, Argument argument) Callback> | |
void | traverse_noresize (Argument argument) |
template<typename Argument, int(*)(value_type *slot, Argument argument) Callback> | |
void | traverse (Argument argument) |
iterator | begin () const |
iterator | end () const |
double | collisions () const |
void | check_complete_insertion () const |
Static Public Member Functions | |
static hash_table * | create_ggc (size_t n, bool sanitize_eq_and_hash=true CXX_MEM_STAT_INFO) |
Private Types | |
typedef Descriptor::value_type | value_type |
typedef Descriptor::compare_type | compare_type |
Private Member Functions | |
void | operator= (hash_table &) |
void | empty_slow () |
value_type * | alloc_entries (size_t n CXX_MEM_STAT_INFO) const |
value_type * | find_empty_slot_for_expand (hashval_t) |
void | verify (const compare_type &comparable, hashval_t hash) |
bool | too_empty_p (unsigned int) |
void | expand () |
value_type * | check_insert_slot (value_type *ret) |
Static Private Member Functions | |
static bool | is_deleted (value_type &v) |
static bool | is_empty (value_type &v) |
static void | mark_deleted (value_type &v) |
static void | mark_empty (value_type &v) |
Private Attributes | |
value_type * | m_entries |
size_t | m_size |
size_t | m_n_elements |
size_t | m_n_deleted |
unsigned int | m_searches |
unsigned int | m_collisions |
unsigned int | m_size_prime_index |
bool | m_ggc |
bool | m_sanitize_eq_and_hash |
Static Private Attributes | |
static const bool | m_gather_mem_stats = false |
Friends | |
template<typename T> | |
void | gt_ggc_mx (hash_table< T > *) |
template<typename T> | |
void | gt_pch_nx (hash_table< T > *) |
template<typename T> | |
void | hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op, void *cookie) |
template<typename T, typename U, typename V> | |
void | gt_pch_nx (hash_map< T, U, V > *, gt_pointer_operator, void *) |
template<typename T, typename U> | |
void | gt_pch_nx (hash_set< T, false, U > *, gt_pointer_operator, void *) |
template<typename T> | |
void | gt_pch_nx (hash_table< T > *, gt_pointer_operator, void *) |
template<typename T> | |
void | gt_cleare_cache (hash_table< T > *) |
User-facing hash table type. The table stores elements of type Descriptor::value_type and uses the static descriptor functions described at the top of the file to hash, compare and remove elements. Specify the template Allocator to allocate and free memory. The default is xcallocator. Storage is an implementation detail and should not be used outside the hash table code.
|
private |
|
private |
|
explicit |
References alloc_entries(), FINAL_PASS_MEM_STAT, hash_table_higher_prime_index(), hash_table_usage(), if(), m_collisions, m_entries, m_gather_mem_stats, m_ggc, m_n_deleted, m_n_elements, m_sanitize_eq_and_hash, m_searches, m_size, m_size_prime_index, MEM_STAT_DECL, NULL, PASS_MEM_STAT, prime_tab, and size().
Referenced by hash_table().
|
explicit |
hash_table< Descriptor, Lazy, Allocator >::~hash_table | ( | ) |
References check_complete_insertion(), ggc_free(), hash_table_usage(), i, is_deleted(), is_empty(), m_entries, m_gather_mem_stats, m_ggc, and m_size.
|
inlineprivate |
This function returns an array of empty hash table elements.
References alloc_entries(), gcc_assert, ggc_cleared_vec_alloc(), hash_table_usage(), i, m_gather_mem_stats, m_ggc, mark_empty(), MEM_STAT_DECL, NULL, and PASS_MEM_STAT.
Referenced by alloc_entries(), empty_slow(), expand(), find_slot_with_hash(), find_with_hash(), and hash_table().
|
inline |
Referenced by gt_cleare_cache(), and shrink_simd_arrays().
|
inline |
|
inlineprivate |
Referenced by find_slot_with_hash().
void hash_table< Descriptor, Lazy, Allocator >::clear_slot | ( | value_type * | slot | ) |
This function clears a specified SLOT in a hash table. It is useful when you've already done the lookup and don't want to do it again.
References check_complete_insertion(), gcc_checking_assert, is_deleted(), is_empty(), m_entries, m_n_deleted, mark_deleted(), and size().
Referenced by gt_cleare_cache(), ipa_merge_profiles(), lto_free_function_in_decl_state_for_node(), move_sese_region_to_fn(), and variable_was_changed().
|
inline |
Referenced by htab_statistics(), and htab_statistics().
|
inlinestatic |
Referenced by add_addr_table_entry(), add_filepath_AT_string(), add_skeleton_AT_string(), create_constant_pool(), decl_debug_args_insert(), decl_for_type_lookup(), expand_block_edges(), find_AT_string(), cgraph_node::get_edge(), init_emit_once(), init_one_libfunc_visibility(), init_optabs(), init_temp_slots(), init_tree_ssa(), init_ttree(), init_varasm_once(), cgraph_node::insert_new_function_version(), ipa_check_create_edge_args(), ipa_record_return_value_range(), ipcp_transformation_initialize(), new_ctf_container(), output_line_string(), record_insns(), record_loop_exits(), record_tm_clone_pair(), record_tm_replacement(), scev_initialize(), symtab_node::set_section_for_node(), split_bb_make_tm_edge(), symbol_table::symtab_initialize_asm_name_hash(), and types_used_by_var_decl_insert().
|
inline |
Referenced by btf_add_vars(), btf_collect_translated_types(), ctf_preprocess(), ctfc_get_num_ctf_types(), ctfc_get_num_ctf_vars(), dataflow_set_merge(), expand(), gen_parallel_loop(), htab_statistics(), htab_statistics(), hash_table< decl_table_entry_hasher >::is_empty(), num_coalesce_pairs(), output_btf_types(), output_ctf_types(), shared_hash_unshare(), traverse(), and vt_find_locations().
|
inline |
|
inline |
Referenced by ctfc_delete_container(), delete_tree_ssa(), parallelize_loops(), and release_recorded_exits().
|
private |
Implements empty() in cases where it isn't a no-op.
References alloc_entries(), check_complete_insertion(), ggc_free(), hash_table_higher_prime_index(), i, is_deleted(), is_empty(), m_entries, m_ggc, m_n_deleted, m_n_elements, m_size, m_size_prime_index, mark_empty(), prime_tab, size(), and too_empty_p().
Referenced by hash_table< decl_table_entry_hasher >::empty().
|
inline |
Referenced by gt_cleare_cache(), and shrink_simd_arrays().
|
private |
The following function changes size of memory allocated for the entries and repeatedly inserts the table elements. The occupancy of the table after the call will be about 50%. Naturally the hash table must already exist. Remember also that the place of the table entries is changed. If memory allocation fails, this function will abort.
References alloc_entries(), check_complete_insertion(), elements(), find_empty_slot_for_expand(), gcc_checking_assert, ggc_free(), hash_table_higher_prime_index(), hash_table_usage(), is_deleted(), is_empty(), m_entries, m_gather_mem_stats, m_ggc, m_n_deleted, m_n_elements, m_size, m_size_prime_index, prime_tab, size(), and too_empty_p().
Referenced by find_slot_with_hash(), and traverse().
|
inline |
|
private |
Similar to find_slot, but without several unwanted side effects: - Does not call equal when it finds an existing entry. - Does not change the count of elements/searches/collisions in the hash table. This function also assumes there are no deleted entries in the table. HASH is the hash value for the element to be inserted.
References find_empty_slot_for_expand(), gcc_checking_assert, hash_table_mod1(), hash_table_mod2(), is_deleted(), is_empty(), m_entries, m_size, m_size_prime_index, and size().
Referenced by expand(), and find_empty_slot_for_expand().
|
inline |
Referenced by account_time_size(), add_action_record(), add_ehspec_entry(), analyze_insns_in_loop(), build_new_reduction(), ctf_dtd_insert(), ctf_dtd_lookup(), ctf_dvd_ignore_insert(), ctf_dvd_ignore_lookup(), ctf_dvd_insert(), ctf_dvd_lookup(), dead_debug_global_insert(), ipa_merge_profiles(), lookup_or_add_counter(), lto_free_function_in_decl_state_for_node(), lto_get_function_in_decl_state(), maybe_copy_prologue_epilogue_insn(), populate_coalesce_list_for_outofssa(), prune_predictions_for_bb(), record_insns(), split_out_patterns(), streamer_string_index(), take_address_of(), undistribute_ops_list(), update_mem_ref_hash_table(), vect_peeling_hash_insert(), vect_transform_loops(), and vtbl_map_node_registration_insert().
hash_table< Descriptor, Lazy, Allocator >::value_type * hash_table< Descriptor, Lazy, Allocator >::find_slot_with_hash | ( | const compare_type & | comparable, |
hashval_t | hash, | ||
enum insert_option | insert ) |
This function searches for a hash table slot containing an entry equal to the given COMPARABLE element and starting with the given HASH. To delete an entry, call this with insert=NO_INSERT, then call clear_slot on the slot returned (possibly after doing some checks). To insert an entry, call this with insert=INSERT, then write the value you want into the returned slot. When inserting an entry, NULL may be returned if memory allocation fails.
References alloc_entries(), check_complete_insertion(), check_insert_slot(), expand(), hash_table_mod1(), hash_table_mod2(), insert(), is_deleted(), is_empty(), m_collisions, m_entries, m_n_deleted, m_n_elements, m_sanitize_eq_and_hash, m_searches, m_size, m_size_prime_index, mark_empty(), NULL, size(), and verify().
Referenced by add_ttypes_entry(), cgraph_add_edge_to_call_site_hash(), cgraph_update_edge_in_call_site_hash(), find_coalesce_pair(), find_or_insert_inv(), hash_table< decl_table_entry_hasher >::find_slot(), force_const_mem(), move_sese_region_to_fn(), notify_dependents_of_changed_value(), optimize_constant_pool(), register_scoped_attribute(), remove_elt_with_hash(), separate_decls_in_region_debug(), separate_decls_in_region_name(), shared_hash_find_slot_1(), shared_hash_find_slot_noinsert_1(), shared_hash_find_slot_unshare_1(), and vars_copy().
hash_table< Descriptor, Lazy, Allocator >::value_type & hash_table< Descriptor, Lazy, Allocator >::find_with_hash | ( | const compare_type & | comparable, |
hashval_t | hash ) |
This function searches for a hash table entry equal to the given COMPARABLE element starting with the given HASH value. It cannot be used to insert or delete an element.
References alloc_entries(), check_complete_insertion(), hash_table_mod1(), hash_table_mod2(), is_deleted(), is_empty(), m_collisions, m_entries, m_sanitize_eq_and_hash, m_searches, m_size, m_size_prime_index, NULL, size(), and verify().
Referenced by dataflow_set_different(), emit_notes_for_differences_1(), emit_notes_for_differences_2(), hash_table< decl_table_entry_hasher >::find(), find_loc_in_1pdv(), find_mem_expr_in_1pdv(), loc_exp_insert_dep(), notify_dependents_of_changed_value(), notify_dependents_of_resolved_value(), shared_hash_find_1(), and vt_expand_loc_callback().
|
inlinestaticprivate |
|
inline |
Referenced by clear_slot(), dump_vars(), empty_slow(), expand(), find_empty_slot_for_expand(), find_slot_with_hash(), find_with_hash(), gather_scalar_reductions(), gen_parallel_loop(), gt_pch_nx(), reduction_phi(), separate_decls_in_region(), hash_table< Descriptor, Lazy, Allocator >::iterator::slide(), transform_to_exit_first_loop(), traverse_noresize(), try_create_reduction_list(), verify(), and ~hash_table().
|
inlinestaticprivate |
|
inlinestaticprivate |
Referenced by clear_slot(), and remove_elt_with_hash().
|
inlinestaticprivate |
Referenced by alloc_entries(), empty_slow(), and find_slot_with_hash().
|
private |
|
inline |
void hash_table< Descriptor, Lazy, Allocator >::remove_elt_with_hash | ( | const compare_type & | comparable, |
hashval_t | hash ) |
This function deletes an element with the given COMPARABLE value from hash table starting with the given HASH. If there is no matching element in the hash table, this function does nothing.
References check_complete_insertion(), find_slot_with_hash(), m_n_deleted, mark_deleted(), and NULL.
Referenced by hash_table< decl_table_entry_hasher >::remove_elt(), and cgraph_edge::set_call_stmt().
|
inline |
|
inlineprivate |
Return true if the current table is excessively big for ELTS elements.
References m_size.
Referenced by empty_slow(), expand(), and traverse().
void hash_table< Descriptor, Lazy, Allocator >::traverse | ( | Argument | argument | ) |
Like traverse_noresize, but does resize the table when it is too empty to improve effectivity of subsequent calls.
References elements(), expand(), m_entries, too_empty_p(), and traverse().
Referenced by btf_collect_translated_types(), clobber_overlapping_mems(), compute_bb_dataflow(), create_call_for_reduction(), create_final_loads_for_reduction(), ctf_preprocess(), dataflow_post_merge_adjust(), dataflow_set_clear_at_call(), dump_vars(), emit_notes_for_differences(), gather_scalar_reductions(), gen_parallel_loop(), separate_decls_in_region(), traverse(), vt_emit_notes(), and vt_find_locations().
void hash_table< Descriptor, Lazy, Allocator >::traverse_noresize | ( | Argument | argument | ) |
This function scans over the entire hash table calling CALLBACK for each live entry. If CALLBACK returns false, the iteration stops. ARGUMENT is passed as CALLBACK's second argument.
References check_complete_insertion(), is_deleted(), is_empty(), m_entries, NULL, size(), and traverse_noresize().
Referenced by statistics_fini_pass(), and traverse_noresize().
|
private |
Verify that all existing elements in the hash table which are equal to COMPARABLE have an equal HASH value provided as argument. Also check that the hash table element counts are correct.
References gcc_checking_assert, hash_table_sanitize_eq_limit, hashtab_chk_error(), i, is_deleted(), is_empty(), m_entries, m_n_deleted, m_n_elements, m_size, and MIN.
Referenced by find_slot_with_hash(), and find_with_hash().
|
friend |
|
friend |
|
friend |
|
friend |
|
friend |
|
friend |
|
friend |
|
private |
Referenced by find_slot_with_hash(), find_with_hash(), hash_table(), and hash_table().
|
private |
|
staticprivate |
Referenced by alloc_entries(), expand(), hash_table(), hash_table(), and ~hash_table().
|
private |
Referenced by alloc_entries(), empty_slow(), expand(), hash_table(), hash_table(), and ~hash_table().
|
private |
Referenced by clear_slot(), empty_slow(), expand(), find_slot_with_hash(), hash_table(), hash_table(), remove_elt_with_hash(), and verify().
|
private |
Referenced by empty_slow(), expand(), find_slot_with_hash(), hash_table(), hash_table(), and verify().
|
private |
Referenced by find_slot_with_hash(), find_with_hash(), hash_table(), and hash_table().
|
private |
Referenced by find_slot_with_hash(), find_with_hash(), hash_table(), and hash_table().
|
private |
|
private |
Referenced by empty_slow(), expand(), find_empty_slot_for_expand(), find_slot_with_hash(), find_with_hash(), and hash_table().