These patches address 3 separate things I discovered in working on
pr94454. As mentioned in the bug, we have disagreement between hash
value equality and key equality in the specialization table.
Once Iain got a reproducible build on gcc110, I came up with
pr94454-shim.diff. This (a) causes all specializations to only be
hashed by their template. and (b) adds a checking assert to the
argument comparator, to assert that if the arguments are equal, the
argument's hashes are the same. This triggered the problem, and a bunch
of other cases using the existing testsuites. We use comp_template_args
not only for the hash table, but for specialization ordering and the
like, hence the protection of that checking_assert for some special cases.
While we could keep the checking assert, the neutering of the hasher to
increase collisions really kills performance -- some of the libstdc++
tests timeout on a non-optimized checking build. I don't think that
should be enabled with checking. There doesn't seem to be an obvious
existing checking flag to add it to (type_checking is enabled on a
checking build).
The problem Eric hit in his case was that expression pack expansions
were comparing equal, (but hashing differently). Causing us to create
two, apparently equal, specializations that would sometimes collide.
I'm not sure why we had some randomness in reproducibility. I didn't
locate an uninitialized field, which was one of my hypotheses about the
cause. This is fixed by pr94454-pack.diff. cp_tree_operand_length says
a pack has 1 operand (for mangling), whereas it actually has 3, but only
two of which are significant for equality. We must special case that in
cp_tree_equal. That new code matches the hasher and the
type_pack_expansion case in structural_comp_types.
However, I also discovered 2 other problems.
The first is that the hasher was not skipping nodes that
template_args_equal would. Fixed by replacing the STRIP_NOPS invocation
by a bespoke loop. There's also a change to tpl-tpl-parm hashing, which
is part of the next problem ...
... we treat tpl-tpl-parms as types. They're not; bound-tpl-tpl-parms
are. We can get away with them being type-like. Unfortunately we give
the original level==orig_level case a canonical type, but the reduced
cases of level<orig_level get structural equality. That breaks the
hasher because we'll use TYPE_HASH (CANONICAL_TYPE ()) when we can.
There's a note in tsubst[TEMPLATE_TEMPLATE_PARM] about why the reduced
ones cannot have a canonical type. (I didn't feel like questioning that
assertion at this point.) So that's the other part of the hash fn change.
Finally, should tpl-tpl-parms ever have a canonical type? I think we
can get away with that, because the comparison machinery will do
structural comparison if one of the nodes requires structural
comparison. It seems somewhat skewed though, and pr94454-ttp.diff stops
tpl-tpl-parms from having canonical types.
In summary:
pr94454-shim.diff - not apply, keep with bug report
pr94454-arghash.diff - apply, fixes hasher
pr94454-pack.diff - apply, fixes cp_tree_equal
pr94454-ttp.diff - maybe?
Eric's testcase is too huge for the testsuite, and I couldn't get it to
trigger with arghash.diff and ttp.diff applied bug pack.diff not. I did
get several fails in the g++ and libstdc++ testsuites with shim.diff
applied, and none of the fixes.
nathan
--
Nathan Sidwell
2020-04-16 Nathan Sidwell <nat...@acm.org>
PR 94454 - specialization hash inconsistencies
* pt.c (iterative_hash_template_arg): Strip nodes as
template_args_equal does.
[ARGUMENT_PACK_SELECT, TREE_VEC, CONSTRUCTOR]: Refactor.
[node_class:TEMPLATE_TEMPLATE_PARM]: Hash by level & index.
[node_class:default]: Refactor.
diff --git i/gcc/cp/pt.c w/gcc/cp/pt.c
index 0a8ec3198d2..5bc94a85129 100644
--- i/gcc/cp/pt.c
+++ w/gcc/cp/pt.c
@@ -195,6 +195,7 @@ static void set_current_access_from_decl (tree);
static enum template_base_result get_template_base (tree, tree, tree, tree,
bool , tree *);
static tree try_class_unification (tree, tree, tree, tree, bool);
+static bool class_nttp_const_wrapper_p (tree t);
static int coerce_template_template_parms (tree, tree, tsubst_flags_t,
tree, tree);
static bool template_template_parm_bindings_ok_p (tree, tree);
@@ -1737,31 +1741,32 @@ spec_hasher::hash (spec_entry *e)
}
/* Recursively calculate a hash value for a template argument ARG, for use
- in the hash tables of template specializations. */
+ in the hash tables of template specializations. We must be
+ careful to (at least) skip the same entities template_args_equal
+ does. */
hashval_t
iterative_hash_template_arg (tree arg, hashval_t val)
{
- unsigned HOST_WIDE_INT i;
- enum tree_code code;
- char tclass;
-
if (arg == NULL_TREE)
return iterative_hash_object (arg, val);
if (!TYPE_P (arg))
- STRIP_NOPS (arg);
-
- if (TREE_CODE (arg) == ARGUMENT_PACK_SELECT)
- gcc_unreachable ();
+ /* Strip nop-like things, but not the same as STRIP_NOPS. */
+ while (CONVERT_EXPR_P (arg)
+ || TREE_CODE (arg) == NON_LVALUE_EXPR
+ || class_nttp_const_wrapper_p (arg))
+ arg = TREE_OPERAND (arg, 0);
- code = TREE_CODE (arg);
- tclass = TREE_CODE_CLASS (code);
+ enum tree_code code = TREE_CODE (arg);
val = iterative_hash_object (code, val);
switch (code)
{
+ case ARGUMENT_PACK_SELECT:
+ gcc_unreachable ();
+
case ERROR_MARK:
return val;
@@ -1769,12 +1774,9 @@ iterative_hash_template_arg (tree arg, hashval_t val)
return iterative_hash_object (IDENTIFIER_HASH_VALUE (arg), val);
case TREE_VEC:
- {
- int i, len = TREE_VEC_LENGTH (arg);
- for (i = 0; i < len; ++i)
- val = iterative_hash_template_arg (TREE_VEC_ELT (arg, i), val);
- return val;
- }
+ for (int i = 0, len = TREE_VEC_LENGTH (arg); i < len; ++i)
+ val = iterative_hash_template_arg (TREE_VEC_ELT (arg, i), val);
+ return val;
case TYPE_PACK_EXPANSION:
case EXPR_PACK_EXPANSION:
@@ -1798,6 +1800,7 @@ iterative_hash_template_arg (tree arg, hashval_t val)
case CONSTRUCTOR:
{
tree field, value;
+ unsigned i;
iterative_hash_template_arg (TREE_TYPE (arg), val);
FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (arg), i, field, value)
{
@@ -1884,6 +1887,7 @@ iterative_hash_template_arg (tree arg, hashval_t val)
break;
}
+ char tclass = TREE_CODE_CLASS (code);
switch (tclass)
{
case tcc_type:
@@ -1899,12 +1903,30 @@ iterative_hash_template_arg (tree arg, hashval_t val)
tree ti = TYPE_ALIAS_TEMPLATE_INFO (ats);
return hash_tmpl_and_args (TI_TEMPLATE (ti), TI_ARGS (ti));
}
- if (TYPE_CANONICAL (arg))
- return iterative_hash_object (TYPE_HASH (TYPE_CANONICAL (arg)),
- val);
- else if (TREE_CODE (arg) == DECLTYPE_TYPE)
- return iterative_hash_template_arg (DECLTYPE_TYPE_EXPR (arg), val);
- /* Otherwise just compare the types during lookup. */
+
+ switch (TREE_CODE (arg))
+ {
+ case TEMPLATE_TEMPLATE_PARM:
+ {
+ tree tpi = TEMPLATE_TYPE_PARM_INDEX (arg);
+
+ /* Do not recurse with TPI directly, as that is unbounded
+ recursion. */
+ val = iterative_hash_object (TEMPLATE_PARM_LEVEL (tpi), val);
+ val = iterative_hash_object (TEMPLATE_PARM_IDX (tpi), val);
+ }
+ break;
+
+ case DECLTYPE_TYPE:
+ val = iterative_hash_template_arg (DECLTYPE_TYPE_EXPR (arg), val);
+ break;
+
+ default:
+ if (tree canonical = TYPE_CANONICAL (arg))
+ val = iterative_hash_object (TYPE_HASH (canonical), val);
+ break;
+ }
+
return val;
case tcc_declaration:
@@ -1913,13 +1935,11 @@ iterative_hash_template_arg (tree arg, hashval_t val)
default:
gcc_assert (IS_EXPR_CODE_CLASS (tclass));
- {
- unsigned n = cp_tree_operand_length (arg);
- for (i = 0; i < n; ++i)
- val = iterative_hash_template_arg (TREE_OPERAND (arg, i), val);
- return val;
- }
+ for (int i = 0, n = cp_tree_operand_length (arg); i < n; ++i)
+ val = iterative_hash_template_arg (TREE_OPERAND (arg, i), val);
+ return val;
}
+
gcc_unreachable ();
return 0;
}
2020-04-16 Nathan Sidwell <nat...@acm.org>
PR 94454 - specialization hash inconsistencies
* tree.c (cp_tree_equal): [TEMPLATE_ID_EXPR, default] Refactor.
[EXPR_PACK_EXPANSION]: Add.
diff --git i/gcc/cp/tree.c w/gcc/cp/tree.c
index 1d311b0fe61..0cb5da1b841 100644
--- i/gcc/cp/tree.c
+++ w/gcc/cp/tree.c
@@ -3767,8 +3767,11 @@ cp_tree_equal (tree t1, tree t2)
TREE_TYPE (TEMPLATE_PARM_DECL (t2))));
case TEMPLATE_ID_EXPR:
- return (cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0))
- && cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1)));
+ if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
+ return false;
+ if (!comp_template_args (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1)))
+ return false;
+ return true;
case CONSTRAINT_INFO:
return cp_tree_equal (CI_ASSOCIATED_CONSTRAINTS (t1),
@@ -3898,6 +3901,15 @@ cp_tree_equal (tree t1, tree t2)
return true;
}
+ case EXPR_PACK_EXPANSION:
+ if (!cp_tree_equal (PACK_EXPANSION_PATTERN (t1),
+ PACK_EXPANSION_PATTERN (t2)))
+ return false;
+ if (!comp_template_args (PACK_EXPANSION_EXTRA_ARGS (t1),
+ PACK_EXPANSION_EXTRA_ARGS (t2)))
+ return false;
+ return true;
+
default:
break;
}
@@ -3912,14 +3924,12 @@ cp_tree_equal (tree t1, tree t2)
case tcc_reference:
case tcc_statement:
{
- int i, n;
-
- n = cp_tree_operand_length (t1);
+ int n = cp_tree_operand_length (t1);
if (TREE_CODE_CLASS (code1) == tcc_vl_exp
&& n != TREE_OPERAND_LENGTH (t2))
return false;
- for (i = 0; i < n; ++i)
+ for (int i = 0; i < n; ++i)
if (!cp_tree_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i)))
return false;
@@ -3928,9 +3938,11 @@ cp_tree_equal (tree t1, tree t2)
case tcc_type:
return same_type_p (t1, t2);
+
default:
gcc_unreachable ();
}
+
/* We can get here with --disable-checking. */
return false;
}
diff --git i/gcc/cp/pt.c w/gcc/cp/pt.c
index 0a8ec3198d2..5bc94a85129 100644
--- i/gcc/cp/pt.c
+++ w/gcc/cp/pt.c
@@ -1724,7 +1725,10 @@ static hashval_t
hash_tmpl_and_args (tree tmpl, tree args)
{
hashval_t val = iterative_hash_object (DECL_UID (tmpl), 0);
- return iterative_hash_template_arg (args, val);
+ if (false) /* Disable to debug the hash table. See the checker in
+ comp_template_args. */
+ val = iterative_hash_template_arg (args, val);
+ return val;
}
/* Returns a hash for a spec_entry node based on the TMPL and ARGS members,
@@ -9106,6 +9132,14 @@ comp_template_args (tree oldargs, tree newargs,
*newarg_ptr = nt;
return 0;
}
+
+ if (!partial_order
+ && ot != any_targ_node
+ && (!(ot && TREE_CODE (ot) == TYPENAME_TYPE)
+ || TREE_CODE (nt) == TYPENAME_TYPE))
+ /* They compared equal, better hash that way too. */
+ gcc_checking_assert (iterative_hash_template_arg (ot, 0)
+ == iterative_hash_template_arg (nt, 0));
}
return 1;
}
2020-04-16 Nathan Sidwell <nat...@acm.org>
PR 94454 - tpl-tpl-parms are not canonicalized types
* pt.c (canonical_type_parameter): Assert not a tpl-tpl-parm.
(process_template_parm): tpl-tpl-parms are structural.
(rewrite_template_parm): Propagate structuralness.
diff --git i/gcc/cp/pt.c w/gcc/cp/pt.c
index 0a8ec3198d2..5bc94a85129 100644
--- i/gcc/cp/pt.c
+++ w/gcc/cp/pt.c
@@ -4382,6 +4402,9 @@ canonical_type_parameter (tree type)
{
tree list;
int idx = TEMPLATE_TYPE_IDX (type);
+
+ gcc_assert (TREE_CODE (type) != TEMPLATE_TEMPLATE_PARM);
+
if (!canonical_template_parms)
vec_alloc (canonical_template_parms, idx + 1);
@@ -4564,7 +4587,10 @@ process_template_parm (tree list, location_t parm_loc, tree parm,
processing_template_decl,
decl, TREE_TYPE (parm));
TEMPLATE_TYPE_PARAMETER_PACK (t) = is_parameter_pack;
- TYPE_CANONICAL (t) = canonical_type_parameter (t);
+ if (TREE_CODE (t) == TEMPLATE_TEMPLATE_PARM)
+ SET_TYPE_STRUCTURAL_EQUALITY (t);
+ else
+ TYPE_CANONICAL (t) = canonical_type_parameter (t);
}
DECL_ARTIFICIAL (decl) = 1;
SET_DECL_TEMPLATE_PARM_P (decl);
@@ -28005,7 +28039,10 @@ rewrite_template_parm (tree olddecl, unsigned index, unsigned level,
TEMPLATE_PARM_PARAMETER_PACK (newidx)
= TEMPLATE_PARM_PARAMETER_PACK (oldidx);
TYPE_STUB_DECL (newtype) = TYPE_NAME (newtype) = newdecl;
- TYPE_CANONICAL (newtype) = canonical_type_parameter (newtype);
+ if (TYPE_STRUCTURAL_EQUALITY_P (TREE_TYPE (olddecl)))
+ SET_TYPE_STRUCTURAL_EQUALITY (newtype);
+ else
+ TYPE_CANONICAL (newtype) = canonical_type_parameter (newtype);
if (TREE_CODE (olddecl) == TEMPLATE_DECL)
{
