[PR94454] specialization hashtable inconsistencies
Nathan Sidwell
nathan@acm.org
Thu Apr 16 15:47:47 GMT 2020
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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pr94454-arghash.diff
Type: text/x-patch
Size: 4748 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20200416/3953067b/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pr94454-pack.diff
Type: text/x-patch
Size: 1976 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20200416/3953067b/attachment-0001.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pr94454-shim.diff
Type: text/x-patch
Size: 1009 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20200416/3953067b/attachment-0002.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pr94454-ttp.diff
Type: text/x-patch
Size: 1710 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20200416/3953067b/attachment-0003.bin>
More information about the Gcc-patches
mailing list