From: Jason Merrill <jason@redhat.com>
To: Patrick Palka <ppalka@redhat.com>
Cc: gcc-patches@gcc.gnu.org
Subject: Re: [PATCH 4/1] c++: More precise tracking of potentially unstable satisfaction
Date: Thu, 17 Dec 2020 08:53:44 -0500 [thread overview]
Message-ID: <23a7ff2a-3c5e-5ed3-e7fa-9240082eab5e@redhat.com> (raw)
In-Reply-To: <fb1da811-c84e-7844-78e9-78bfe3c1d771@idea>
On 12/16/20 6:24 PM, Patrick Palka wrote:
> On Wed, 16 Dec 2020, Jason Merrill wrote:
>
>> On 12/14/20 3:29 PM, Patrick Palka wrote:
>>> On Mon, 14 Dec 2020, Jason Merrill wrote:
>>>
>>>> On 12/14/20 1:07 PM, Patrick Palka wrote:
>>>>> This makes tracking of potentially unstable satisfaction results more
>>>>> precise by recording the specific types for which completion failed
>>>>> during satisfaction. We now recompute a satisfaction result only if one
>>>>> of these types has been completed since the last time we computed the
>>>>> satisfaction result. Thus the number of times that we recompute a
>>>>> satisfaction result is now bounded by the number of such incomplete
>>>>> types, rather than being effectively unbounded. This allows us to
>>>>> remove the invalid assumption in note_ftc_for_satisfaction that was
>>>>> added to avoid a compile time performance regression in cmcstl2 due to
>>>>> repeated re-computation of a satisfaction result that depended on
>>>>> completion of a permanently incomplete class template specialization.
>>>>>
>>>>> In order to continue to detect the instability in concepts-complete3.C,
>>>>> we also need to explicitly keep track of return type deduction failure
>>>>> alongside type completion failure. So this patch also adds a call to
>>>>> note_ftc_for_satisfaction in require_deduced_type.
>>>>>
>>>>> gcc/cp/ChangeLog:
>>>>>
>>>>> * constraint.cc (failed_type_completion_count): Remove.
>>>>> (failed_type_completions): Define.
>>>>> (note_failed_type_completion_for_satisfaction): Append the
>>>>> supplied argument to failed_type_completions.
>>>>> (some_type_complete_p): Define.
>>>>> (sat_entry::maybe_unstable): Replace with ...
>>>>> (sat_entry::ftc_begin, sat_entry::ftc_end): ... these.
>>>>> (satisfaction_cache::ftc_count): Replace with ...
>>>>> (satisfaction_cache::ftc_begin): ... this.
>>>>> (satisfaction_cache::satisfaction_cache): Adjust accordingly.
>>>>> (satisfaction_cache::get): Adjust accordingly, using
>>>>> some_type_complete_p.
>>>>> (satisfaction_cache::save): Adjust accordingly.
>>>>> (satisfy_declaration_constraints): Likewise.
>>>>> * decl.c (require_deduced_type): Call
>>>>> note_failed_type_completion_for_satisfaction.
>>>>> ---
>>>>> gcc/cp/constraint.cc | 89
>>>>> +++++++++++++++++++++++++++-----------------
>>>>> gcc/cp/decl.c | 1 +
>>>>> 2 files changed, 56 insertions(+), 34 deletions(-)
>>>>>
>>>>> diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
>>>>> index dc5c34e7e91..fd5d9429c9d 100644
>>>>> --- a/gcc/cp/constraint.cc
>>>>> +++ b/gcc/cp/constraint.cc
>>>>> @@ -2374,26 +2374,44 @@ tsubst_parameter_mapping (tree map, tree args,
>>>>> tsubst_flags_t complain, tree in_
>>>>> Constraint satisfaction
>>>>> ---------------------------------------------------------------------------*/
>>>>> -/* A counter incremented by
>>>>> note_failed_type_completion_for_satisfaction().
>>>>> - It's used by the satisfaction caches in order to flag "potentially
>>>>> unstable"
>>>>> - satisfaction results. */
>>>>> +/* A vector of incomplete types (and declarations with undeduced return
>>>>> types),
>>>>> + appended to by note_failed_type_completion_for_satisfaction. The
>>>>> + satisfaction caches use this in order to keep track of "potentially
>>>>> unstable"
>>>>> + satisfaction results.
>>>>> -static unsigned failed_type_completion_count;
>>>>> + Since references to entries in vector are stored only in the
>>>>> GC-deletable
>>>>> + sat_cache, it's safe to make this deletable as well. */
>>>>> -/* Called whenever a type completion failure occurs that definitely
>>>>> affects
>>>>> - the semantics of the program, by e.g. inducing substitution failure.
>>>>> */
>>>>> +static GTY((deletable)) vec<tree, va_gc> *failed_type_completions;
>>>>
>>>>> +/* Called whenever a type completion (or return type deduction) failure
>>>>> occurs
>>>>> + that definitely affects the semantics of the program, by e.g.
>>>>> inducing
>>>>> + substitution failure. */
>>>>> void
>>>>> -note_failed_type_completion_for_satisfaction (tree type)
>>>>> -{
>>>>> - gcc_checking_assert (!COMPLETE_TYPE_P (type));
>>>>> - if (CLASS_TYPE_P (type)
>>>>> - && CLASSTYPE_TEMPLATE_INSTANTIATION (type))
>>>>> - /* After instantiation, a class template specialization that's
>>>>> - incomplete will remain incomplete, so for our purposes we can
>>>>> - ignore this completion failure event. */;
>>>>> - else
>>>>> - ++failed_type_completion_count;
>>>>> +note_failed_type_completion_for_satisfaction (tree t)
>>>>> +{
>>>>> + gcc_checking_assert ((TYPE_P (t) && !COMPLETE_TYPE_P (t))
>>>>> + || (DECL_P (t) && undeduced_auto_decl (t)));
>>>>> + vec_safe_push (failed_type_completions, t);
>>>>> +}
>>>>
>>>> It looks like we'll happily add to this table outside of satisfaction,
>>>> making
>>>> it much larger than it needs to be.
>>>
>>> I should've mentioned that in practice these events (type completion
>>> failure or return type deduction failure inducing substitution failure)
>>> seem to be rare enough that the vector ends up being very small even
>>> when we append to it outside of satisfaction. For example the vector
>>> ends up being appended to at most 13 times in any one test in the
>>> libstdc++ ranges testsuite and cmcstl2 testsuite, and so far zero times
>>> when compiling llvm or range-v3.
>>
>> Good to know, but I would still expect it to be larger in a codebase that uses
>> opaque types.
>>
>> Certainly we shouldn't add to the vec when !flag_concepts.
>
> Sounds good, it seems easy enough to avoid appending to the vector
> outside of satisfaction, so we should at least do that. I'm testing
> the following that sets/clears 'satisfying_constraint' before/after
> satisfaction, and inspects it in note_failed_type_completion_for_satisfaction
> before we append to the vector.
OK.
> -- >8 --
>
> Subject: [PATCH] c++: More precise tracking of potentially unstable
> satisfaction
>
> This makes tracking of potentially unstable satisfaction results more
> precise by recording the specific types for which completion failed
> during satisfaction. We now recompute a satisfaction result only if one
> of these types has been completed since the last time we computed the
> satisfaction result. Thus the number of times that we recompute a
> satisfaction result is now bounded by the number of such incomplete
> types, rather than being effectively unbounded. This allows us to
> remove the invalid assumption in note_ftc_for_satisfaction that was
> added to avoid a compile time performance regression in cmcstl2 due to
> repeated recomputation of a satisfaction result that depended on
> completion of a permanently incomplete class template specialization.
>
> In order to continue to detect the instability in concepts-complete3.C,
> we also need to explicitly keep track of return type deduction failure
> alongside type completion failure. So this patch also adds a call to
> note_ftc_for_satisfaction in require_deduced_type.
>
> gcc/cp/ChangeLog:
>
> * constraint.cc (satisfying_constraint): Move up definition
> and give it bool type.
> (failed_type_completion_count): Replace with ...
> (failed_type_completions): ... this.
> (note_failed_type_completion_for_satisfaction): Append the
> supplied argument to failed_type_completions.
> (some_type_complete_p): Define.
> (sat_entry::maybe_unstable): Replace with ...
> (sat_entry::ftc_begin, sat_entry::ftc_end): ... these.
> (satisfaction_cache::ftc_count): Replace with ...
> (satisfaction_cache::ftc_begin): ... this.
> (satisfaction_cache::satisfaction_cache): Adjust accordingly.
> (satisfaction_cache::get): Adjust accordingly, using
> some_type_complete_p.
> (satisfaction_cache::save): Adjust accordingly.
> (satisfying_constraint_p): Remove.
> (satisfy_constraint): Set satisfying_constraint.
> (satisfy_declaration_constraints): Likewise.
> * decl.c (require_deduced_type): Call
> note_failed_type_completion_for_satisfaction.
> ---
> gcc/cp/constraint.cc | 114 ++++++++++++++++++++++++-------------------
> gcc/cp/decl.c | 1 +
> 2 files changed, 65 insertions(+), 50 deletions(-)
>
> diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
> index dc5c34e7e91..6a1abb23b22 100644
> --- a/gcc/cp/constraint.cc
> +++ b/gcc/cp/constraint.cc
> @@ -2374,26 +2374,51 @@ tsubst_parameter_mapping (tree map, tree args, tsubst_flags_t complain, tree in_
> Constraint satisfaction
> ---------------------------------------------------------------------------*/
>
> -/* A counter incremented by note_failed_type_completion_for_satisfaction().
> - It's used by the satisfaction caches in order to flag "potentially unstable"
> - satisfaction results. */
> +/* True if we are currently satisfying a constraint. */
>
> -static unsigned failed_type_completion_count;
> +static bool satisfying_constraint;
>
> -/* Called whenever a type completion failure occurs that definitely affects
> - the semantics of the program, by e.g. inducing substitution failure. */
> +/* A vector of incomplete types (and of declarations with undeduced return type),
> + appended to by note_failed_type_completion_for_satisfaction. The
> + satisfaction caches use this in order to keep track of "potentially unstable"
> + satisfaction results.
> +
> + Since references to entries in this vector are stored only in the
> + GC-deletable sat_cache, it's safe to make this deletable as well. */
> +
> +static GTY((deletable)) vec<tree, va_gc> *failed_type_completions;
> +
> +/* Called whenever a type completion (or return type deduction) failure occurs
> + that definitely affects the meaning of the program, by e.g. inducing
> + substitution failure. */
>
> void
> -note_failed_type_completion_for_satisfaction (tree type)
> -{
> - gcc_checking_assert (!COMPLETE_TYPE_P (type));
> - if (CLASS_TYPE_P (type)
> - && CLASSTYPE_TEMPLATE_INSTANTIATION (type))
> - /* After instantiation, a class template specialization that's
> - incomplete will remain incomplete, so for our purposes we can
> - ignore this completion failure event. */;
> - else
> - ++failed_type_completion_count;
> +note_failed_type_completion_for_satisfaction (tree t)
> +{
> + if (satisfying_constraint)
> + {
> + gcc_checking_assert ((TYPE_P (t) && !COMPLETE_TYPE_P (t))
> + || (DECL_P (t) && undeduced_auto_decl (t)));
> + vec_safe_push (failed_type_completions, t);
> + }
> +}
> +
> +/* Returns true if the range [BEGIN, END) of elements within the
> + failed_type_completions vector contains a complete type (or a
> + declaration with a non-placeholder return type). */
> +
> +static bool
> +some_type_complete_p (int begin, int end)
> +{
> + for (int i = begin; i < end; i++)
> + {
> + tree t = (*failed_type_completions)[i];
> + if (TYPE_P (t) && COMPLETE_TYPE_P (t))
> + return true;
> + if (DECL_P (t) && !undeduced_auto_decl (t))
> + return true;
> + }
> + return false;
> }
>
> /* Hash functions and data types for satisfaction cache entries. */
> @@ -2417,12 +2442,10 @@ struct GTY((for_user)) sat_entry
> performed. */
> location_t location;
>
> - /* True if this satisfaction result is flagged as "potentially unstable",
> - i.e. the result might change at different points in the program if
> - recomputed from scratch (which would be ill-formed). This flag controls
> - whether to recompute a cached satisfaction result from scratch even when
> - evaluating quietly. */
> - bool maybe_unstable;
> + /* The range of elements appended to the failed_type_completions vector
> + during computation of this satisfaction result, encoded as a begin/end
> + pair of offsets. */
> + int ftc_begin, ftc_end;
>
> /* True if we want to diagnose the above instability when it's detected.
> We don't always want to do so, in order to avoid emitting duplicate
> @@ -2531,7 +2554,7 @@ struct satisfaction_cache
>
> sat_entry *entry;
> sat_info info;
> - unsigned ftc_count;
> + int ftc_begin;
> };
>
> /* Constructor for the satisfaction_cache class. We're performing satisfaction
> @@ -2539,7 +2562,7 @@ struct satisfaction_cache
>
> satisfaction_cache
> ::satisfaction_cache (tree atom, tree args, sat_info info)
> - : entry(nullptr), info(info), ftc_count(failed_type_completion_count)
> + : entry(nullptr), info(info), ftc_begin(-1)
> {
> if (!sat_cache)
> sat_cache = hash_table<sat_hasher>::create_ggc (31);
> @@ -2578,7 +2601,7 @@ satisfaction_cache
> entry->args = args;
> entry->result = NULL_TREE;
> entry->location = input_location;
> - entry->maybe_unstable = false;
> + entry->ftc_begin = entry->ftc_end = -1;
> entry->diagnose_instability = false;
> if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (atom))
> /* We always want to diagnose instability of an atom with an
> @@ -2616,10 +2639,16 @@ satisfaction_cache::get ()
> return error_mark_node;
> }
>
> - if (info.noisy () || entry->maybe_unstable || !entry->result)
> + /* This satisfaction result is "potentially unstable" if a type for which
> + type completion failed during its earlier computation is now complete. */
> + bool maybe_unstable = some_type_complete_p (entry->ftc_begin,
> + entry->ftc_end);
> +
> + if (info.noisy () || maybe_unstable || !entry->result)
> {
> /* We're computing the satisfaction result from scratch. */
> entry->evaluating = true;
> + ftc_begin = vec_safe_length (failed_type_completions);
> return NULL_TREE;
> }
> else
> @@ -2667,32 +2696,16 @@ satisfaction_cache::save (tree result)
> if (info.quiet ())
> {
> entry->result = result;
> - /* We heuristically flag this satisfaction result as potentially unstable
> - iff during its computation, completion of a type failed. Note that
> - this may also clear the flag if the result turned out to be
> - independent of the previously detected type completion failure. */
> - entry->maybe_unstable = (ftc_count != failed_type_completion_count);
> + /* Store into this entry the list of relevant failed type completions
> + that occurred during (re)computation of the satisfaction result. */
> + gcc_checking_assert (ftc_begin != -1);
> + entry->ftc_begin = ftc_begin;
> + entry->ftc_end = vec_safe_length (failed_type_completions);
> }
>
> return result;
> }
>
> -static int satisfying_constraint = 0;
> -
> -/* Returns true if we are currently satisfying a constraint.
> -
> - This is used to guard against recursive calls to evaluate_concept_check
> - during template argument substitution.
> -
> - TODO: Do we need this now that we fully normalize prior to evaluation?
> - I think not. */
> -
> -bool
> -satisfying_constraint_p ()
> -{
> - return satisfying_constraint;
> -}
> -
> /* Substitute ARGS into constraint-expression T during instantiation of
> a member of a class template. */
>
> @@ -3012,6 +3025,8 @@ satisfy_constraint (tree t, tree args, sat_info info)
> {
> auto_timevar time (TV_CONSTRAINT_SAT);
>
> + auto ovr = make_temp_override (satisfying_constraint, true);
> +
> /* Turn off template processing. Constraint satisfaction only applies
> to non-dependent terms, so we want to ensure full checking here. */
> processing_template_decl_sentinel proc (true);
> @@ -3120,7 +3135,7 @@ satisfy_declaration_constraints (tree t, sat_info info)
> norm = normalize_nontemplate_requirements (t, info.noisy ());
> }
>
> - unsigned ftc_count = failed_type_completion_count;
> + unsigned ftc_count = vec_safe_length (failed_type_completions);
>
> tree result = boolean_true_node;
> if (norm)
> @@ -3136,8 +3151,7 @@ satisfy_declaration_constraints (tree t, sat_info info)
> /* True if this satisfaction is (heuristically) potentially unstable, i.e.
> if its result may depend on where in the program it was performed. */
> bool maybe_unstable_satisfaction = false;
> -
> - if (ftc_count != failed_type_completion_count)
> + if (ftc_count != vec_safe_length (failed_type_completions))
> /* Type completion failure occurred during satisfaction. The satisfaction
> result may (or may not) materially depend on the completeness of a type,
> so we consider it potentially unstable. */
> diff --git a/gcc/cp/decl.c b/gcc/cp/decl.c
> index b56eb113fd6..6e8dd0b45fd 100644
> --- a/gcc/cp/decl.c
> +++ b/gcc/cp/decl.c
> @@ -17869,6 +17869,7 @@ require_deduced_type (tree decl, tsubst_flags_t complain)
> /* We probably already complained about deduction failure. */;
> else if (complain & tf_error)
> error ("use of %qD before deduction of %<auto%>", decl);
> + note_failed_type_completion_for_satisfaction (decl);
> return false;
> }
> return true;
>
next prev parent reply other threads:[~2020-12-17 13:53 UTC|newest]
Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-12-14 18:07 [PATCH 3/1] c++: Fix return type deduction during satisfaction Patrick Palka
2020-12-14 18:07 ` [PATCH 4/1] c++: More precise tracking of potentially unstable satisfaction Patrick Palka
2020-12-14 19:18 ` Jason Merrill
2020-12-14 20:29 ` Patrick Palka
2020-12-16 21:55 ` Jason Merrill
2020-12-16 23:24 ` Patrick Palka
2020-12-17 13:53 ` Jason Merrill [this message]
2020-12-14 18:58 ` [PATCH 3/1] c++: Fix return type deduction during satisfaction Jason Merrill
2020-12-14 20:47 ` Patrick Palka
2020-12-15 3:20 ` Jason Merrill
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=23a7ff2a-3c5e-5ed3-e7fa-9240082eab5e@redhat.com \
--to=jason@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=ppalka@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).