[PATCH 3/1] c++: Fix return type deduction during satisfaction

[PATCH 3/1] c++: Fix return type deduction during satisfaction

[Patrick Palka]

During satisfaction that's entered through the three-parameter version
of satisfy_declaration_constraints, current_function_decl gets set to
the dependent DECL_TEMPLATE_RESULT for sake of access checking.  This
makes the predicate in_template_function return true during satisfaction
from this entrypoint, which in turn makes calls to mark_used exit early
before it does its full processing.  This leads to us accepting the
invalid testcase below due to mark_used never attempting to deduce the
return type of A::foo() and detecting failure thereof.

It seems wrong for in_template_function to return true during
instantiation or during satisfaction, so this patch strengthens
in_template_function to additionally check current_instantiation().

Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK to
commit?

gcc/cp/ChangeLog:

	* pt.c (in_template_function): Return false if
	current_instantiation() is non-NULL.

gcc/testsuite/ChangeLog:

	* g++.dg/cpp2a/concepts-requires23.C: New test.
---
 gcc/cp/pt.c                                      | 9 +++++----
 gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C | 9 +++++++++
 2 files changed, 14 insertions(+), 4 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C

diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index 5b13f125002..5f7bc7000c4 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -10805,9 +10805,9 @@ uses_template_parms (tree t)
   return dependent_p;
 }
 
-/* Returns true iff current_function_decl is an incompletely instantiated
-   template.  Useful instead of processing_template_decl because the latter
-   is set to 0 during instantiate_non_dependent_expr.  */
+/* Returns true iff we're processing an incompletely instantiated template.
+   Useful instead of processing_template_decl because the latter is set to
+   0 during instantiate_non_dependent_expr.  */
 
 bool
 in_template_function (void)
@@ -10815,7 +10815,8 @@ in_template_function (void)
   tree fn = current_function_decl;
   bool ret;
   ++processing_template_decl;
-  ret = (fn && DECL_LANG_SPECIFIC (fn)
+  ret = (!current_instantiation ()
+	 && fn && DECL_LANG_SPECIFIC (fn)
 	 && DECL_TEMPLATE_INFO (fn)
 	 && any_dependent_template_arguments_p (DECL_TI_ARGS (fn)));
   --processing_template_decl;
diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C b/gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C
new file mode 100644
index 00000000000..e109beaac4f
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C
@@ -0,0 +1,9 @@
+// { dg-do compile { target c++20 } }
+
+// Verify f<A>'s associated constraints evaluate to false due
+// to return type deduction failure for A::foo().
+
+template <class T> concept fooable = requires { T::foo(0); };
+template <fooable T> int f ();
+struct A { static auto *foo(auto); };
+int a = f<A>(); // { dg-error "no match" }
-- 
2.29.2.540.g3cf59784d4

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

[Patrick Palka]

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);
+}
+
+/* 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 +2435,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 +2547,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 +2555,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 +2594,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 +2632,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,11 +2689,11 @@ 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);
+      /* Record 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;
@@ -3120,7 +3142,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 +3158,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;
-- 
2.29.2.540.g3cf59784d4

Re: [PATCH 3/1] c++: Fix return type deduction during satisfaction

[Jason Merrill]

On 12/14/20 1:07 PM, Patrick Palka wrote:
> During satisfaction that's entered through the three-parameter version
> of satisfy_declaration_constraints, current_function_decl gets set to
> the dependent DECL_TEMPLATE_RESULT for sake of access checking.  This
> makes the predicate in_template_function return true during satisfaction
> from this entrypoint, which in turn makes calls to mark_used exit early
> before it does its full processing.  This leads to us accepting the
> invalid testcase below due to mark_used never attempting to deduce the
> return type of A::foo() and detecting failure thereof.
> 
> It seems wrong for in_template_function to return true during
> instantiation or during satisfaction, so this patch strengthens
> in_template_function to additionally check current_instantiation().

This seems like it ought to work, but I also wonder about looking at 
cfun->decl (which is less volatile) instead of current_function_decl for 
in_template_function.

> Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK to
> commit?
> 
> gcc/cp/ChangeLog:
> 
> 	* pt.c (in_template_function): Return false if
> 	current_instantiation() is non-NULL.
> 
> gcc/testsuite/ChangeLog:
> 
> 	* g++.dg/cpp2a/concepts-requires23.C: New test.
> ---
>   gcc/cp/pt.c                                      | 9 +++++----
>   gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C | 9 +++++++++
>   2 files changed, 14 insertions(+), 4 deletions(-)
>   create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C
> 
> diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
> index 5b13f125002..5f7bc7000c4 100644
> --- a/gcc/cp/pt.c
> +++ b/gcc/cp/pt.c
> @@ -10805,9 +10805,9 @@ uses_template_parms (tree t)
>     return dependent_p;
>   }
>   
> -/* Returns true iff current_function_decl is an incompletely instantiated
> -   template.  Useful instead of processing_template_decl because the latter
> -   is set to 0 during instantiate_non_dependent_expr.  */
> +/* Returns true iff we're processing an incompletely instantiated template.
> +   Useful instead of processing_template_decl because the latter is set to
> +   0 during instantiate_non_dependent_expr.  */
>   
>   bool
>   in_template_function (void)
> @@ -10815,7 +10815,8 @@ in_template_function (void)
>     tree fn = current_function_decl;
>     bool ret;
>     ++processing_template_decl;
> -  ret = (fn && DECL_LANG_SPECIFIC (fn)
> +  ret = (!current_instantiation ()
> +	 && fn && DECL_LANG_SPECIFIC (fn)
>   	 && DECL_TEMPLATE_INFO (fn)
>   	 && any_dependent_template_arguments_p (DECL_TI_ARGS (fn)));
>     --processing_template_decl;
> diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C b/gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C
> new file mode 100644
> index 00000000000..e109beaac4f
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C
> @@ -0,0 +1,9 @@
> +// { dg-do compile { target c++20 } }
> +
> +// Verify f<A>'s associated constraints evaluate to false due
> +// to return type deduction failure for A::foo().
> +
> +template <class T> concept fooable = requires { T::foo(0); };
> +template <fooable T> int f ();
> +struct A { static auto *foo(auto); };
> +int a = f<A>(); // { dg-error "no match" }
> 

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

[Jason Merrill]

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.

For template instantiations, we probably want to remember the template 
itself rather than each individual instantiation, and then check if we 
see a new definition or partial specialization.  That should mean fewer 
elements to consider, and also less impact from order of instantiation.

I also wonder about using a hash_set or _map instead of a vec to reduce 
the size, though that would mean sacrificing the information about which 
specific types a particular atom cares about.

> +/* 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 +2435,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 +2547,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 +2555,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 +2594,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 +2632,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,11 +2689,11 @@ 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);
> +      /* Record 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;
> @@ -3120,7 +3142,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 +3158,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;
> 

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

[Patrick Palka]

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.

> 
> For template instantiations, we probably want to remember the template itself
> rather than each individual instantiation, and then check if we see a new
> definition or partial specialization.  That should mean fewer elements to
> consider, and also less impact from order of instantiation.
> 
> I also wonder about using a hash_set or _map instead of a vec to reduce the
> size, though that would mean sacrificing the information about which specific
> types a particular atom cares about.

So since the vector already ends up being very small, I suspect these
might not have a noticeable performance impact.

> 
> > +/* 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 +2435,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 +2547,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 +2555,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 +2594,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 +2632,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,11 +2689,11 @@ 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);
> > +      /* Record 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;
> > @@ -3120,7 +3142,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 +3158,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;
> > 
> 
> 

Re: [PATCH 3/1] c++: Fix return type deduction during satisfaction

[Patrick Palka]

On Mon, 14 Dec 2020, Jason Merrill wrote:

> On 12/14/20 1:07 PM, Patrick Palka wrote:
> > During satisfaction that's entered through the three-parameter version
> > of satisfy_declaration_constraints, current_function_decl gets set to
> > the dependent DECL_TEMPLATE_RESULT for sake of access checking.  This
> > makes the predicate in_template_function return true during satisfaction
> > from this entrypoint, which in turn makes calls to mark_used exit early
> > before it does its full processing.  This leads to us accepting the
> > invalid testcase below due to mark_used never attempting to deduce the
> > return type of A::foo() and detecting failure thereof.
> > 
> > It seems wrong for in_template_function to return true during
> > instantiation or during satisfaction, so this patch strengthens
> > in_template_function to additionally check current_instantiation().
> 
> This seems like it ought to work, but I also wonder about looking at
> cfun->decl (which is less volatile) instead of current_function_decl for
> in_template_function.

That works well, so far it's passed make check-c++.  I'm fully testing
the following patch:

-- >8 --

Subject: [PATCH] c++: Fix return type deduction during satisfaction

During satisfaction that's entered through the three-parameter version
of satisfy_declaration_constraints, current_function_decl gets set to
the dependent DECL_TEMPLATE_RESULT for sake of access checking.  This
makes the predicate in_template_function return true during satisfaction
from this entrypoint, which in turn makes calls to mark_used exit early
before it does its full processing.  This leads to us accepting the
invalid testcase below due to mark_used never attempting to deduce the
return type of A::foo() and detecting failure thereof.

It seems wrong for in_template_function to be true during instantiation
or during satisfaction, so this patch makes in_template_function inspect
the less volatile cfun->decl instead of current_function_decl.

gcc/cp/ChangeLog:

	* pt.c (in_template_function): Inspect cfun->decl instead of
	current_function_decl.

gcc/testsuite/ChangeLog:

	* g++.dg/cpp2a/concepts-requires23.C: New test.
---
 gcc/cp/pt.c                                      | 6 ++++--
 gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C | 9 +++++++++
 2 files changed, 13 insertions(+), 2 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C

diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index 5b13f125002..ce2e8797aae 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -10805,14 +10805,16 @@ uses_template_parms (tree t)
   return dependent_p;
 }
 
-/* Returns true iff current_function_decl is an incompletely instantiated
+/* Returns true iff we're processing an incompletely instantiated function
    template.  Useful instead of processing_template_decl because the latter
    is set to 0 during instantiate_non_dependent_expr.  */
 
 bool
 in_template_function (void)
 {
-  tree fn = current_function_decl;
+  /* Inspect the less volatile cfun->decl instead of current_function_decl;
+     the latter might get set for e.g. access checking during satisfaction.  */
+  tree fn = cfun ? cfun->decl : NULL_TREE;
   bool ret;
   ++processing_template_decl;
   ret = (fn && DECL_LANG_SPECIFIC (fn)
diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C b/gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C
new file mode 100644
index 00000000000..e109beaac4f
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C
@@ -0,0 +1,9 @@
+// { dg-do compile { target c++20 } }
+
+// Verify f<A>'s associated constraints evaluate to false due
+// to return type deduction failure for A::foo().
+
+template <class T> concept fooable = requires { T::foo(0); };
+template <fooable T> int f ();
+struct A { static auto *foo(auto); };
+int a = f<A>(); // { dg-error "no match" }
-- 
2.29.2.540.g3cf59784d4

Re: [PATCH 3/1] c++: Fix return type deduction during satisfaction

[Jason Merrill]

On 12/14/20 3:47 PM, Patrick Palka wrote:
> On Mon, 14 Dec 2020, Jason Merrill wrote:
> 
>> On 12/14/20 1:07 PM, Patrick Palka wrote:
>>> During satisfaction that's entered through the three-parameter version
>>> of satisfy_declaration_constraints, current_function_decl gets set to
>>> the dependent DECL_TEMPLATE_RESULT for sake of access checking.  This
>>> makes the predicate in_template_function return true during satisfaction
>>> from this entrypoint, which in turn makes calls to mark_used exit early
>>> before it does its full processing.  This leads to us accepting the
>>> invalid testcase below due to mark_used never attempting to deduce the
>>> return type of A::foo() and detecting failure thereof.
>>>
>>> It seems wrong for in_template_function to return true during
>>> instantiation or during satisfaction, so this patch strengthens
>>> in_template_function to additionally check current_instantiation().
>>
>> This seems like it ought to work, but I also wonder about looking at
>> cfun->decl (which is less volatile) instead of current_function_decl for
>> in_template_function.
> 
> That works well, so far it's passed make check-c++.  I'm fully testing
> the following patch:

OK.

> -- >8 --
> 
> Subject: [PATCH] c++: Fix return type deduction during satisfaction
> 
> During satisfaction that's entered through the three-parameter version
> of satisfy_declaration_constraints, current_function_decl gets set to
> the dependent DECL_TEMPLATE_RESULT for sake of access checking.  This
> makes the predicate in_template_function return true during satisfaction
> from this entrypoint, which in turn makes calls to mark_used exit early
> before it does its full processing.  This leads to us accepting the
> invalid testcase below due to mark_used never attempting to deduce the
> return type of A::foo() and detecting failure thereof.
> 
> It seems wrong for in_template_function to be true during instantiation
> or during satisfaction, so this patch makes in_template_function inspect
> the less volatile cfun->decl instead of current_function_decl.
> 
> gcc/cp/ChangeLog:
> 
> 	* pt.c (in_template_function): Inspect cfun->decl instead of
> 	current_function_decl.
> 
> gcc/testsuite/ChangeLog:
> 
> 	* g++.dg/cpp2a/concepts-requires23.C: New test.
> ---
>   gcc/cp/pt.c                                      | 6 ++++--
>   gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C | 9 +++++++++
>   2 files changed, 13 insertions(+), 2 deletions(-)
>   create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C
> 
> diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
> index 5b13f125002..ce2e8797aae 100644
> --- a/gcc/cp/pt.c
> +++ b/gcc/cp/pt.c
> @@ -10805,14 +10805,16 @@ uses_template_parms (tree t)
>     return dependent_p;
>   }
>   
> -/* Returns true iff current_function_decl is an incompletely instantiated
> +/* Returns true iff we're processing an incompletely instantiated function
>      template.  Useful instead of processing_template_decl because the latter
>      is set to 0 during instantiate_non_dependent_expr.  */
>   
>   bool
>   in_template_function (void)
>   {
> -  tree fn = current_function_decl;
> +  /* Inspect the less volatile cfun->decl instead of current_function_decl;
> +     the latter might get set for e.g. access checking during satisfaction.  */
> +  tree fn = cfun ? cfun->decl : NULL_TREE;
>     bool ret;
>     ++processing_template_decl;
>     ret = (fn && DECL_LANG_SPECIFIC (fn)
> diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C b/gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C
> new file mode 100644
> index 00000000000..e109beaac4f
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/cpp2a/concepts-requires23.C
> @@ -0,0 +1,9 @@
> +// { dg-do compile { target c++20 } }
> +
> +// Verify f<A>'s associated constraints evaluate to false due
> +// to return type deduction failure for A::foo().
> +
> +template <class T> concept fooable = requires { T::foo(0); };
> +template <fooable T> int f ();
> +struct A { static auto *foo(auto); };
> +int a = f<A>(); // { dg-error "no match" }
> 

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

[Jason Merrill]

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.
>> For template instantiations, we probably want to remember the template itself
>> rather than each individual instantiation, and then check if we see a new
>> definition or partial specialization.  That should mean fewer elements to
>> consider, and also less impact from order of instantiation.
>>
>> I also wonder about using a hash_set or _map instead of a vec to reduce the
>> size, though that would mean sacrificing the information about which specific
>> types a particular atom cares about.
> 
> So since the vector already ends up being very small, I suspect these
> might not have a noticeable performance impact.
> 
>>
>>> +/* 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 +2435,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 +2547,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 +2555,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 +2594,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 +2632,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,11 +2689,11 @@ 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);
>>> +      /* Record 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;
>>> @@ -3120,7 +3142,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 +3158,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;
>>>
>>
>>
> 

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

[Patrick Palka]

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.

-- >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;
-- 
2.30.0.rc0

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

[Jason Merrill]

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