https://gcc.gnu.org/g:f00ec077b71fbf53f3202a6f2b176127b7b69eb3
commit r17-5723-gf00ec077b71fbf53f3202a6f2b176127b7b69eb3 Author: David Malcolm <[email protected]> Date: Wed Oct 28 19:23:46 2026 -0400 analyzer: use std::map rather than hash_map for symbol consolidation I've found my usage of hash_map to be error-prone, and the hash calculations tend to show up in the profile. We choose not to support garbage collection in the analyzer, so rework this code to replace hash_map with std::map for simplicity and debuggability. No functional change intended. gcc/analyzer/ChangeLog: * common.h (cmp_types): New decl. * constraint-manager.cc (cmp_types): Move to svalue.c. * region-model-manager.cc (region_model_manager::get_or_create_constant_svalue): Port m_constants_map from hash_map to std::map. (region_model_manager::get_or_create_unknown_svalue): Likewise for m_unknowns_map. (region_model_manager::get_or_create_initial_value): Likewise for m_initial_values_map. (region_model_manager::get_or_create_setjmp_svalue): Likewise for m_setjmp_values_map. (region_model_manager::get_or_create_poisoned_svalue): Likewise for m_poisoned_values_map. (region_model_manager::get_ptr_svalue): Likewise for m_pointer_values_map. (region_model_manager::get_or_create_unaryop): Likewise for m_unaryop_values_map. (region_model_manager::get_or_create_binop): Likewise for m_binop_values_map. (region_model_manager::get_or_create_sub_svalue): Likewise for m_sub_values_map. (region_model_manager::get_or_create_repeated_svalue): Likewise for m_repeated_values_map. (region_model_manager::get_or_create_bits_within): Likewise for m_bits_within_values_map. (region_model_manager::get_or_create_unmergeable): Likewise for m_unmergeable_values_map. (region_model_manager::get_or_create_widening_svalue): Likewise for m_widening_values_map. (region_model_manager::get_or_create_compound_svalue): Likewise for m_compound_values_map. (region_model_manager::get_or_create_conjured_svalue): Likewise for m_conjured_values_map. (region_model_manager::get_or_create_asm_output_svalue): Likewise for m_asm_output_values_map. (region_model_manager::get_or_create_const_fn_result_svalue): Likewise for m_const_fn_result_values_map. (region_model_manager::get_region_for_fndecl): Likewise for m_fndecls_map. (region_model_manager::get_region_for_label): Likewise for m_labels_map. (region_model_manager::get_region_for_global): Likewise for m_global_map. (region_model_manager::get_field_region): Make "key" const. (region_model_manager::get_element_region): Likewise. (region_model_manager::get_offset_region): Likewise. (region_model_manager::get_sized_region): Likewise. (region_model_manager::get_cast_region): Likewise. (region_model_manager::get_frame_region): Likewise. (region_model_manager::get_region_for_string): Port m_string_map from hash_map to std::map. (region_model_manager::get_bit_range): Make "key" const. (region_model_manager::get_var_arg_region): Likewise. (log_uniq_map): Implement for std::map. * region-model-manager.h (region_model_manager::constants_map_t): Convert from hash_map to std::map. (region_model_manager::unknowns_map_t): Likewise. (region_model_manager::poisoned_values_map_t): Likewise. (region_model_manager::setjmp_values_map_t): Likewise. (region_model_manager::initial_values_map_t): Likewise. (region_model_manager::pointer_values_map_t): Likewise. (region_model_manager::unaryop_values_map_t): Likewise. (region_model_manager::binop_values_map_t): Likewise. (region_model_manager::sub_values_map_t): Likewise. (region_model_manager::repeated_values_map_t): Likewise. (region_model_manager::bits_within_values_map_t): Likewise. (region_model_manager::unmergeable_values_map_t): Likewise. (region_model_manager::widening_values_map_t): Likewise. (region_model_manager::compound_values_map_t): Likewise. (region_model_manager::conjured_values_map_t): Likewise. (region_model_manager::asm_output_values_map_t): Likewise. (region_model_manager::const_fn_result_values_map_t): Likewise. (region_model_manager::fndecls_map_t): Likewise. (region_model_manager::labels_map_t): Likewise. (region_model_manager::globals_map_t): Likewise. (region_model_manager::string_map_t): Likewise. * setjmp-longjmp.cc (setjmp_svalue::key_t::operator<): New. * svalue.cc (cmp_types) Move here from constraint-manager.cc and make non-static. (region_svalue::key_t::operator<): New. (constant_svalue::key_t::operator<): New. (unaryop_svalue::key_t::operator<): New. (binop_svalue::key_t::operator<): New. (sub_svalue::key_t::operator<): New. (repeated_svalue::key_t::operator<): New. (bits_within_svalue::key_t::operator<): New. (widening_svalue::key_t::operator<): New. (compound_svalue::key_t::operator<): New. (conjured_svalue::key_t::operator<): New. (asm_output_svalue::key_t::operator<): New. (const_fn_result_svalue::key_t::operator<): New. * svalue.h (region_svalue::key_t::hash): Delete. (region_svalue::key_t::operator<): New decl. (region_svalue::key_t::mark_deleted): Delete. (region_svalue::key_t::mark_empty): Delete. (region_svalue::key_t::is_deleted): Delete. (region_svalue::key_t::is_empty): Delete. (struct default_hash_traits<region_svalue::key_t>): Delete. (constant_svalue::key_t::hash): Delete. (constant_svalue::key_t::operator<): New. (constant_svalue::key_t::mark_deleted): Delete. (constant_svalue::key_t::mark_empty): Delete. (constant_svalue::key_t::is_deleted) Delete. (constant_svalue::key_t::is_empty): Delete. (struct default_hash_traits<constant_svalue::key_t>): Delete. (poisoned_svalue::key_t::hash): Delete. (poisoned_svalue::key_t::operator<): New. (poisoned_svalue::key_t::mark_deleted): Delete. (poisoned_svalue::key_t::mark_empty): Delete. (poisoned_svalue::key_t::is_deleted): Delete. (poisoned_svalue::key_t::is_empty): Delete. (struct default_hash_traits<poisoned_svalue::key_t>): Delete. (setjmp_record::add_to_hash): Delete. (setjmp_svalue::key_t::hash): Delete. (setjmp_svalue::key_t::operator<): New. (setjmp_svalue::key_t::mark_deleted): Delete. (setjmp_svalue::key_t::mark_empty): Delete. (setjmp_svalue::key_t::is_deleted): Delete. (setjmp_svalue::key_t::is_empty): Delete. (struct default_hash_traits<setjmp_svalue::key_t>): Delete. (unaryop_svalue::key_t::hash): Delete. (unaryop_svalue::key_t::operator<): New. (unaryop_svalue::key_t::mark_deleted): Delete. (unaryop_svalue::key_t::mark_empty): Delete. (unaryop_svalue::key_t::is_deleted): Delete. (unaryop_svalue::key_t::is_empty): Delete. (struct default_hash_traits<unaryop_svalue::key_t>): Delete. (binop_svalue::key_t::hash): Delete. (binop_svalue::key_t::operator<): New. (binop_svalue::key_t::mark_deleted): Delete. (binop_svalue::key_t::mark_empty): Delete. (binop_svalue::key_t::is_deleted): Delete. (binop_svalue::key_t::is_empty): Delete. (struct default_hash_traits<binop_svalue::key_t>): Delete. (sub_svalue::key_t::hash): Delete. (sub_svalue::key_t::operator<): New. (sub_svalue::key_t::mark_deleted): Delete. (sub_svalue::key_t::mark_empty): Delete. (sub_svalue::key_t::is_deleted): Delete. (sub_svalue::key_t::is_empty): Delete. (struct default_hash_traits<sub_svalue::key_t>): Delete. (repeated_svalue::key_t::hash): Delete. (repeated_svalue::key_t::operator<): New. (repeated_svalue::key_t::mark_deleted): Delete. (repeated_svalue::key_t::mark_empty): Delete. (repeated_svalue::key_t::is_deleted): Delete. (repeated_svalue::key_t::is_empty): Delete. (struct default_hash_traits<repeated_svalue::key_t>): Delete. (bits_within_svalue::key_t::hash): Delete. (bits_within_svalue::key_t::operator<): New. (bits_within_svalue::key_t::mark_deleted): Delete. (bits_within_svalue::key_t::mark_empty): Delete. (bits_within_svalue::key_t::is_deleted): Delete. (bits_within_svalue::key_t::is_empty): Delete. (struct default_hash_traits<bits_within_svalue::key_t>): Delete. (class widening_svalue): Update leading comment. (widening_svalue::key_t::hash): Delete. (widening_svalue::key_t::operator<): New. (widening_svalue::key_t::mark_deleted): Delete. (widening_svalue::key_t::mark_empty): Delete. (widening_svalue::key_t::is_deleted): Delete. (widening_svalue::key_t::is_empty): Delete. (struct default_hash_traits<widening_svalue::key_t>): Delete. (compound_svalue::key_t::hash): Delete. (compound_svalue::key_t::operator<): New. (compound_svalue::key_t::mark_deleted): Delete. (compound_svalue::key_t::mark_empty): Delete. (compound_svalue::key_t::is_deleted): Delete. (compound_svalue::key_t::is_empty): Delete. (struct default_hash_traits<compound_svalue::key_t>): Delete. (conjured_svalue::key_t::hash): Delete (conjured_svalue::key_t::operator<): New. (conjured_svalue::key_t::mark_deleted): Delete. (conjured_svalue::key_t::mark_empty): Delete. (conjured_svalue::key_t::is_deleted): Delete. (conjured_svalue::key_t::is_empty): Delete. (struct default_hash_traits<conjured_svalue::key_t>): Delete. (asm_output_svalue::key_t::hash): Delete. (asm_output_svalue::key_t::operator<): New. (asm_output_svalue::key_t::mark_deleted): Delete. (asm_output_svalue::key_t::mark_empty): Delete. (asm_output_svalue::key_t::is_deleted): Delete. (asm_output_svalue::key_t::is_empty): Delete. (struct default_hash_traits<asm_output_svalue::key_t>): Delete. (const_fn_result_svalue::key_t::hash): Delete. (const_fn_result_svalue::key_t::operator<): New. (const_fn_result_svalue::key_t::mark_deleted): Delete. (const_fn_result_svalue::key_t::mark_empty): Delete. (const_fn_result_svalue::key_t::is_deleted): Delete. (const_fn_result_svalue::key_t::is_empty): Delete. (struct default_hash_traits<const_fn_result_svalue::key_t>): Delete. Signed-off-by: David Malcolm <[email protected]> Diff: --- gcc/analyzer/common.h | 1 + gcc/analyzer/constraint-manager.cc | 8 - gcc/analyzer/region-model-manager.cc | 230 ++++++++++++++----------- gcc/analyzer/region-model-manager.h | 46 +++-- gcc/analyzer/setjmp-longjmp.cc | 8 + gcc/analyzer/svalue.cc | 159 +++++++++++++++++ gcc/analyzer/svalue.h | 323 +++-------------------------------- 7 files changed, 345 insertions(+), 430 deletions(-) diff --git a/gcc/analyzer/common.h b/gcc/analyzer/common.h index 637f8a432206..3ffcebd69c03 100644 --- a/gcc/analyzer/common.h +++ b/gcc/analyzer/common.h @@ -162,6 +162,7 @@ extern void print_expr_for_user (pretty_printer *pp, tree t); extern bool printable_expr_p (const_tree expr); extern int readability_comparator (const void *p1, const void *p2); extern int tree_cmp (const void *p1, const void *p2); +extern int cmp_types (const_tree a, const_tree b); extern tree fixup_tree_for_diagnostic (tree); extern tree get_diagnostic_tree_for_gassign (const gassign *); diff --git a/gcc/analyzer/constraint-manager.cc b/gcc/analyzer/constraint-manager.cc index 57e98f9d1198..3293f21b3245 100644 --- a/gcc/analyzer/constraint-manager.cc +++ b/gcc/analyzer/constraint-manager.cc @@ -512,14 +512,6 @@ bounded_range::operator== (const bounded_range &other) const && tree_int_cst_equal (m_upper, other.m_upper)); } -static int -cmp_types (const_tree type1, const_tree type2) -{ - int t1 = TYPE_UID (type1); - int t2 = TYPE_UID (type2); - return t1 - t2; -} - int bounded_range::cmp (const bounded_range &br1, const bounded_range &br2) { diff --git a/gcc/analyzer/region-model-manager.cc b/gcc/analyzer/region-model-manager.cc index 4b1aacccb632..8899a4c8dcb2 100644 --- a/gcc/analyzer/region-model-manager.cc +++ b/gcc/analyzer/region-model-manager.cc @@ -210,14 +210,14 @@ region_model_manager::get_or_create_constant_svalue (tree type, tree cst_expr) gcc_assert (CONSTANT_CLASS_P (cst_expr)); gcc_assert (type == TREE_TYPE (cst_expr) || type == NULL_TREE); - constant_svalue::key_t key (type, cst_expr); - constant_svalue **slot = m_constants_map.get (key); - if (slot) - return *slot; + const constant_svalue::key_t key (type, cst_expr); + auto iter = m_constants_map.find (key); + if (iter != m_constants_map.end ()) + return iter->second; constant_svalue *cst_sval = new constant_svalue (alloc_symbol_id (), type, cst_expr); RETURN_UNKNOWN_IF_TOO_COMPLEX (cst_sval); - m_constants_map.put (key, cst_sval); + m_constants_map.insert ({key, cst_sval}); return cst_sval; } @@ -281,11 +281,11 @@ region_model_manager::get_or_create_unknown_svalue (tree type) return m_unknown_NULL; } - unknown_svalue **slot = m_unknowns_map.get (type); - if (slot) - return *slot; + auto iter = m_unknowns_map.find (type); + if (iter != m_unknowns_map.end ()) + return iter->second; unknown_svalue *sval = new unknown_svalue (alloc_symbol_id (), type); - m_unknowns_map.put (type, sval); + m_unknowns_map.insert ({type, sval}); return sval; } @@ -341,12 +341,13 @@ region_model_manager::get_or_create_initial_value (const region *reg, if (reg->symbolic_for_unknown_ptr_p ()) return get_or_create_unknown_svalue (reg->get_type ()); - if (initial_svalue **slot = m_initial_values_map.get (reg)) - return *slot; + auto iter = m_initial_values_map.find (reg); + if (iter != m_initial_values_map.end ()) + return iter->second; initial_svalue *initial_sval = new initial_svalue (alloc_symbol_id (), reg->get_type (), reg); RETURN_UNKNOWN_IF_TOO_COMPLEX (initial_sval); - m_initial_values_map.put (reg, initial_sval); + m_initial_values_map.insert ({reg, initial_sval}); return initial_sval; } @@ -357,12 +358,13 @@ const svalue * region_model_manager::get_or_create_setjmp_svalue (const setjmp_record &r, tree type) { - setjmp_svalue::key_t key (r, type); - if (setjmp_svalue **slot = m_setjmp_values_map.get (key)) - return *slot; + const setjmp_svalue::key_t key (r, type); + auto iter = m_setjmp_values_map.find (key); + if (iter != m_setjmp_values_map.end ()) + return iter->second; setjmp_svalue *setjmp_sval = new setjmp_svalue (r, alloc_symbol_id (), type); RETURN_UNKNOWN_IF_TOO_COMPLEX (setjmp_sval); - m_setjmp_values_map.put (key, setjmp_sval); + m_setjmp_values_map.insert ({key, setjmp_sval}); return setjmp_sval; } @@ -373,13 +375,14 @@ const svalue * region_model_manager::get_or_create_poisoned_svalue (enum poison_kind kind, tree type) { - poisoned_svalue::key_t key (kind, type); - if (poisoned_svalue **slot = m_poisoned_values_map.get (key)) - return *slot; + const poisoned_svalue::key_t key (kind, type); + auto iter = m_poisoned_values_map.find (key); + if (iter != m_poisoned_values_map.end ()) + return iter->second; poisoned_svalue *poisoned_sval = new poisoned_svalue (kind, alloc_symbol_id (), type); RETURN_UNKNOWN_IF_TOO_COMPLEX (poisoned_sval); - m_poisoned_values_map.put (key, poisoned_sval); + m_poisoned_values_map.insert ( {key, poisoned_sval} ); return poisoned_sval; } @@ -395,13 +398,14 @@ region_model_manager::get_ptr_svalue (tree ptr_type, const region *pointee) if (ptr_type == sym_reg->get_pointer ()->get_type ()) return sym_reg->get_pointer (); - region_svalue::key_t key (ptr_type, pointee); - if (region_svalue **slot = m_pointer_values_map.get (key)) - return *slot; + const region_svalue::key_t key (ptr_type, pointee); + auto iter = m_pointer_values_map.find (key); + if (iter != m_pointer_values_map.end ()) + return iter->second; region_svalue *sval = new region_svalue (alloc_symbol_id (), ptr_type, pointee); RETURN_UNKNOWN_IF_TOO_COMPLEX (sval); - m_pointer_values_map.put (key, sval); + m_pointer_values_map.insert ({key, sval}); return sval; } @@ -559,13 +563,14 @@ region_model_manager::get_or_create_unaryop (tree type, enum tree_code op, { if (const svalue *folded = maybe_fold_unaryop (type, op, arg)) return folded; - unaryop_svalue::key_t key (type, op, arg); - if (unaryop_svalue **slot = m_unaryop_values_map.get (key)) - return *slot; + const unaryop_svalue::key_t key (type, op, arg); + auto iter = m_unaryop_values_map.find (key); + if (iter != m_unaryop_values_map.end ()) + return iter->second; unaryop_svalue *unaryop_sval = new unaryop_svalue (alloc_symbol_id (), type, op, arg); RETURN_UNKNOWN_IF_TOO_COMPLEX (unaryop_sval); - m_unaryop_values_map.put (key, unaryop_sval); + m_unaryop_values_map.insert ({key, unaryop_sval}); return unaryop_sval; } @@ -991,13 +996,14 @@ region_model_manager::get_or_create_binop (tree type, enum tree_code op, || !arg1->can_have_associated_state_p ()) return get_or_create_unknown_svalue (type); - binop_svalue::key_t key (type, op, arg0, arg1); - if (binop_svalue **slot = m_binop_values_map.get (key)) - return *slot; + const binop_svalue::key_t key (type, op, arg0, arg1); + auto iter = m_binop_values_map.find (key); + if (iter != m_binop_values_map.end ()) + return iter->second; binop_svalue *binop_sval = new binop_svalue (alloc_symbol_id (), type, op, arg0, arg1); RETURN_UNKNOWN_IF_TOO_COMPLEX (binop_sval); - m_binop_values_map.put (key, binop_sval); + m_binop_values_map.insert ({key, binop_sval}); return binop_sval; } @@ -1104,13 +1110,14 @@ region_model_manager::get_or_create_sub_svalue (tree type, = maybe_fold_sub_svalue (type, parent_svalue, subregion)) return folded; - sub_svalue::key_t key (type, parent_svalue, subregion); - if (sub_svalue **slot = m_sub_values_map.get (key)) - return *slot; + const sub_svalue::key_t key (type, parent_svalue, subregion); + auto iter = m_sub_values_map.find (key); + if (iter != m_sub_values_map.end ()) + return iter->second; sub_svalue *sub_sval = new sub_svalue (alloc_symbol_id (), type, parent_svalue, subregion); RETURN_UNKNOWN_IF_TOO_COMPLEX (sub_sval); - m_sub_values_map.put (key, sub_sval); + m_sub_values_map.insert ({key, sub_sval}); return sub_sval; } @@ -1166,13 +1173,14 @@ region_model_manager::get_or_create_repeated_svalue (tree type, = maybe_fold_repeated_svalue (type, outer_size, inner_svalue)) return folded; - repeated_svalue::key_t key (type, outer_size, inner_svalue); - if (repeated_svalue **slot = m_repeated_values_map.get (key)) - return *slot; + const repeated_svalue::key_t key (type, outer_size, inner_svalue); + auto iter = m_repeated_values_map.find (key); + if (iter != m_repeated_values_map.end ()) + return iter->second; repeated_svalue *repeated_sval = new repeated_svalue (alloc_symbol_id (), type, outer_size, inner_svalue); RETURN_UNKNOWN_IF_TOO_COMPLEX (repeated_sval); - m_repeated_values_map.put (key, repeated_sval); + m_repeated_values_map.insert ({key, repeated_sval}); return repeated_sval; } @@ -1359,13 +1367,14 @@ region_model_manager::get_or_create_bits_within (tree type, = maybe_fold_bits_within_svalue (type, bits, inner_svalue)) return folded; - bits_within_svalue::key_t key (type, bits, inner_svalue); - if (bits_within_svalue **slot = m_bits_within_values_map.get (key)) - return *slot; + const bits_within_svalue::key_t key (type, bits, inner_svalue); + auto iter = m_bits_within_values_map.find (key); + if (iter != m_bits_within_values_map.end ()) + return iter->second; bits_within_svalue *bits_within_sval = new bits_within_svalue (alloc_symbol_id (), type, bits, inner_svalue); RETURN_UNKNOWN_IF_TOO_COMPLEX (bits_within_sval); - m_bits_within_values_map.put (key, bits_within_sval); + m_bits_within_values_map.insert ({key, bits_within_sval}); return bits_within_sval; } @@ -1378,12 +1387,13 @@ region_model_manager::get_or_create_unmergeable (const svalue *arg) if (arg->get_kind () == SK_UNMERGEABLE) return arg; - if (unmergeable_svalue **slot = m_unmergeable_values_map.get (arg)) - return *slot; + auto iter = m_unmergeable_values_map.find (arg); + if (iter != m_unmergeable_values_map.end ()) + return iter->second; unmergeable_svalue *unmergeable_sval = new unmergeable_svalue (alloc_symbol_id (), arg); RETURN_UNKNOWN_IF_TOO_COMPLEX (unmergeable_sval); - m_unmergeable_values_map.put (arg, unmergeable_sval); + m_unmergeable_values_map.insert ({arg, unmergeable_sval}); return unmergeable_sval; } @@ -1399,14 +1409,15 @@ get_or_create_widening_svalue (tree type, { gcc_assert (base_sval->get_kind () != SK_WIDENING); gcc_assert (iter_sval->get_kind () != SK_WIDENING); - widening_svalue::key_t key (type, snode, base_sval, iter_sval); - if (widening_svalue **slot = m_widening_values_map.get (key)) - return *slot; + const widening_svalue::key_t key (type, snode, base_sval, iter_sval); + auto iter = m_widening_values_map.find (key); + if (iter != m_widening_values_map.end ()) + return iter->second; widening_svalue *widening_sval = new widening_svalue (alloc_symbol_id (), type, snode, base_sval, iter_sval); RETURN_UNKNOWN_IF_TOO_COMPLEX (widening_sval); - m_widening_values_map.put (key, widening_sval); + m_widening_values_map.insert ({key, widening_sval}); return widening_sval; } @@ -1417,15 +1428,16 @@ const svalue * region_model_manager::get_or_create_compound_svalue (tree type, concrete_binding_map &&map) { - compound_svalue::key_t tmp_key (type, &map); - if (compound_svalue **slot = m_compound_values_map.get (tmp_key)) - return *slot; + const compound_svalue::key_t tmp_key (type, &map); + auto iter = m_compound_values_map.find (tmp_key); + if (iter != m_compound_values_map.end ()) + return iter->second; compound_svalue *compound_sval = new compound_svalue (alloc_symbol_id (), type, std::move (map)); RETURN_UNKNOWN_IF_TOO_COMPLEX (compound_sval); /* Use make_key rather than reusing the key, so that we use a ptr to compound_sval's binding_map, rather than the MAP param. */ - m_compound_values_map.put (compound_sval->make_key (), compound_sval); + m_compound_values_map.insert ({compound_sval->make_key (), compound_sval}); return compound_sval; } @@ -1437,14 +1449,15 @@ region_model_manager::get_or_create_compound_svalue (tree type, const concrete_binding_map &map) { compound_svalue::key_t tmp_key (type, &map); - if (compound_svalue **slot = m_compound_values_map.get (tmp_key)) - return *slot; + auto iter = m_compound_values_map.find (tmp_key); + if (iter != m_compound_values_map.end ()) + return iter->second; compound_svalue *compound_sval = new compound_svalue (alloc_symbol_id (), type, map); RETURN_UNKNOWN_IF_TOO_COMPLEX (compound_sval); /* Use make_key rather than reusing the key, so that we use a ptr to compound_sval's binding_map, rather than the MAP param. */ - m_compound_values_map.put (compound_sval->make_key (), compound_sval); + m_compound_values_map.insert ({compound_sval->make_key (), compound_sval}); return compound_sval; } @@ -1471,10 +1484,11 @@ region_model_manager::get_or_create_conjured_svalue (tree type, const conjured_purge &p, unsigned idx) { - conjured_svalue::key_t key (type, stmt, id_reg, idx); - if (conjured_svalue **slot = m_conjured_values_map.get (key)) + const conjured_svalue::key_t key (type, stmt, id_reg, idx); + auto iter = m_conjured_values_map.find (key); + if (iter != m_conjured_values_map.end ()) { - const conjured_svalue *sval = *slot; + const conjured_svalue *sval = iter->second; /* We're reusing an existing conjured_svalue, perhaps from a different state within this analysis, or perhaps from an earlier state on this execution path. For the latter, purge any state involving the "new" @@ -1485,7 +1499,7 @@ region_model_manager::get_or_create_conjured_svalue (tree type, conjured_svalue *conjured_sval = new conjured_svalue (alloc_symbol_id (), type, stmt, id_reg, idx); RETURN_UNKNOWN_IF_TOO_COMPLEX (conjured_sval); - m_conjured_values_map.put (key, conjured_sval); + m_conjured_values_map.insert ({key, conjured_sval}); return conjured_sval; } @@ -1524,14 +1538,15 @@ get_or_create_asm_output_svalue (tree type, const char *asm_string = gimple_asm_string (asm_stmt); const unsigned noutputs = gimple_asm_noutputs (asm_stmt); - asm_output_svalue::key_t key (type, asm_string, output_idx, inputs); - if (asm_output_svalue **slot = m_asm_output_values_map.get (key)) - return *slot; + const asm_output_svalue::key_t key (type, asm_string, output_idx, inputs); + auto iter = m_asm_output_values_map.find (key); + if (iter != m_asm_output_values_map.end ()) + return iter->second; asm_output_svalue *asm_output_sval = new asm_output_svalue (alloc_symbol_id (), type, asm_string, output_idx, noutputs, inputs); RETURN_UNKNOWN_IF_TOO_COMPLEX (asm_output_sval); - m_asm_output_values_map.put (key, asm_output_sval); + m_asm_output_values_map.insert ({key, asm_output_sval}); return asm_output_sval; } @@ -1553,14 +1568,15 @@ get_or_create_asm_output_svalue (tree type, = maybe_fold_asm_output_svalue (type, inputs)) return folded; - asm_output_svalue::key_t key (type, asm_string, output_idx, inputs); - if (asm_output_svalue **slot = m_asm_output_values_map.get (key)) - return *slot; + const asm_output_svalue::key_t key (type, asm_string, output_idx, inputs); + auto iter = m_asm_output_values_map.find (key); + if (iter != m_asm_output_values_map.end ()) + return iter->second; asm_output_svalue *asm_output_sval = new asm_output_svalue (alloc_symbol_id (), type, asm_string, output_idx, num_outputs, inputs); RETURN_UNKNOWN_IF_TOO_COMPLEX (asm_output_sval); - m_asm_output_values_map.put (key, asm_output_sval); + m_asm_output_values_map.insert ({key, asm_output_sval}); return asm_output_sval; } @@ -1578,13 +1594,14 @@ get_or_create_const_fn_result_svalue (tree type, gcc_assert (TREE_READONLY (fndecl)); gcc_assert (inputs.length () <= const_fn_result_svalue::MAX_INPUTS); - const_fn_result_svalue::key_t key (type, fndecl, inputs); - if (const_fn_result_svalue **slot = m_const_fn_result_values_map.get (key)) - return *slot; + const const_fn_result_svalue::key_t key (type, fndecl, inputs); + auto iter = m_const_fn_result_values_map.find (key); + if (iter != m_const_fn_result_values_map.end ()) + return iter->second; const_fn_result_svalue *const_fn_result_sval = new const_fn_result_svalue (alloc_symbol_id (), type, fndecl, inputs); RETURN_UNKNOWN_IF_TOO_COMPLEX (const_fn_result_sval); - m_const_fn_result_values_map.put (key, const_fn_result_sval); + m_const_fn_result_values_map.insert ({key, const_fn_result_sval}); return const_fn_result_sval; } @@ -1687,12 +1704,12 @@ region_model_manager::get_region_for_fndecl (tree fndecl) { gcc_assert (TREE_CODE (fndecl) == FUNCTION_DECL); - function_region **slot = m_fndecls_map.get (fndecl); - if (slot) - return *slot; + auto iter = m_fndecls_map.find (fndecl); + if (iter != m_fndecls_map.end ()) + return iter->second; function_region *reg = new function_region (alloc_symbol_id (), &m_code_region, fndecl); - m_fndecls_map.put (fndecl, reg); + m_fndecls_map.insert ({fndecl, reg}); return reg; } @@ -1703,9 +1720,9 @@ region_model_manager::get_region_for_label (tree label) { gcc_assert (TREE_CODE (label) == LABEL_DECL); - label_region **slot = m_labels_map.get (label); - if (slot) - return *slot; + auto iter = m_labels_map.find (label); + if (iter != m_labels_map.end ()) + return iter->second; tree fndecl = DECL_CONTEXT (label); gcc_assert (fndecl && TREE_CODE (fndecl) == FUNCTION_DECL); @@ -1713,7 +1730,7 @@ region_model_manager::get_region_for_label (tree label) const function_region *func_reg = get_region_for_fndecl (fndecl); label_region *reg = new label_region (alloc_symbol_id (), func_reg, label); - m_labels_map.put (label, reg); + m_labels_map.insert ({label, reg}); return reg; } @@ -1724,12 +1741,13 @@ region_model_manager::get_region_for_global (tree expr) { gcc_assert (VAR_P (expr)); - decl_region **slot = m_globals_map.get (expr); - if (slot) - return *slot; + auto iter = m_globals_map.find (expr); + if (iter != m_globals_map.end ()) + return iter->second; + decl_region *reg = new decl_region (alloc_symbol_id (), &m_globals_region, expr); - m_globals_map.put (expr, reg); + m_globals_map.insert ({expr, reg}); return reg; } @@ -1760,7 +1778,7 @@ region_model_manager::get_field_region (const region *parent, tree field) if (parent->symbolic_for_unknown_ptr_p ()) return get_unknown_symbolic_region (TREE_TYPE (field)); - field_region::key_t key (parent, field); + const field_region::key_t key (parent, field); if (field_region *reg = m_field_regions.get (key)) return reg; @@ -1782,7 +1800,7 @@ region_model_manager::get_element_region (const region *parent, if (parent->symbolic_for_unknown_ptr_p ()) return get_unknown_symbolic_region (element_type); - element_region::key_t key (parent, element_type, index); + const element_region::key_t key (parent, element_type, index); if (element_region *reg = m_element_regions.get (key)) return reg; @@ -1822,7 +1840,7 @@ region_model_manager::get_offset_region (const region *parent, return get_offset_region (parent->get_parent_region (), type, sval_sum); } - offset_region::key_t key (parent, type, byte_offset); + const offset_region::key_t key (parent, type, byte_offset); if (offset_region *reg = m_offset_regions.get (key)) return reg; @@ -1857,7 +1875,7 @@ region_model_manager::get_sized_region (const region *parent, return parent; } - sized_region::key_t key (parent, type, byte_size_sval); + const sized_region::key_t key (parent, type, byte_size_sval); if (sized_region *reg = m_sized_regions.get (key)) return reg; @@ -1881,7 +1899,7 @@ region_model_manager::get_cast_region (const region *original_region, if (original_region->symbolic_for_unknown_ptr_p ()) return get_unknown_symbolic_region (type); - cast_region::key_t key (original_region, type); + const cast_region::key_t key (original_region, type); if (cast_region *reg = m_cast_regions.get (key)) return reg; @@ -1900,7 +1918,7 @@ region_model_manager::get_frame_region (const frame_region *calling_frame, { int index = calling_frame ? calling_frame->get_index () + 1 : 0; - frame_region::key_t key (calling_frame, fun); + const frame_region::key_t key (calling_frame, fun); if (frame_region *reg = m_frame_regions.get (key)) return reg; @@ -1917,7 +1935,7 @@ region_model_manager::get_frame_region (const frame_region *calling_frame, const region * region_model_manager::get_symbolic_region (const svalue *sval) { - symbolic_region::key_t key (&m_root_region, sval); + const symbolic_region::key_t key (&m_root_region, sval); if (symbolic_region *reg = m_symbolic_regions.get (key)) return reg; @@ -1935,12 +1953,13 @@ region_model_manager::get_region_for_string (tree string_cst) { gcc_assert (TREE_CODE (string_cst) == STRING_CST); - string_region **slot = m_string_map.get (string_cst); - if (slot) - return *slot; + auto iter = m_string_map.find (string_cst); + if (iter != m_string_map.end ()) + return iter->second; + string_region *reg = new string_region (alloc_symbol_id (), &m_root_region, string_cst); - m_string_map.put (string_cst, reg); + m_string_map.insert ({string_cst, reg}); return reg; } @@ -1956,7 +1975,7 @@ region_model_manager::get_bit_range (const region *parent, tree type, if (parent->symbolic_for_unknown_ptr_p ()) return get_unknown_symbolic_region (type); - bit_range_region::key_t key (parent, type, bits); + const bit_range_region::key_t key (parent, type, bits); if (bit_range_region *reg = m_bit_range_regions.get (key)) return reg; @@ -1975,7 +1994,7 @@ region_model_manager::get_var_arg_region (const frame_region *parent_frame, { gcc_assert (parent_frame); - var_arg_region::key_t key (parent_frame, idx); + const var_arg_region::key_t key (parent_frame, idx); if (var_arg_region *reg = m_var_arg_regions.get (key)) return reg; @@ -2094,6 +2113,19 @@ log_uniq_map (logger *logger, bool show_objs, const char *title, /* Dump the number of objects that were managed by MAP to LOGGER. If SHOW_OBJS is true, also dump the objects themselves. */ +template <typename K, typename T> +static void +log_uniq_map (logger *logger, bool show_objs, const char *title, + const std::map<K, T*> &map) +{ + logger->log (" # %s: %li", title, (long)map.size ()); + if (!show_objs) + return; + + for (auto &iter : map) + log_managed_object<T> (logger, iter.second); +} + template <typename T> static void log_uniq_map (logger *logger, bool show_objs, const char *title, diff --git a/gcc/analyzer/region-model-manager.h b/gcc/analyzer/region-model-manager.h index 02b5125c435b..6e3e38e57c9d 100644 --- a/gcc/analyzer/region-model-manager.h +++ b/gcc/analyzer/region-model-manager.h @@ -214,68 +214,66 @@ private: heap_region m_heap_region; /* svalue consolidation. */ - typedef hash_map<constant_svalue::key_t, constant_svalue *> constants_map_t; + typedef std::map<constant_svalue::key_t, constant_svalue *> constants_map_t; constants_map_t m_constants_map; - typedef hash_map<tree, unknown_svalue *> unknowns_map_t; + typedef std::map<tree, unknown_svalue *> unknowns_map_t; unknowns_map_t m_unknowns_map; const unknown_svalue *m_unknown_NULL; - typedef hash_map<poisoned_svalue::key_t, + typedef std::map<poisoned_svalue::key_t, poisoned_svalue *> poisoned_values_map_t; poisoned_values_map_t m_poisoned_values_map; - typedef hash_map<setjmp_svalue::key_t, + typedef std::map<setjmp_svalue::key_t, setjmp_svalue *> setjmp_values_map_t; setjmp_values_map_t m_setjmp_values_map; - typedef hash_map<const region *, initial_svalue *> initial_values_map_t; + typedef std::map<const region *, initial_svalue *> initial_values_map_t; initial_values_map_t m_initial_values_map; - typedef hash_map<region_svalue::key_t, region_svalue *> pointer_values_map_t; + typedef std::map<region_svalue::key_t, region_svalue *> pointer_values_map_t; pointer_values_map_t m_pointer_values_map; - typedef hash_map<unaryop_svalue::key_t, + typedef std::map<unaryop_svalue::key_t, unaryop_svalue *> unaryop_values_map_t; unaryop_values_map_t m_unaryop_values_map; - typedef hash_map<binop_svalue::key_t, binop_svalue *> binop_values_map_t; + typedef std::map<binop_svalue::key_t, binop_svalue *> binop_values_map_t; binop_values_map_t m_binop_values_map; - typedef hash_map<sub_svalue::key_t, sub_svalue *> sub_values_map_t; + typedef std::map<sub_svalue::key_t, sub_svalue *> sub_values_map_t; sub_values_map_t m_sub_values_map; - typedef hash_map<repeated_svalue::key_t, + typedef std::map<repeated_svalue::key_t, repeated_svalue *> repeated_values_map_t; repeated_values_map_t m_repeated_values_map; - typedef hash_map<bits_within_svalue::key_t, + typedef std::map<bits_within_svalue::key_t, bits_within_svalue *> bits_within_values_map_t; bits_within_values_map_t m_bits_within_values_map; - typedef hash_map<const svalue *, + typedef std::map<const svalue *, unmergeable_svalue *> unmergeable_values_map_t; unmergeable_values_map_t m_unmergeable_values_map; - typedef hash_map<widening_svalue::key_t, - widening_svalue */*, - widening_svalue::key_t::hash_map_traits*/> - widening_values_map_t; + typedef std::map<widening_svalue::key_t, + widening_svalue *> widening_values_map_t; widening_values_map_t m_widening_values_map; - typedef hash_map<compound_svalue::key_t, + typedef std::map<compound_svalue::key_t, compound_svalue *> compound_values_map_t; compound_values_map_t m_compound_values_map; - typedef hash_map<conjured_svalue::key_t, + typedef std::map<conjured_svalue::key_t, conjured_svalue *> conjured_values_map_t; conjured_values_map_t m_conjured_values_map; - typedef hash_map<asm_output_svalue::key_t, + typedef std::map<asm_output_svalue::key_t, asm_output_svalue *> asm_output_values_map_t; asm_output_values_map_t m_asm_output_values_map; - typedef hash_map<const_fn_result_svalue::key_t, + typedef std::map<const_fn_result_svalue::key_t, const_fn_result_svalue *> const_fn_result_values_map_t; const_fn_result_values_map_t m_const_fn_result_values_map; @@ -292,16 +290,16 @@ private: /* region consolidation. */ code_region m_code_region; - typedef hash_map<tree, function_region *> fndecls_map_t; + typedef std::map<tree, function_region *> fndecls_map_t; typedef fndecls_map_t::iterator fndecls_iterator_t; fndecls_map_t m_fndecls_map; - typedef hash_map<tree, label_region *> labels_map_t; + typedef std::map<tree, label_region *> labels_map_t; typedef labels_map_t::iterator labels_iterator_t; labels_map_t m_labels_map; globals_region m_globals_region; - typedef hash_map<tree, decl_region *> globals_map_t; + typedef std::map<tree, decl_region *> globals_map_t; typedef globals_map_t::iterator globals_iterator_t; globals_map_t m_globals_map; @@ -316,7 +314,7 @@ private: consolidation_map<frame_region> m_frame_regions; consolidation_map<symbolic_region> m_symbolic_regions; - typedef hash_map<tree, string_region *> string_map_t; + typedef std::map<tree, string_region *> string_map_t; string_map_t m_string_map; consolidation_map<bit_range_region> m_bit_range_regions; diff --git a/gcc/analyzer/setjmp-longjmp.cc b/gcc/analyzer/setjmp-longjmp.cc index d0cc8ff6bc4e..602287d7c238 100644 --- a/gcc/analyzer/setjmp-longjmp.cc +++ b/gcc/analyzer/setjmp-longjmp.cc @@ -72,6 +72,14 @@ setjmp_record::cmp (const setjmp_record &rec1, const setjmp_record &rec2) /* class setjmp_svalue : public svalue. */ +bool +setjmp_svalue::key_t::operator< (const key_t &other) const +{ + if (int c = setjmp_record::cmp (m_record, other.m_record)) + return c < 0; + return cmp_types (m_type, other.m_type) < 0; +} + /* Implementation of svalue::accept vfunc for setjmp_svalue. */ void diff --git a/gcc/analyzer/svalue.cc b/gcc/analyzer/svalue.cc index f21fc4c586c5..e6a682efd757 100644 --- a/gcc/analyzer/svalue.cc +++ b/gcc/analyzer/svalue.cc @@ -513,6 +513,14 @@ cmp_csts_same_type (const_tree cst1, const_tree cst2) } } +int +cmp_types (const_tree a, const_tree b) +{ + int t1 = a ? TYPE_UID (a) : -1; + int t2 = b ? TYPE_UID (b) : -1; + return t1 - t2; +} + /* Comparator for imposing a deterministic order on constants that might not be of the same type. */ @@ -923,6 +931,14 @@ svalue::maybe_get_value_range_1 (value_range &out) const /* class region_svalue : public svalue. */ +bool +region_svalue::key_t::operator< (const key_t &other) const +{ + if (int c = cmp_types (m_type, other.m_type)) + return c < 0; + return m_reg->get_id () < other.m_reg->get_id (); +} + /* Implementation of svalue::dump_to_pp vfunc for region_svalue. */ void @@ -1014,6 +1030,17 @@ region_svalue::eval_condition (const region_svalue *lhs, /* class constant_svalue : public svalue. */ +bool +constant_svalue::key_t::operator< (const key_t &other) const +{ + if (int c = cmp_types (m_type, other.m_type)) + return c < 0; + if (int c = cmp_types (TREE_TYPE (m_cst), TREE_TYPE (other.m_cst))) + return c < 0; + gcc_assert (TREE_CODE (m_cst) == TREE_CODE (other.m_cst)); + return cmp_csts_same_type (m_cst, other.m_cst) < 0; +} + /* Implementation of svalue::dump_to_pp vfunc for constant_svalue. */ void @@ -1453,6 +1480,18 @@ initial_svalue::initial_value_of_param_p () const /* class unaryop_svalue : public svalue. */ +bool +unaryop_svalue::key_t::operator< (const key_t &other) const +{ + if (int c = (int)m_op - (int)other.m_op) + return c < 0; + if (int c = cmp_types (m_type, other.m_type)) + return c < 0; + if (int c = symbol::cmp_ids (m_arg, other.m_arg)) + return c < 0; + return false; +} + /* Implementation of svalue::dump_to_pp vfunc for unaryop_svalue. */ void @@ -1585,6 +1624,20 @@ unaryop_svalue::maybe_get_value_range_1 (value_range &out) const /* class binop_svalue : public svalue. */ +bool +binop_svalue::key_t::operator< (const key_t &other) const +{ + if (int c = (int)m_op - (int)other.m_op) + return c < 0; + if (int c = cmp_types (m_type, other.m_type)) + return c < 0; + if (int c = symbol::cmp_ids (m_arg0, other.m_arg0)) + return c < 0; + if (int c = symbol::cmp_ids (m_arg1, other.m_arg1)) + return c < 0; + return false; +} + /* Return whether OP be printed as an infix operator. */ static bool @@ -1685,6 +1738,18 @@ binop_svalue::implicitly_live_p (const svalue_set *live_svalues, /* class sub_svalue : public svalue. */ +bool +sub_svalue::key_t::operator< (const key_t &other) const +{ + if (int c = cmp_types (m_type, other.m_type)) + return c < 0; + if (int c = symbol::cmp_ids (m_parent_svalue, other.m_parent_svalue)) + return c < 0; + if (int c = symbol::cmp_ids (m_subregion, other.m_subregion)) + return c < 0; + return false; +} + /* sub_svalue'c ctor. */ sub_svalue::sub_svalue (symbol::id_t id, @@ -1798,6 +1863,18 @@ sub_svalue::implicitly_live_p (const svalue_set *live_svalues, /* class repeated_svalue : public svalue. */ +bool +repeated_svalue::key_t::operator< (const key_t &other) const +{ + if (int c = cmp_types (m_type, other.m_type)) + return c < 0; + if (int c = symbol::cmp_ids (m_outer_size, other.m_outer_size)) + return c < 0; + if (int c = symbol::cmp_ids (m_inner_svalue, other.m_inner_svalue)) + return c < 0; + return false; +} + /* repeated_svalue'c ctor. */ repeated_svalue::repeated_svalue (symbol::id_t id, @@ -1947,6 +2024,18 @@ repeated_svalue::maybe_fold_bits_within (tree type, /* class bits_within_svalue : public svalue. */ +bool +bits_within_svalue::key_t::operator< (const key_t &other) const +{ + if (int c = cmp_types (m_type, other.m_type)) + return c < 0; + if (int c = bit_range::cmp (m_bits, other.m_bits)) + return c < 0; + if (int c = symbol::cmp_ids (m_inner_svalue, other.m_inner_svalue)) + return c < 0; + return false; +} + /* bits_within_svalue'c ctor. */ bits_within_svalue::bits_within_svalue (symbol::id_t id, @@ -2052,6 +2141,20 @@ bits_within_svalue::implicitly_live_p (const svalue_set *live_svalues, /* class widening_svalue : public svalue. */ +bool +widening_svalue::key_t::operator< (const key_t &other) const +{ + if (int c = cmp_types (m_type, other.m_type)) + return c < 0; + if (int c = m_snode->m_id - other.m_snode->m_id) + return c < 0; + if (int c = symbol::cmp_ids (m_base_sval, other.m_base_sval)) + return c < 0; + if (int c = symbol::cmp_ids (m_iter_sval, other.m_iter_sval)) + return c < 0; + return false; +} + /* Implementation of svalue::dump_to_pp vfunc for widening_svalue. */ void @@ -2331,6 +2434,16 @@ unmergeable_svalue::implicitly_live_p (const svalue_set *live_svalues, /* class compound_svalue : public svalue. */ +bool +compound_svalue::key_t::operator< (const key_t &other) const +{ + if (int c = cmp_types (m_type, other.m_type)) + return c < 0; + if (int c = concrete_binding_map::cmp (*m_map_ptr, *other.m_map_ptr)) + return c < 0; + return false; +} + compound_svalue::compound_svalue (symbol::id_t id, tree type, concrete_binding_map &&map) @@ -2484,6 +2597,20 @@ compound_svalue::maybe_fold_bits_within (tree type, /* class conjured_svalue : public svalue. */ +bool +conjured_svalue::key_t::operator< (const key_t &other) const +{ + if (int c = cmp_types (m_type, other.m_type)) + return c < 0; + if (int c = m_stmt->uid - other.m_stmt->uid) + return c < 0; + if (int c = symbol::cmp_ids (m_id_reg, other.m_id_reg)) + return c < 0; + if (int c = m_idx == other.m_idx) + return c < 0; + return false; +} + /* Implementation of svalue::dump_to_pp vfunc for conjured_svalue. */ void @@ -2558,6 +2685,23 @@ conjured_svalue::lhs_value_p () const /* class asm_output_svalue : public svalue. */ +bool +asm_output_svalue::key_t::operator< (const key_t &other) const +{ + if (int c = cmp_types (m_type, other.m_type)) + return c < 0; + if (int c = strcmp (m_asm_string, other.m_asm_string)) + return c < 0; + if (int c = (int)m_output_idx - (int)other.m_output_idx) + return c < 0; + if (int c = (int)m_num_inputs - (int)other.m_num_inputs) + return c < 0; + for (unsigned i = 0; i < m_num_inputs; i++) + if (int c = symbol::cmp_ids (m_input_arr[i], other.m_input_arr[i])) + return c < 0; + return false; +} + /* Implementation of svalue::dump_to_pp vfunc for asm_output_svalue. */ void @@ -2652,6 +2796,21 @@ asm_output_svalue::accept (visitor *v) const /* class const_fn_result_svalue : public svalue. */ +bool +const_fn_result_svalue::key_t::operator< (const key_t &other) const +{ + if (int c = cmp_types (m_type, other.m_type)) + return c < 0; + if (int c = DECL_UID (m_fndecl) - DECL_UID (other.m_fndecl)) + return c < 0; + if (int c = (int)m_num_inputs - (int)other.m_num_inputs) + return c < 0; + for (unsigned i = 0; i < m_num_inputs; i++) + if (int c = symbol::cmp_ids (m_input_arr[i], other.m_input_arr[i])) + return c < 0; + return false; +} + /* Implementation of svalue::dump_to_pp vfunc for const_fn_result_svalue. */ void diff --git a/gcc/analyzer/svalue.h b/gcc/analyzer/svalue.h index 506981a83294..9322ae90b1f4 100644 --- a/gcc/analyzer/svalue.h +++ b/gcc/analyzer/svalue.h @@ -235,24 +235,12 @@ public: : m_type (type), m_reg (reg) {} - hashval_t hash () const - { - inchash::hash hstate; - hstate.add_ptr (m_type); - hstate.add_ptr (m_reg); - return hstate.end (); - } - + bool operator< (const key_t &other) const; bool operator== (const key_t &other) const { return (m_type == other.m_type && m_reg == other.m_reg); } - void mark_deleted () { m_type = reinterpret_cast<tree> (1); } - void mark_empty () { m_type = reinterpret_cast<tree> (2); } - bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } - bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } - tree m_type; const region *m_reg; }; @@ -301,12 +289,6 @@ is_a_helper <const region_svalue *>::test (const svalue *sval) return sval->get_kind () == SK_REGION; } -template <> struct default_hash_traits<region_svalue::key_t> -: public member_function_hash_traits<region_svalue::key_t> -{ - static const bool empty_zero_p = false; -}; - namespace ana { /* Concrete subclass of svalue representing a specific constant value. @@ -323,24 +305,13 @@ public: : m_type (type), m_cst (cst) {} - hashval_t hash () const - { - inchash::hash hstate; - hstate.add_ptr (m_type); - hstate.add_ptr (m_cst); - return hstate.end (); - } - + bool + operator< (const key_t &other) const; bool operator== (const key_t &other) const { return (m_type == other.m_type && m_cst == other.m_cst); } - void mark_deleted () { m_type = reinterpret_cast<tree> (1); } - void mark_empty () { m_type = reinterpret_cast<tree> (2); } - bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } - bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } - tree m_type; tree m_cst; }; @@ -398,12 +369,6 @@ is_a_helper <const constant_svalue *>::test (const svalue *sval) return sval->get_kind () == SK_CONSTANT; } -template <> struct default_hash_traits<constant_svalue::key_t> -: public member_function_hash_traits<constant_svalue::key_t> -{ - static const bool empty_zero_p = false; -}; - namespace ana { /* Concrete subclass of svalue representing an unknowable value, the bottom @@ -473,24 +438,20 @@ public: : m_kind (kind), m_type (type) {} - hashval_t hash () const + bool + operator< (const key_t &other) const { - inchash::hash hstate; - hstate.add_int (static_cast<int> (m_kind)); - hstate.add_ptr (m_type); - return hstate.end (); + if (m_kind < other.m_kind) + return true; + return cmp_types (m_type, other.m_type) < 0; } - bool operator== (const key_t &other) const + bool + operator== (const key_t &other) const { return (m_kind == other.m_kind && m_type == other.m_type); } - void mark_deleted () { m_type = reinterpret_cast<tree> (1); } - void mark_empty () { m_type = reinterpret_cast<tree> (2); } - bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } - bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } - enum poison_kind m_kind; tree m_type; }; @@ -536,12 +497,6 @@ is_a_helper <const poisoned_svalue *>::test (const svalue *sval) return sval->get_kind () == SK_POISONED; } -template <> struct default_hash_traits<poisoned_svalue::key_t> -: public member_function_hash_traits<poisoned_svalue::key_t> -{ - static const bool empty_zero_p = false; -}; - namespace ana { /* A bundle of information recording a setjmp/sigsetjmp call, corresponding @@ -563,19 +518,12 @@ struct setjmp_record && m_setjmp_call == other.m_setjmp_call); } - void add_to_hash (inchash::hash *hstate) const - { - hstate->add_ptr (m_enode); - hstate->add_ptr (m_sedge); - hstate->add_ptr (m_setjmp_call); - } - static int cmp (const setjmp_record &rec1, const setjmp_record &rec2); const exploded_node *m_enode; const superedge *m_sedge; const gcall *m_setjmp_call; - // non-null, but we can't use a reference since we're putting these in a hash_map + // non-null, but we can't use a reference since we're putting these in a std::map }; /* Concrete subclass of svalue representing buffers for setjmp/sigsetjmp, @@ -592,24 +540,12 @@ public: : m_record (record), m_type (type) {} - hashval_t hash () const - { - inchash::hash hstate; - m_record.add_to_hash (&hstate); - hstate.add_ptr (m_type); - return hstate.end (); - } - + bool operator< (const key_t &other) const; bool operator== (const key_t &other) const { return (m_record == other.m_record && m_type == other.m_type); } - void mark_deleted () { m_type = reinterpret_cast<tree> (1); } - void mark_empty () { m_type = reinterpret_cast<tree> (2); } - bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } - bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } - setjmp_record m_record; tree m_type; }; @@ -652,12 +588,6 @@ is_a_helper <const setjmp_svalue *>::test (const svalue *sval) return sval->get_kind () == SK_SETJMP; } -template <> struct default_hash_traits<setjmp_svalue::key_t> -: public member_function_hash_traits<setjmp_svalue::key_t> -{ - static const bool empty_zero_p = false; -}; - namespace ana { /* Concrete subclass of svalue representing the initial value of a @@ -726,15 +656,7 @@ public: : m_type (type), m_op (op), m_arg (arg) {} - hashval_t hash () const - { - inchash::hash hstate; - hstate.add_ptr (m_type); - hstate.add_int (m_op); - hstate.add_ptr (m_arg); - return hstate.end (); - } - + bool operator< (const key_t &other) const; bool operator== (const key_t &other) const { return (m_type == other.m_type @@ -742,11 +664,6 @@ public: && m_arg == other.m_arg); } - void mark_deleted () { m_type = reinterpret_cast<tree> (1); } - void mark_empty () { m_type = reinterpret_cast<tree> (2); } - bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } - bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } - tree m_type; enum tree_code m_op; const svalue *m_arg; @@ -800,12 +717,6 @@ is_a_helper <const unaryop_svalue *>::test (const svalue *sval) return sval->get_kind () == SK_UNARYOP; } -template <> struct default_hash_traits<unaryop_svalue::key_t> -: public member_function_hash_traits<unaryop_svalue::key_t> -{ - static const bool empty_zero_p = false; -}; - namespace ana { /* Concrete subclass of svalue representing a binary operation of @@ -822,16 +733,7 @@ public: : m_type (type), m_op (op), m_arg0 (arg0), m_arg1 (arg1) {} - hashval_t hash () const - { - inchash::hash hstate; - hstate.add_ptr (m_type); - hstate.add_int (m_op); - hstate.add_ptr (m_arg0); - hstate.add_ptr (m_arg1); - return hstate.end (); - } - + bool operator< (const key_t &other) const; bool operator== (const key_t &other) const { return (m_type == other.m_type @@ -840,11 +742,6 @@ public: && m_arg1 == other.m_arg1); } - void mark_deleted () { m_type = reinterpret_cast<tree> (1); } - void mark_empty () { m_type = reinterpret_cast<tree> (2); } - bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } - bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } - tree m_type; enum tree_code m_op; const svalue *m_arg0; @@ -903,12 +800,6 @@ is_a_helper <const binop_svalue *>::test (const svalue *sval) return sval->get_kind () == SK_BINOP; } -template <> struct default_hash_traits<binop_svalue::key_t> -: public member_function_hash_traits<binop_svalue::key_t> -{ - static const bool empty_zero_p = false; -}; - namespace ana { /* Concrete subclass of svalue representing the result of accessing a subregion @@ -925,15 +816,7 @@ public: : m_type (type), m_parent_svalue (parent_svalue), m_subregion (subregion) {} - hashval_t hash () const - { - inchash::hash hstate; - hstate.add_ptr (m_type); - hstate.add_ptr (m_parent_svalue); - hstate.add_ptr (m_subregion); - return hstate.end (); - } - + bool operator< (const key_t &other) const; bool operator== (const key_t &other) const { return (m_type == other.m_type @@ -941,11 +824,6 @@ public: && m_subregion == other.m_subregion); } - void mark_deleted () { m_type = reinterpret_cast<tree> (1); } - void mark_empty () { m_type = reinterpret_cast<tree> (2); } - bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } - bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } - tree m_type; const svalue *m_parent_svalue; const region *m_subregion; @@ -989,12 +867,6 @@ is_a_helper <const sub_svalue *>::test (const svalue *sval) return sval->get_kind () == SK_SUB; } -template <> struct default_hash_traits<sub_svalue::key_t> -: public member_function_hash_traits<sub_svalue::key_t> -{ - static const bool empty_zero_p = false; -}; - namespace ana { /* Concrete subclass of svalue representing repeating an inner svalue @@ -1013,15 +885,7 @@ public: : m_type (type), m_outer_size (outer_size), m_inner_svalue (inner_svalue) {} - hashval_t hash () const - { - inchash::hash hstate; - hstate.add_ptr (m_type); - hstate.add_ptr (m_outer_size); - hstate.add_ptr (m_inner_svalue); - return hstate.end (); - } - + bool operator< (const key_t &other) const; bool operator== (const key_t &other) const { return (m_type == other.m_type @@ -1029,11 +893,6 @@ public: && m_inner_svalue == other.m_inner_svalue); } - void mark_deleted () { m_type = reinterpret_cast<tree> (1); } - void mark_empty () { m_type = reinterpret_cast<tree> (2); } - bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } - bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } - tree m_type; const svalue *m_outer_size; const svalue *m_inner_svalue; @@ -1084,12 +943,6 @@ is_a_helper <const repeated_svalue *>::test (const svalue *sval) return sval->get_kind () == SK_REPEATED; } -template <> struct default_hash_traits<repeated_svalue::key_t> -: public member_function_hash_traits<repeated_svalue::key_t> -{ - static const bool empty_zero_p = false; -}; - namespace ana { /* A range of bits/bytes within another svalue @@ -1109,14 +962,7 @@ public: : m_type (type), m_bits (bits), m_inner_svalue (inner_svalue) {} - hashval_t hash () const - { - inchash::hash hstate; - hstate.add_ptr (m_type); - hstate.add_ptr (m_inner_svalue); - return hstate.end (); - } - + bool operator< (const key_t &other) const; bool operator== (const key_t &other) const { return (m_type == other.m_type @@ -1124,11 +970,6 @@ public: && m_inner_svalue == other.m_inner_svalue); } - void mark_deleted () { m_type = reinterpret_cast<tree> (1); } - void mark_empty () { m_type = reinterpret_cast<tree> (2); } - bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } - bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } - tree m_type; bit_range m_bits; const svalue *m_inner_svalue; @@ -1180,12 +1021,6 @@ is_a_helper <const bits_within_svalue *>::test (const svalue *sval) return sval->get_kind () == SK_BITS_WITHIN; } -template <> struct default_hash_traits<bits_within_svalue::key_t> -: public member_function_hash_traits<bits_within_svalue::key_t> -{ - static const bool empty_zero_p = false; -}; - namespace ana { /* Concrete subclass of svalue: decorate another svalue, @@ -1289,10 +1124,10 @@ namespace ana { representing a possible fixed point in an iteration from the base to +ve infinity, or -ve infinity, and thus useful for representing a value within a loop. - We also need to capture the program_point at which the merger happens, + TODO: We also need to capture the program_point at which the merger happens, so that distinguish between different iterators, and thus handle nested loops. (currently we capture the function_point instead, for - simplicity of hashing). */ + redundant historical reasons). */ class widening_svalue : public svalue { @@ -1306,14 +1141,7 @@ public: m_base_sval (base_sval), m_iter_sval (iter_sval) {} - hashval_t hash () const - { - inchash::hash hstate; - hstate.add_ptr (m_base_sval); - hstate.add_ptr (m_iter_sval); - return hstate.end (); - } - + bool operator< (const key_t &other) const; bool operator== (const key_t &other) const { return (m_type == other.m_type @@ -1322,11 +1150,6 @@ public: && m_iter_sval == other.m_iter_sval); } - void mark_deleted () { m_type = reinterpret_cast<tree> (1); } - void mark_empty () { m_type = reinterpret_cast<tree> (2); } - bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } - bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } - tree m_type; const supernode *m_snode; const svalue *m_base_sval; @@ -1394,12 +1217,6 @@ is_a_helper <const widening_svalue *>::test (const svalue *sval) return sval->get_kind () == SK_WIDENING; } -template <> struct default_hash_traits<widening_svalue::key_t> -: public member_function_hash_traits<widening_svalue::key_t> -{ - static const bool empty_zero_p = false; -}; - namespace ana { /* Concrete subclass of svalue representing a mapping of bit-ranges @@ -1429,25 +1246,13 @@ public: : m_type (type), m_map_ptr (map_ptr) {} - hashval_t hash () const - { - inchash::hash hstate; - hstate.add_ptr (m_type); - //hstate.add_ptr (m_map_ptr); // TODO - return hstate.end (); - } - + bool operator< (const key_t &other) const; bool operator== (const key_t &other) const { return (m_type == other.m_type && *m_map_ptr == *other.m_map_ptr); } - void mark_deleted () { m_type = reinterpret_cast<tree> (1); } - void mark_empty () { m_type = reinterpret_cast<tree> (2); } - bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } - bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } - tree m_type; const concrete_binding_map *m_map_ptr; }; @@ -1503,12 +1308,6 @@ is_a_helper <const compound_svalue *>::test (const svalue *sval) return sval->get_kind () == SK_COMPOUND; } -template <> struct default_hash_traits<compound_svalue::key_t> -: public member_function_hash_traits<compound_svalue::key_t> -{ - static const bool empty_zero_p = false; -}; - namespace ana { /* A bundle of state for purging information from a program_state about @@ -1559,15 +1358,7 @@ public: : m_type (type), m_stmt (stmt), m_id_reg (id_reg), m_idx (idx) {} - hashval_t hash () const - { - inchash::hash hstate; - hstate.add_ptr (m_type); - hstate.add_ptr (m_stmt); - hstate.add_ptr (m_id_reg); - return hstate.end (); - } - + bool operator< (const key_t &other) const; bool operator== (const key_t &other) const { return (m_type == other.m_type @@ -1576,16 +1367,6 @@ public: && m_idx == other.m_idx); } - /* Use m_stmt to mark empty/deleted, as m_type can be NULL_TREE for - legitimate instances. */ - void mark_deleted () { m_stmt = reinterpret_cast<const gimple *> (1); } - void mark_empty () { m_stmt = nullptr; } - bool is_deleted () const - { - return m_stmt == reinterpret_cast<const gimple *> (1); - } - bool is_empty () const { return m_stmt == nullptr; } - tree m_type; const gimple *m_stmt; const region *m_id_reg; @@ -1636,12 +1417,6 @@ is_a_helper <const conjured_svalue *>::test (const svalue *sval) return sval->get_kind () == SK_CONJURED; } -template <> struct default_hash_traits<conjured_svalue::key_t> -: public member_function_hash_traits<conjured_svalue::key_t> -{ - static const bool empty_zero_p = true; -}; - namespace ana { /* An output from a deterministic asm stmt, where we want to identify a @@ -1673,17 +1448,7 @@ public: m_input_arr[i] = inputs[i]; } - hashval_t hash () const - { - inchash::hash hstate; - hstate.add_ptr (m_type); - /* We don't bother hashing m_asm_str. */ - hstate.add_int (m_output_idx); - for (unsigned i = 0; i < m_num_inputs; i++) - hstate.add_ptr (m_input_arr[i]); - return hstate.end (); - } - + bool operator< (const key_t &other) const; bool operator== (const key_t &other) const { if (!(m_type == other.m_type @@ -1697,16 +1462,6 @@ public: return true; } - /* Use m_asm_string to mark empty/deleted, as m_type can be NULL_TREE for - legitimate instances. */ - void mark_deleted () { m_asm_string = reinterpret_cast<const char *> (1); } - void mark_empty () { m_asm_string = nullptr; } - bool is_deleted () const - { - return m_asm_string == reinterpret_cast<const char *> (1); - } - bool is_empty () const { return m_asm_string == nullptr; } - tree m_type; const char *m_asm_string; unsigned m_output_idx; @@ -1782,12 +1537,6 @@ is_a_helper <const asm_output_svalue *>::test (const svalue *sval) return sval->get_kind () == SK_ASM_OUTPUT; } -template <> struct default_hash_traits<asm_output_svalue::key_t> -: public member_function_hash_traits<asm_output_svalue::key_t> -{ - static const bool empty_zero_p = true; -}; - namespace ana { /* The return value from a function with __attribute((const)) for given @@ -1818,16 +1567,7 @@ public: m_input_arr[i] = inputs[i]; } - hashval_t hash () const - { - inchash::hash hstate; - hstate.add_ptr (m_type); - hstate.add_ptr (m_fndecl); - for (unsigned i = 0; i < m_num_inputs; i++) - hstate.add_ptr (m_input_arr[i]); - return hstate.end (); - } - + bool operator< (const key_t &other) const; bool operator== (const key_t &other) const { if (!(m_type == other.m_type @@ -1840,15 +1580,6 @@ public: return true; } - /* Use m_fndecl to mark empty/deleted. */ - void mark_deleted () { m_fndecl = reinterpret_cast<tree> (1); } - void mark_empty () { m_fndecl = NULL_TREE; } - bool is_deleted () const - { - return m_fndecl == reinterpret_cast<tree> (1); - } - bool is_empty () const { return m_fndecl == NULL_TREE; } - tree m_type; tree m_fndecl; unsigned m_num_inputs; @@ -1913,10 +1644,4 @@ is_a_helper <const const_fn_result_svalue *>::test (const svalue *sval) return sval->get_kind () == SK_CONST_FN_RESULT; } -template <> struct default_hash_traits<const_fn_result_svalue::key_t> -: public member_function_hash_traits<const_fn_result_svalue::key_t> -{ - static const bool empty_zero_p = true; -}; - #endif /* GCC_ANALYZER_SVALUE_H */
