[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