* [PATCH] c++: Reuse identical ATOMIC_CONSTRs during normalization @ 2020-11-03 20:43 Patrick Palka 2020-11-05 20:45 ` Jason Merrill 0 siblings, 1 reply; 5+ messages in thread From: Patrick Palka @ 2020-11-03 20:43 UTC (permalink / raw) To: gcc-patches Profiling revealed that sat_hasher::equal accounts for nearly 40% of compile time in some cmcstl2 tests. This patch eliminates this bottleneck by caching the ATOMIC_CONSTRs returned by normalize_atom. This in turn allows us to replace the expensive atomic_constraints_identical_p check in sat_hasher::equal with cheap pointer equality, with no loss in cache hit rate. With this patch, compile time for the cmcstl2 test test/algorithm/set_symmetric_difference4.cpp drops from 19s to 11s with an --enable-checking=release compiler. Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for trunk? gcc/cp/ChangeLog: * constraint.cc (struct atom_hasher): New descriptor class for a hash_table. Use it to define ... (atom_cache): ... this. (normalize_atom): Use it to cache ATOMIC_CONSTRs when not generating diagnostics. (sat_hasher::hash): Use htab_hash_pointer instead of hash_atomic_constraint. (sat_hasher::equal): Test for pointer equality instead of atomic_constraints_identical_p. --- gcc/cp/constraint.cc | 37 ++++++++++++++++++++++++++++++++++--- 1 file changed, 34 insertions(+), 3 deletions(-) diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc index b6f6f0d02a5..ce720c641e8 100644 --- a/gcc/cp/constraint.cc +++ b/gcc/cp/constraint.cc @@ -710,6 +710,25 @@ normalize_concept_check (tree check, tree args, norm_info info) return normalize_expression (def, subst, info); } +/* Hash functions for ATOMIC_CONSTRs. */ + +struct atom_hasher : default_hash_traits<tree> +{ + static hashval_t hash (tree atom) + { + return hash_atomic_constraint (atom); + } + + static bool equal (tree atom1, tree atom2) + { + return atomic_constraints_identical_p (atom1, atom2); + } +}; + +/* Used by normalize_atom to cache ATOMIC_CONSTRs. */ + +static GTY((deletable)) hash_table<atom_hasher> *atom_cache; + /* The normal form of an atom depends on the expression. The normal form of a function call to a function concept is a check constraint for that concept. The normal form of a reference to a variable @@ -729,7 +748,19 @@ normalize_atom (tree t, tree args, norm_info info) /* Build a new info object for the atom. */ tree ci = build_tree_list (t, info.context); - return build1 (ATOMIC_CONSTR, ci, map); + tree atom = build1 (ATOMIC_CONSTR, ci, map); + if (!info.generate_diagnostics ()) + { + /* Cache the ATOMIC_CONSTRs that we return, so that sat_hasher::equal + later can quickly compare two atoms using just pointer equality. */ + if (!atom_cache) + atom_cache = hash_table<atom_hasher>::create_ggc (31); + tree *slot = atom_cache->find_slot (atom, INSERT); + if (*slot) + return *slot; + *slot = atom; + } + return atom; } /* Returns the normal form of an expression. */ @@ -2284,13 +2315,13 @@ struct sat_hasher : ggc_ptr_hash<sat_entry> { static hashval_t hash (sat_entry *e) { - hashval_t value = hash_atomic_constraint (e->constr); + hashval_t value = htab_hash_pointer (e->constr); return iterative_hash_template_arg (e->args, value); } static bool equal (sat_entry *e1, sat_entry *e2) { - if (!atomic_constraints_identical_p (e1->constr, e2->constr)) + if (e1->constr != e2->constr) return false; return template_args_equal (e1->args, e2->args); } -- 2.29.2.154.g7f7ebe054a ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] c++: Reuse identical ATOMIC_CONSTRs during normalization 2020-11-03 20:43 [PATCH] c++: Reuse identical ATOMIC_CONSTRs during normalization Patrick Palka @ 2020-11-05 20:45 ` Jason Merrill 2020-11-05 23:00 ` Patrick Palka 0 siblings, 1 reply; 5+ messages in thread From: Jason Merrill @ 2020-11-05 20:45 UTC (permalink / raw) To: Patrick Palka, gcc-patches On 11/3/20 3:43 PM, Patrick Palka wrote: > Profiling revealed that sat_hasher::equal accounts for nearly 40% of > compile time in some cmcstl2 tests. > > This patch eliminates this bottleneck by caching the ATOMIC_CONSTRs > returned by normalize_atom. This in turn allows us to replace the > expensive atomic_constraints_identical_p check in sat_hasher::equal > with cheap pointer equality, with no loss in cache hit rate. > > With this patch, compile time for the cmcstl2 test > test/algorithm/set_symmetric_difference4.cpp drops from 19s to 11s with > an --enable-checking=release compiler. > > Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for > trunk? > > gcc/cp/ChangeLog: > > * constraint.cc (struct atom_hasher): New descriptor class for a > hash_table. Use it to define ... > (atom_cache): ... this. > (normalize_atom): Use it to cache ATOMIC_CONSTRs when not > generating diagnostics. > (sat_hasher::hash): Use htab_hash_pointer instead of > hash_atomic_constraint. > (sat_hasher::equal): Test for pointer equality instead of > atomic_constraints_identical_p. > --- > gcc/cp/constraint.cc | 37 ++++++++++++++++++++++++++++++++++--- > 1 file changed, 34 insertions(+), 3 deletions(-) > > diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc > index b6f6f0d02a5..ce720c641e8 100644 > --- a/gcc/cp/constraint.cc > +++ b/gcc/cp/constraint.cc > @@ -710,6 +710,25 @@ normalize_concept_check (tree check, tree args, norm_info info) > return normalize_expression (def, subst, info); > } > > +/* Hash functions for ATOMIC_CONSTRs. */ > + > +struct atom_hasher : default_hash_traits<tree> > +{ > + static hashval_t hash (tree atom) > + { > + return hash_atomic_constraint (atom); > + } > + > + static bool equal (tree atom1, tree atom2) > + { > + return atomic_constraints_identical_p (atom1, atom2); > + } > +}; This is the same as constraint_hash in logic.cc; either they should be combined, or (probably) the hash table in logic.cc should be changed to also take advantage of pointer equivalence. > +/* Used by normalize_atom to cache ATOMIC_CONSTRs. */ > + > +static GTY((deletable)) hash_table<atom_hasher> *atom_cache; If we're relying on pointer identity, this can't be deletable; if GC discards it, later normalization will generate a new equivalent ATOMIC_CONSTR, breaking the uniqueness assumption. > /* The normal form of an atom depends on the expression. The normal > form of a function call to a function concept is a check constraint > for that concept. The normal form of a reference to a variable > @@ -729,7 +748,19 @@ normalize_atom (tree t, tree args, norm_info info) > /* Build a new info object for the atom. */ > tree ci = build_tree_list (t, info.context); > > - return build1 (ATOMIC_CONSTR, ci, map); > + tree atom = build1 (ATOMIC_CONSTR, ci, map); > + if (!info.generate_diagnostics ()) > + { > + /* Cache the ATOMIC_CONSTRs that we return, so that sat_hasher::equal > + later can quickly compare two atoms using just pointer equality. */ > + if (!atom_cache) > + atom_cache = hash_table<atom_hasher>::create_ggc (31); > + tree *slot = atom_cache->find_slot (atom, INSERT); > + if (*slot) > + return *slot; > + *slot = atom; > + } > + return atom; > } > > /* Returns the normal form of an expression. */ > @@ -2284,13 +2315,13 @@ struct sat_hasher : ggc_ptr_hash<sat_entry> > { > static hashval_t hash (sat_entry *e) > { We could use a comment here about why we can just hash the pointer. > - hashval_t value = hash_atomic_constraint (e->constr); > + hashval_t value = htab_hash_pointer (e->constr); > return iterative_hash_template_arg (e->args, value); > } > > static bool equal (sat_entry *e1, sat_entry *e2) > { > - if (!atomic_constraints_identical_p (e1->constr, e2->constr)) > + if (e1->constr != e2->constr) > return false; > return template_args_equal (e1->args, e2->args); > } > ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] c++: Reuse identical ATOMIC_CONSTRs during normalization 2020-11-05 20:45 ` Jason Merrill @ 2020-11-05 23:00 ` Patrick Palka 2020-11-06 1:31 ` Patrick Palka 0 siblings, 1 reply; 5+ messages in thread From: Patrick Palka @ 2020-11-05 23:00 UTC (permalink / raw) To: Jason Merrill; +Cc: Patrick Palka, gcc-patches On Thu, 5 Nov 2020, Jason Merrill wrote: > On 11/3/20 3:43 PM, Patrick Palka wrote: > > Profiling revealed that sat_hasher::equal accounts for nearly 40% of > > compile time in some cmcstl2 tests. > > > > This patch eliminates this bottleneck by caching the ATOMIC_CONSTRs > > returned by normalize_atom. This in turn allows us to replace the > > expensive atomic_constraints_identical_p check in sat_hasher::equal > > with cheap pointer equality, with no loss in cache hit rate. > > > > With this patch, compile time for the cmcstl2 test > > test/algorithm/set_symmetric_difference4.cpp drops from 19s to 11s with > > an --enable-checking=release compiler. > > > > Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for > > trunk? > > > > gcc/cp/ChangeLog: > > > > * constraint.cc (struct atom_hasher): New descriptor class for a > > hash_table. Use it to define ... > > (atom_cache): ... this. > > (normalize_atom): Use it to cache ATOMIC_CONSTRs when not > > generating diagnostics. > > (sat_hasher::hash): Use htab_hash_pointer instead of > > hash_atomic_constraint. > > (sat_hasher::equal): Test for pointer equality instead of > > atomic_constraints_identical_p. > > --- > > gcc/cp/constraint.cc | 37 ++++++++++++++++++++++++++++++++++--- > > 1 file changed, 34 insertions(+), 3 deletions(-) > > > > diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc > > index b6f6f0d02a5..ce720c641e8 100644 > > --- a/gcc/cp/constraint.cc > > +++ b/gcc/cp/constraint.cc > > @@ -710,6 +710,25 @@ normalize_concept_check (tree check, tree args, > > norm_info info) > > return normalize_expression (def, subst, info); > > } > > +/* Hash functions for ATOMIC_CONSTRs. */ > > + > > +struct atom_hasher : default_hash_traits<tree> > > +{ > > + static hashval_t hash (tree atom) > > + { > > + return hash_atomic_constraint (atom); > > + } > > + > > + static bool equal (tree atom1, tree atom2) > > + { > > + return atomic_constraints_identical_p (atom1, atom2); > > + } > > +}; > > This is the same as constraint_hash in logic.cc; either they should be > combined, or (probably) the hash table in logic.cc should be changed to also > take advantage of pointer equivalence. Ah, I forgot about the existence of this hasher. Consider this hasher changed to take advantage of the pointer equivalence (I'll post a revised and tested patch later today). > > > +/* Used by normalize_atom to cache ATOMIC_CONSTRs. */ > > + > > +static GTY((deletable)) hash_table<atom_hasher> *atom_cache; > > If we're relying on pointer identity, this can't be deletable; if GC discards > it, later normalization will generate a new equivalent ATOMIC_CONSTR, breaking > the uniqueness assumption. But because no ATOMIC_CONSTR is ever reachable from a GC root (since they live only inside GC-deletable structures), there will never be two equivalent ATOMIC_CONSTR trees live at once, which is a sufficient enough notion of uniqueness for us, I think. > > > /* The normal form of an atom depends on the expression. The normal > > form of a function call to a function concept is a check constraint > > for that concept. The normal form of a reference to a variable > > @@ -729,7 +748,19 @@ normalize_atom (tree t, tree args, norm_info info) > > /* Build a new info object for the atom. */ > > tree ci = build_tree_list (t, info.context); > > - return build1 (ATOMIC_CONSTR, ci, map); > > + tree atom = build1 (ATOMIC_CONSTR, ci, map); > > + if (!info.generate_diagnostics ()) > > + { > > + /* Cache the ATOMIC_CONSTRs that we return, so that sat_hasher::equal > > + later can quickly compare two atoms using just pointer equality. */ > > + if (!atom_cache) > > + atom_cache = hash_table<atom_hasher>::create_ggc (31); > > + tree *slot = atom_cache->find_slot (atom, INSERT); > > + if (*slot) > > + return *slot; > > + *slot = atom; > > + } > > + return atom; > > } > > /* Returns the normal form of an expression. */ > > @@ -2284,13 +2315,13 @@ struct sat_hasher : ggc_ptr_hash<sat_entry> > > { > > static hashval_t hash (sat_entry *e) > > { > > We could use a comment here about why we can just hash the pointer. Will do. The subsequent patch ("Use two levels of caching in satisfy_atom") also adds + /* Atoms with uninstantiated mappings are built in normalize_atom. + Their identity is determined by their pointer value due to + the caching of ATOMIC_CONSTRs performed therein. */ to sat_hasher::equal, but it could use repeating in sat_hasher::hash. > > > - hashval_t value = hash_atomic_constraint (e->constr); > > + hashval_t value = htab_hash_pointer (e->constr); > > return iterative_hash_template_arg (e->args, value); > > } > > static bool equal (sat_entry *e1, sat_entry *e2) > > { > > - if (!atomic_constraints_identical_p (e1->constr, e2->constr)) > > + if (e1->constr != e2->constr) > > return false; > > return template_args_equal (e1->args, e2->args); > > } > > > > ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] c++: Reuse identical ATOMIC_CONSTRs during normalization 2020-11-05 23:00 ` Patrick Palka @ 2020-11-06 1:31 ` Patrick Palka 2020-11-06 20:26 ` Jason Merrill 0 siblings, 1 reply; 5+ messages in thread From: Patrick Palka @ 2020-11-06 1:31 UTC (permalink / raw) To: Patrick Palka; +Cc: Jason Merrill, gcc-patches On Thu, 5 Nov 2020, Patrick Palka wrote: > On Thu, 5 Nov 2020, Jason Merrill wrote: > > > On 11/3/20 3:43 PM, Patrick Palka wrote: > > > Profiling revealed that sat_hasher::equal accounts for nearly 40% of > > > compile time in some cmcstl2 tests. > > > > > > This patch eliminates this bottleneck by caching the ATOMIC_CONSTRs > > > returned by normalize_atom. This in turn allows us to replace the > > > expensive atomic_constraints_identical_p check in sat_hasher::equal > > > with cheap pointer equality, with no loss in cache hit rate. > > > > > > With this patch, compile time for the cmcstl2 test > > > test/algorithm/set_symmetric_difference4.cpp drops from 19s to 11s with > > > an --enable-checking=release compiler. > > > > > > Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for > > > trunk? > > > > > > gcc/cp/ChangeLog: > > > > > > * constraint.cc (struct atom_hasher): New descriptor class for a > > > hash_table. Use it to define ... > > > (atom_cache): ... this. > > > (normalize_atom): Use it to cache ATOMIC_CONSTRs when not > > > generating diagnostics. > > > (sat_hasher::hash): Use htab_hash_pointer instead of > > > hash_atomic_constraint. > > > (sat_hasher::equal): Test for pointer equality instead of > > > atomic_constraints_identical_p. > > > --- > > > gcc/cp/constraint.cc | 37 ++++++++++++++++++++++++++++++++++--- > > > 1 file changed, 34 insertions(+), 3 deletions(-) > > > > > > diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc > > > index b6f6f0d02a5..ce720c641e8 100644 > > > --- a/gcc/cp/constraint.cc > > > +++ b/gcc/cp/constraint.cc > > > @@ -710,6 +710,25 @@ normalize_concept_check (tree check, tree args, > > > norm_info info) > > > return normalize_expression (def, subst, info); > > > } > > > +/* Hash functions for ATOMIC_CONSTRs. */ > > > + > > > +struct atom_hasher : default_hash_traits<tree> > > > +{ > > > + static hashval_t hash (tree atom) > > > + { > > > + return hash_atomic_constraint (atom); > > > + } > > > + > > > + static bool equal (tree atom1, tree atom2) > > > + { > > > + return atomic_constraints_identical_p (atom1, atom2); > > > + } > > > +}; > > > > This is the same as constraint_hash in logic.cc; either they should be > > combined, or (probably) the hash table in logic.cc should be changed to also > > take advantage of pointer equivalence. > > Ah, I forgot about the existence of this hasher. Consider this hasher > changed to take advantage of the pointer equivalence (I'll post a > revised and tested patch later today). On second thought, if we make the hasher in logic.cc and other places (e.g. add_constraint and constraints_equivalent_p) take advantage of pointer-based identity for ATOMIC_CONSTR, then we'd be relying on the uniqueness assumption in a crucial way rather than just relying on it in the satisfaction cache in a benign way that doesn't affect the semantics of the program if the assumption is somehow violated (we just get a cache miss if it is violated). So it seems to me it'd be better to not infect other parts of the code with this assumption, and to keep it local to the satisfaction cache, so as to minimize complexity. So I suppose we should go with combining these two "structural" hashers. > > > > > > +/* Used by normalize_atom to cache ATOMIC_CONSTRs. */ > > > + > > > +static GTY((deletable)) hash_table<atom_hasher> *atom_cache; > > > > If we're relying on pointer identity, this can't be deletable; if GC discards > > it, later normalization will generate a new equivalent ATOMIC_CONSTR, breaking > > the uniqueness assumption. > > But because no ATOMIC_CONSTR is ever reachable from a GC root (since > they live only inside GC-deletable structures), there will never be two > equivalent ATOMIC_CONSTR trees live at once, which is a sufficient > enough notion of uniqueness for us, I think. > > > > > > /* The normal form of an atom depends on the expression. The normal > > > form of a function call to a function concept is a check constraint > > > for that concept. The normal form of a reference to a variable > > > @@ -729,7 +748,19 @@ normalize_atom (tree t, tree args, norm_info info) > > > /* Build a new info object for the atom. */ > > > tree ci = build_tree_list (t, info.context); > > > - return build1 (ATOMIC_CONSTR, ci, map); > > > + tree atom = build1 (ATOMIC_CONSTR, ci, map); > > > + if (!info.generate_diagnostics ()) > > > + { > > > + /* Cache the ATOMIC_CONSTRs that we return, so that sat_hasher::equal > > > + later can quickly compare two atoms using just pointer equality. */ > > > + if (!atom_cache) > > > + atom_cache = hash_table<atom_hasher>::create_ggc (31); > > > + tree *slot = atom_cache->find_slot (atom, INSERT); > > > + if (*slot) > > > + return *slot; > > > + *slot = atom; > > > + } > > > + return atom; > > > } > > > /* Returns the normal form of an expression. */ > > > @@ -2284,13 +2315,13 @@ struct sat_hasher : ggc_ptr_hash<sat_entry> > > > { > > > static hashval_t hash (sat_entry *e) > > > { > > > > We could use a comment here about why we can just hash the pointer. > > Will do. The subsequent patch ("Use two levels of caching in > satisfy_atom") also adds > > + /* Atoms with uninstantiated mappings are built in normalize_atom. > + Their identity is determined by their pointer value due to > + the caching of ATOMIC_CONSTRs performed therein. */ > > to sat_hasher::equal, but it could use repeating in sat_hasher::hash. > > > > > > - hashval_t value = hash_atomic_constraint (e->constr); > > > + hashval_t value = htab_hash_pointer (e->constr); > > > return iterative_hash_template_arg (e->args, value); > > > } > > > static bool equal (sat_entry *e1, sat_entry *e2) > > > { > > > - if (!atomic_constraints_identical_p (e1->constr, e2->constr)) > > > + if (e1->constr != e2->constr) > > > return false; > > > return template_args_equal (e1->args, e2->args); > > > } > > > > > > > > ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] c++: Reuse identical ATOMIC_CONSTRs during normalization 2020-11-06 1:31 ` Patrick Palka @ 2020-11-06 20:26 ` Jason Merrill 0 siblings, 0 replies; 5+ messages in thread From: Jason Merrill @ 2020-11-06 20:26 UTC (permalink / raw) To: Patrick Palka; +Cc: gcc-patches On 11/5/20 8:31 PM, Patrick Palka wrote: > On Thu, 5 Nov 2020, Patrick Palka wrote: > >> On Thu, 5 Nov 2020, Jason Merrill wrote: >> >>> On 11/3/20 3:43 PM, Patrick Palka wrote: >>>> Profiling revealed that sat_hasher::equal accounts for nearly 40% of >>>> compile time in some cmcstl2 tests. >>>> >>>> This patch eliminates this bottleneck by caching the ATOMIC_CONSTRs >>>> returned by normalize_atom. This in turn allows us to replace the >>>> expensive atomic_constraints_identical_p check in sat_hasher::equal >>>> with cheap pointer equality, with no loss in cache hit rate. >>>> >>>> With this patch, compile time for the cmcstl2 test >>>> test/algorithm/set_symmetric_difference4.cpp drops from 19s to 11s with >>>> an --enable-checking=release compiler. >>>> >>>> Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for >>>> trunk? >>>> >>>> gcc/cp/ChangeLog: >>>> >>>> * constraint.cc (struct atom_hasher): New descriptor class for a >>>> hash_table. Use it to define ... >>>> (atom_cache): ... this. >>>> (normalize_atom): Use it to cache ATOMIC_CONSTRs when not >>>> generating diagnostics. >>>> (sat_hasher::hash): Use htab_hash_pointer instead of >>>> hash_atomic_constraint. >>>> (sat_hasher::equal): Test for pointer equality instead of >>>> atomic_constraints_identical_p. >>>> --- >>>> gcc/cp/constraint.cc | 37 ++++++++++++++++++++++++++++++++++--- >>>> 1 file changed, 34 insertions(+), 3 deletions(-) >>>> >>>> diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc >>>> index b6f6f0d02a5..ce720c641e8 100644 >>>> --- a/gcc/cp/constraint.cc >>>> +++ b/gcc/cp/constraint.cc >>>> @@ -710,6 +710,25 @@ normalize_concept_check (tree check, tree args, >>>> norm_info info) >>>> return normalize_expression (def, subst, info); >>>> } >>>> +/* Hash functions for ATOMIC_CONSTRs. */ >>>> + >>>> +struct atom_hasher : default_hash_traits<tree> >>>> +{ >>>> + static hashval_t hash (tree atom) >>>> + { >>>> + return hash_atomic_constraint (atom); >>>> + } >>>> + >>>> + static bool equal (tree atom1, tree atom2) >>>> + { >>>> + return atomic_constraints_identical_p (atom1, atom2); >>>> + } >>>> +}; >>> >>> This is the same as constraint_hash in logic.cc; either they should be >>> combined, or (probably) the hash table in logic.cc should be changed to also >>> take advantage of pointer equivalence. >> >> Ah, I forgot about the existence of this hasher. Consider this hasher >> changed to take advantage of the pointer equivalence (I'll post a >> revised and tested patch later today). > > On second thought, if we make the hasher in logic.cc and other places > (e.g. add_constraint and constraints_equivalent_p) take advantage of > pointer-based identity for ATOMIC_CONSTR, then we'd be relying on the > uniqueness assumption in a crucial way rather than just relying on it in > the satisfaction cache in a benign way that doesn't affect the semantics > of the program if the assumption is somehow violated (we just get a > cache miss if it is violated). True. But if doing this is a big speedup for satisfaction, I imagine it would also be a big speedup for subsumption. Maybe use the assumption and if CHECKING_P, make sure that the structural comparison matches the pointer comparison? The v2 patch is OK for now, this question doesn't need to block it. > So it seems to me it'd be better to not infect other parts of the code > with this assumption, and to keep it local to the satisfaction cache, > so as to minimize complexity. So I suppose we should go with combining > these two "structural" hashers. > >> >>> >>>> +/* Used by normalize_atom to cache ATOMIC_CONSTRs. */ >>>> + >>>> +static GTY((deletable)) hash_table<atom_hasher> *atom_cache; >>> >>> If we're relying on pointer identity, this can't be deletable; if GC discards >>> it, later normalization will generate a new equivalent ATOMIC_CONSTR, breaking >>> the uniqueness assumption. >> >> But because no ATOMIC_CONSTR is ever reachable from a GC root (since >> they live only inside GC-deletable structures), there will never be two >> equivalent ATOMIC_CONSTR trees live at once, which is a sufficient >> enough notion of uniqueness for us, I think. Makes sense. >>>> /* The normal form of an atom depends on the expression. The normal >>>> form of a function call to a function concept is a check constraint >>>> for that concept. The normal form of a reference to a variable >>>> @@ -729,7 +748,19 @@ normalize_atom (tree t, tree args, norm_info info) >>>> /* Build a new info object for the atom. */ >>>> tree ci = build_tree_list (t, info.context); >>>> - return build1 (ATOMIC_CONSTR, ci, map); >>>> + tree atom = build1 (ATOMIC_CONSTR, ci, map); >>>> + if (!info.generate_diagnostics ()) >>>> + { >>>> + /* Cache the ATOMIC_CONSTRs that we return, so that sat_hasher::equal >>>> + later can quickly compare two atoms using just pointer equality. */ >>>> + if (!atom_cache) >>>> + atom_cache = hash_table<atom_hasher>::create_ggc (31); >>>> + tree *slot = atom_cache->find_slot (atom, INSERT); >>>> + if (*slot) >>>> + return *slot; >>>> + *slot = atom; >>>> + } >>>> + return atom; >>>> } >>>> /* Returns the normal form of an expression. */ >>>> @@ -2284,13 +2315,13 @@ struct sat_hasher : ggc_ptr_hash<sat_entry> >>>> { >>>> static hashval_t hash (sat_entry *e) >>>> { >>> >>> We could use a comment here about why we can just hash the pointer. >> >> Will do. The subsequent patch ("Use two levels of caching in >> satisfy_atom") also adds >> >> + /* Atoms with uninstantiated mappings are built in normalize_atom. >> + Their identity is determined by their pointer value due to >> + the caching of ATOMIC_CONSTRs performed therein. */ >> >> to sat_hasher::equal, but it could use repeating in sat_hasher::hash. >> >>> >>>> - hashval_t value = hash_atomic_constraint (e->constr); >>>> + hashval_t value = htab_hash_pointer (e->constr); >>>> return iterative_hash_template_arg (e->args, value); >>>> } >>>> static bool equal (sat_entry *e1, sat_entry *e2) >>>> { >>>> - if (!atomic_constraints_identical_p (e1->constr, e2->constr)) >>>> + if (e1->constr != e2->constr) >>>> return false; >>>> return template_args_equal (e1->args, e2->args); >>>> } >>>> >>> >>> >> > ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2020-11-06 20:26 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2020-11-03 20:43 [PATCH] c++: Reuse identical ATOMIC_CONSTRs during normalization Patrick Palka 2020-11-05 20:45 ` Jason Merrill 2020-11-05 23:00 ` Patrick Palka 2020-11-06 1:31 ` Patrick Palka 2020-11-06 20:26 ` Jason Merrill
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).