Hi.
As slightly discussed here:
https://gcc.gnu.org/ml/gcc-patches/2018-10/msg01674.html I fixed
a situation where an equal operator of a hash table returns true, while
corresponding hash
value of a pair of elements is different. That's inconsistent and can probably
cause issues
in different areas of compiler.
I wrote a simple patch that verifies for a newly added element into a hash
table that there's
no other equal element with a different hash. That's O(n) for each insert, so
that it's only
enabled with -fchecking=3. Apart from that the way how it's enable is a bit
cumbersome, but
that's caused by usage of hash-table also in generated files.
Anyway, there are first places where I see violation of the sanity check:
1) cselib_lookup_1:
$ cat ice.c
a() { b(); }
$ /dev/shm/objdir/gcc/xgcc -B/dev/shm/objdir/gcc/ ice.c -g -c -fchecking=3 -O
hash table checking failed: equal operator returns true for a pair of values
with a different hash valueduring RTL pass: vartrack
ice.c:1:1: internal compiler error: in find_slot_with_hash, at hash-table.h:905
1 | a() { b(); }
| ^
0x9680b5 hash_table<cselib_hasher,
xcallocator>::find_slot_with_hash(cselib_hasher::key* const&, unsigned int,
insert_option)
/home/marxin/Programming/gcc/gcc/hash-table.h:905
0x962518 cselib_find_slot
/home/marxin/Programming/gcc/gcc/cselib.c:584
0x9625d4 cselib_lookup_1
/home/marxin/Programming/gcc/gcc/cselib.c:2097
0x9625d4 cselib_lookup(rtx_def*, machine_mode, int, machine_mode)
/home/marxin/Programming/gcc/gcc/cselib.c:2141
0x965ee7 cselib_record_sets
/home/marxin/Programming/gcc/gcc/cselib.c:2593
0x9670a9 cselib_process_insn(rtx_insn*)
/home/marxin/Programming/gcc/gcc/cselib.c:2790
0x1036b73 vt_initialize
/home/marxin/Programming/gcc/gcc/var-tracking.c:10231
0x103b98a variable_tracking_main_1
/home/marxin/Programming/gcc/gcc/var-tracking.c:10460
0x103b98a variable_tracking_main()
/home/marxin/Programming/gcc/gcc/var-tracking.c:10513
2) gfc_find_module
$ ./xgcc -B.
/home/marxin/Programming/gcc/gcc/testsuite/gfortran.dg/coarray/alloc_comp_2.f90
-fcoarray=single -fchecking=3
hash table checking failed: equal operator returns true for a pair of values
with a different hash valuef951: internal compiler error: in
find_slot_with_hash, at hash-table.h:905
0x8e5e86 hash_table<module_hasher, xcallocator>::find_slot_with_hash(char
const* const&, unsigned int, insert_option)
/home/marxin/Programming/gcc/gcc/hash-table.h:905
0x8e2c2c gfc_find_module(char const*)
/home/marxin/Programming/gcc/gcc/fortran/trans-decl.c:4865
0x8e4f42 gfc_generate_module_vars(gfc_namespace*)
/home/marxin/Programming/gcc/gcc/fortran/trans-decl.c:5475
0x8b8d7e gfc_generate_module_code(gfc_namespace*)
/home/marxin/Programming/gcc/gcc/fortran/trans.c:2190
0x868427 translate_all_program_units
/home/marxin/Programming/gcc/gcc/fortran/parse.c:6112
0x868427 gfc_parse_file()
/home/marxin/Programming/gcc/gcc/fortran/parse.c:6328
0x8b19cb gfc_be_parse_file
/home/marxin/Programming/gcc/gcc/fortran/f95-lang.c:204
3) lookup_template_class_1
$ ./xg++ -B. /home/marxin/Programming/gcc/gcc/testsuite/g++.dg/template/ttp23.C
-c -fchecking=3
hash table checking failed: equal operator returns true for a pair of values
with a different hash
value/home/marxin/Programming/gcc/gcc/testsuite/g++.dg/template/ttp23.C: In
instantiation of ‘struct B<A>’:
/home/marxin/Programming/gcc/gcc/testsuite/g++.dg/template/ttp23.C:15:8:
required from here
/home/marxin/Programming/gcc/gcc/testsuite/g++.dg/template/ttp23.C:8:17:
internal compiler error: in find_slot_with_hash, at hash-table.h:905
8 | friend bool foo (const B<Q>& a);
| ^~~
0xa265a4 hash_table<spec_hasher, xcallocator>::find_slot_with_hash(spec_entry*
const&, unsigned int, insert_option)
/home/marxin/Programming/gcc/gcc/hash-table.h:905
0xa042ce lookup_template_class_1
/home/marxin/Programming/gcc/gcc/cp/pt.c:9629
0xa042ce lookup_template_class(tree_node*, tree_node*, tree_node*, tree_node*,
int, int)
/home/marxin/Programming/gcc/gcc/cp/pt.c:9674
0xa03670 tsubst_aggr_type
/home/marxin/Programming/gcc/gcc/cp/pt.c:12679
0x9fefcd tsubst(tree_node*, tree_node*, int, tree_node*)
/home/marxin/Programming/gcc/gcc/cp/pt.c:14294
0x9fe1a9 tsubst(tree_node*, tree_node*, int, tree_node*)
/home/marxin/Programming/gcc/gcc/cp/pt.c:14285
0xa0d8bd tsubst_arg_types
/home/marxin/Programming/gcc/gcc/cp/pt.c:13891
0xa0dc24 tsubst_function_type
/home/marxin/Programming/gcc/gcc/cp/pt.c:14032
0x9fe790 tsubst(tree_node*, tree_node*, int, tree_node*)
/home/marxin/Programming/gcc/gcc/cp/pt.c:14769
0x9f2c7c tsubst_function_decl
/home/marxin/Programming/gcc/gcc/cp/pt.c:12921
0xa02d27 tsubst_template_decl
/home/marxin/Programming/gcc/gcc/cp/pt.c:13214
0x9f4416 tsubst_decl
/home/marxin/Programming/gcc/gcc/cp/pt.c:13316
0x9ff0ca tsubst(tree_node*, tree_node*, int, tree_node*)
/home/marxin/Programming/gcc/gcc/cp/pt.c:14212
0xa1dfd0 tsubst_friend_function
/home/marxin/Programming/gcc/gcc/cp/pt.c:10310
0xa1dfd0 instantiate_class_template_1
/home/marxin/Programming/gcc/gcc/cp/pt.c:11359
0xa1dfd0 instantiate_class_template(tree_node*)
/home/marxin/Programming/gcc/gcc/cp/pt.c:11424
0xa66b22 complete_type(tree_node*)
/home/marxin/Programming/gcc/gcc/cp/typeck.c:138
0x9023c7 start_decl_1(tree_node*, bool)
/home/marxin/Programming/gcc/gcc/cp/decl.c:5278
0x92a15f start_decl(cp_declarator const*, cp_decl_specifier_seq*, int,
tree_node*, tree_node*, tree_node**)
/home/marxin/Programming/gcc/gcc/cp/decl.c:5241
0x9c1944 cp_parser_init_declarator
/home/marxin/Programming/gcc/gcc/cp/parser.c:19750
4) register_specialization
$ ./xg++ -B.
/home/marxin/Programming/gcc/gcc/testsuite/g++.dg/cpp0x/udlit-template.C
-I/dev/shm/objdir/x86_64-pc-linux-gnu/libstdc++-v3/include/x86_64-pc-linux-gnu
-I/dev/shm/objdir/x86_64-pc-linux-gnu/libstdc++-v3/include
-I/home/marxin/Programming/gcc/libstdc++-v3/libsupc++
-I/home/marxin/Programming/gcc/libstdc++-v3/include/ba -c -fchecking=3
hash table checking failed: equal operator returns true for a pair of values
with a different hash
value/home/marxin/Programming/gcc/gcc/testsuite/g++.dg/cpp0x/udlit-template.C:13:21:
internal compiler error: in find_slot_with_hash, at hash-table.h:905
13 | operator"" _abc<>()
| ^
0xa265a4 hash_table<spec_hasher, xcallocator>::find_slot_with_hash(spec_entry*
const&, unsigned int, insert_option)
/home/marxin/Programming/gcc/gcc/hash-table.h:905
0x9e35e6 register_specialization
/home/marxin/Programming/gcc/gcc/cp/pt.c:1534
0xa22ac3 check_explicit_specialization(tree_node*, tree_node*, int, int,
tree_node*)
/home/marxin/Programming/gcc/gcc/cp/pt.c:3243
0x91552d grokfndecl
/home/marxin/Programming/gcc/gcc/cp/decl.c:9106
0x9274bd grokdeclarator(cp_declarator const*, cp_decl_specifier_seq*,
decl_context, int, tree_node**)
/home/marxin/Programming/gcc/gcc/cp/decl.c:12607
0x92a9c6 start_function(cp_decl_specifier_seq*, cp_declarator const*,
tree_node*)
/home/marxin/Programming/gcc/gcc/cp/decl.c:15470
0x9c14a9 cp_parser_function_definition_from_specifiers_and_declarator
/home/marxin/Programming/gcc/gcc/cp/parser.c:26853
0x9c14a9 cp_parser_init_declarator
/home/marxin/Programming/gcc/gcc/cp/parser.c:19654
0x9c8ebd cp_parser_single_declaration
/home/marxin/Programming/gcc/gcc/cp/parser.c:27437
0x9c9b11 cp_parser_explicit_specialization
/home/marxin/Programming/gcc/gcc/cp/parser.c:16802
0x9cf30e cp_parser_declaration
/home/marxin/Programming/gcc/gcc/cp/parser.c:12822
0x9cf94d cp_parser_translation_unit
/home/marxin/Programming/gcc/gcc/cp/parser.c:4631
0x9cf94d c_parse_file()
/home/marxin/Programming/gcc/gcc/cp/parser.c:39108
0xadde4a c_common_parse_file()
/home/marxin/Programming/gcc/gcc/c-family/c-opts.c:1150
5) the case fixed in PR86158:
$ /home/marxin/Programming/gcc/gcc/testsuite/gcc.dg/ipa/iinline-2.c:37:1:
internal compiler error: in find_slot_with_hash, at hash-table.h:905
0xba10f6 hash_table<ipa_vr_ggc_hash_traits,
xcallocator>::find_slot_with_hash(value_range* const&, unsigned int,
insert_option)
/home/marxin/Programming/gcc/gcc/hash-table.h:905
0xb9e02c hash_table<ipa_vr_ggc_hash_traits,
xcallocator>::find_slot(value_range* const&, insert_option)
/home/marxin/Programming/gcc/gcc/hash-table.h:418
0xb8ea21 ipa_get_value_range
/home/marxin/Programming/gcc/gcc/ipa-prop.c:1776
0xb8eab6 ipa_get_value_range
/home/marxin/Programming/gcc/gcc/ipa-prop.c:1795
0xb8eae5 ipa_set_jfunc_vr
/home/marxin/Programming/gcc/gcc/ipa-prop.c:1806
0xb8ef49 ipa_compute_jump_functions_for_edge
/home/marxin/Programming/gcc/gcc/ipa-prop.c:1875
0xb8fb53 ipa_compute_jump_functions_for_bb
/home/marxin/Programming/gcc/gcc/ipa-prop.c:2017
0xb912ab analysis_dom_walker::before_dom_children(basic_block_def*)
/home/marxin/Programming/gcc/gcc/ipa-prop.c:2535
0x158f997 dom_walker::walk(basic_block_def*)
/home/marxin/Programming/gcc/gcc/domwalk.c:353
0xb915b0 ipa_analyze_node(cgraph_node*)
/home/marxin/Programming/gcc/gcc/ipa-prop.c:2605
0xb776bf inline_indirect_intraprocedural_analysis
/home/marxin/Programming/gcc/gcc/ipa-fnsummary.c:3125
0xb776bf inline_analyze_function(cgraph_node*)
/home/marxin/Programming/gcc/gcc/ipa-fnsummary.c:3145
0xb77866 ipa_fn_summary_generate
/home/marxin/Programming/gcc/gcc/ipa-fnsummary.c:3189
0xca1751 execute_ipa_summary_passes(ipa_opt_pass_d*)
/home/marxin/Programming/gcc/gcc/passes.c:2131
0x96907a ipa_passes
/home/marxin/Programming/gcc/gcc/cgraphunit.c:2505
0x96907a symbol_table::compile()
/home/marxin/Programming/gcc/gcc/cgraphunit.c:2616
0x96b055 symbol_table::finalize_compilation_unit()
/home/marxin/Programming/gcc/gcc/cgraphunit.c:2861
My question is whether we want to have in GCC 9 time frame or should I wait
with that?
Does it worth implementing?
Thanks,
Martin
---
gcc/hash-table.c | 2 ++
gcc/hash-table.h | 25 ++++++++++++++++++++++++-
gcc/toplev.c | 3 +++
3 files changed, 29 insertions(+), 1 deletion(-)
diff --git a/gcc/hash-table.c b/gcc/hash-table.c
index bff9644ae81..d396a368171 100644
--- a/gcc/hash-table.c
+++ b/gcc/hash-table.c
@@ -121,3 +121,5 @@ void dump_hash_table_loc_statistics (void)
hash_table_usage ().dump (origin);
}
}
+
+bool hash_table_verify_p = false;
diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index bd83345c7b8..2d740b42535 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -240,6 +240,10 @@ along with GCC; see the file COPYING3. If not see
#include "hash-traits.h"
#include "hash-map-traits.h"
+#ifndef GENERATOR_FILE
+extern bool hash_table_verify_p;
+#endif
+
template<typename, typename, typename> class hash_map;
template<typename, typename> class hash_set;
@@ -883,12 +887,31 @@ hash_table<Descriptor, Allocator>
expand ();
m_searches++;
+ size_t size = m_size;
+
+#ifndef GENERATOR_FILE
+ if (hash_table_verify_p)
+ if (insert == INSERT)
+ for (size_t i = 0; i < size; i++)
+ {
+ value_type *entry = &m_entries[i];
+ if (!is_empty (*entry) && !is_deleted (*entry)
+ && Descriptor::equal (*entry, comparable)
+ && hash != Descriptor::hash (*entry))
+ {
+ fprintf (stderr, "hash table checking failed: "
+ "equal operator returns true for a pair "
+ "of values with a different hash value");
+ gcc_unreachable ();
+ }
+ }
+#endif
+// TODO: enable it also for generated files: there are failures!
value_type *first_deleted_slot = NULL;
hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
value_type *entry = &m_entries[index];
- size_t size = m_size;
if (is_empty (*entry))
goto empty_entry;
else if (is_deleted (*entry))
diff --git a/gcc/toplev.c b/gcc/toplev.c
index d7ea11abf53..4cd3aafa2e8 100644
--- a/gcc/toplev.c
+++ b/gcc/toplev.c
@@ -2289,6 +2289,9 @@ toplev::main (int argc, char **argv)
handle_common_deferred_options ();
+ if (flag_checking > 2)
+ hash_table_verify_p = true;
+
init_local_tick ();
initialize_plugins ();
