[PATCH 4/1] c++: More precise tracking of potentially unstable satisfaction

Jason Merrill jason@redhat.com
Thu Dec 17 13:53:44 GMT 2020


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;
> 



More information about the Gcc-patches mailing list