[PATCH] c++: cache partial template specialization selection

[Patrick Palka <ppalka@redhat.com>]

There's currently no cheap way to obtain the partial template
specialization (and arguments relative to it) that was selected for a
class or variable template specialization.  Our only option is to
compute the result from scratch via most_specialized_partial_spec.

For class templates this isn't really an issue because we usually need
this information just once, upon instantiation.  But for variable
templates we need it upon specialization and later upon instantiation.
It'd be good for this information to be readily available in general
however.

To that end, this patch adds a TI_PARTIAL_INFO field to TEMPLATE_INFO
that holds another TEMPLATE_INFO consisting of the partial template and
arguments relative to it, which most_specialized_partial_spec then
uses to transparently cache its (now TEMPLATE_INFO) result.

Similarly, there's no easy way to go from the DECL_TEMPLATE_RESULT of a
partial TEMPLATE_DECL back to the TEMPLATE_DECL.  (Our best option is to
walk the DECL_TEMPLATE_SPECIALIZATIONS list of the primary TEMPLATE_DECL.)
So this patch also uses this new field to link these entities in this
other direction.

Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for
trunk?  Memory usage increases by ~0.2% overall with this patch (due to
the larger TEMPLATE_INFO, which now is the same size as TREE_LIST),
which seems acceptable.

gcc/cp/ChangeLog:

	* cp-tree.h (tree_template_info::partial): New data member.
	(TI_PARTIAL_INFO): New tree accessor.
	(most_specialized_partial_spec): Add defaulted bool parameter.
	* module.cc (trees_out::core_vals) <case TEMPLATE_INFO>:
	Stream TI_PARTIAL_INFO.
	(trees_in::core_vals) <case TEMPLATE_INFO>: Likewise.
	* parser.cc (specialization_of): Adjust after making
	most_specialized_partial_spec return TEMPLATE_INFO instead
	of TREE_LIST.
	* pt.cc (process_partial_specialization): Set TI_PARTIAL_INFO
	of 'decl' to point back to the partial TEMPLATE_DECL.  Likewise
	(and pass rechecking=true to most_specialization_partial_spec).
	(instantiate_class_template): Likewise.
	(instantiate_template): Set TI_PARTIAL_INFO to the result of
	most_specialization_partial_spec after forming a variable
	template specialization.
	(most_specialized_partial_spec): Add 'rechecking' parameter.
	Exit early if the template is not primary.  Use the TI_PARTIAL_INFO
	of the corresponding TEMPLATE_INFO as a cache unless 'rechecking'
	is true.  Don't bother setting TREE_TYPE of each TREE_LIST.
	(instantiate_decl): Adjust after making
	most_specialized_partial_spec return TEMPLATE_INFO instead of
	TREE_LIST.
	* ptree.cc (cxx_print_xnode) <case TEMPLATE_INFO>: Dump
	TI_PARTIAL_INFO.
---
 gcc/cp/cp-tree.h | 11 ++++++-
 gcc/cp/module.cc |  2 ++
 gcc/cp/parser.cc |  6 ++--
 gcc/cp/pt.cc     | 75 +++++++++++++++++++++++++++++++-----------------
 gcc/cp/ptree.cc  |  3 ++
 5 files changed, 66 insertions(+), 31 deletions(-)

diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 83982233111..fe94af46346 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -1564,6 +1564,7 @@ struct GTY(()) tree_template_info {
   struct tree_base base;
   tree tmpl;
   tree args;
+  tree partial;
   vec<deferred_access_check, va_gc> *deferred_access_checks;
 };
 
@@ -3755,6 +3756,14 @@ struct GTY(()) lang_decl {
   ((struct tree_template_info*)TEMPLATE_INFO_CHECK (NODE))->args
 #define TI_PENDING_TEMPLATE_FLAG(NODE) \
   TREE_LANG_FLAG_1 (TEMPLATE_INFO_CHECK (NODE))
+
+/* For a class or variable template specialization, this contains the
+   TEMPLATE_INFO result of most_specialized_partial_spec, i.e. the selected
+   partial template specialization and arguments relative to it.  */
+#define TI_PARTIAL_INFO(NODE) \
+  (gcc_checking_assert (PRIMARY_TEMPLATE_P (TI_TEMPLATE (NODE))), \
+   ((struct tree_template_info*)NODE)->partial)
+
 /* For a given TREE_VEC containing a template argument list,
    this property contains the number of arguments that are not
    defaulted.  */
@@ -7397,7 +7406,7 @@ extern bool comp_template_args			(tree, tree, tree * = NULL,
 extern int template_args_equal                  (tree, tree, bool = false);
 extern tree maybe_process_partial_specialization (tree);
 extern tree most_specialized_instantiation	(tree);
-extern tree most_specialized_partial_spec       (tree, tsubst_flags_t);
+extern tree most_specialized_partial_spec       (tree, tsubst_flags_t, bool = false);
 extern void print_candidates			(tree);
 extern void instantiate_pending_templates	(int);
 extern tree tsubst_default_argument		(tree, int, tree, tree,
diff --git a/gcc/cp/module.cc b/gcc/cp/module.cc
index ecde98d69b4..ea362bdffa4 100644
--- a/gcc/cp/module.cc
+++ b/gcc/cp/module.cc
@@ -6364,6 +6364,7 @@ trees_out::core_vals (tree t)
       {
 	WT (((lang_tree_node *)t)->template_info.tmpl);
 	WT (((lang_tree_node *)t)->template_info.args);
+	WT (((lang_tree_node *)t)->template_info.partial);
 
 	const auto *ac = (((lang_tree_node *)t)
 			  ->template_info.deferred_access_checks);
@@ -6851,6 +6852,7 @@ trees_in::core_vals (tree t)
     case TEMPLATE_INFO:
       RT (((lang_tree_node *)t)->template_info.tmpl);
       RT (((lang_tree_node *)t)->template_info.args);
+      RT (((lang_tree_node *)t)->template_info.partial);
       if (unsigned len = u ())
 	{
 	  auto &ac = (((lang_tree_node *)t)
diff --git a/gcc/cp/parser.cc b/gcc/cp/parser.cc
index 09cba713437..769c1d7b8ed 100644
--- a/gcc/cp/parser.cc
+++ b/gcc/cp/parser.cc
@@ -34347,9 +34347,9 @@ specialization_of (tree type)
 
   /* Determine the template or its partial specialization to which TYPE
      corresponds.  */
-  if (tree spec = most_specialized_partial_spec (type, tf_none))
-    if (spec != error_mark_node)
-      ret = TREE_TYPE (TREE_VALUE (spec));
+  if (tree ti = most_specialized_partial_spec (type, tf_none))
+    if (ti != error_mark_node)
+      ret = TREE_TYPE (TI_TEMPLATE (ti));
 
   if (ret == type)
     ret = CLASSTYPE_PRIMARY_TEMPLATE_TYPE (type);
diff --git a/gcc/cp/pt.cc b/gcc/cp/pt.cc
index dd10409ce18..fc44fb06fc0 100644
--- a/gcc/cp/pt.cc
+++ b/gcc/cp/pt.cc
@@ -5410,6 +5410,8 @@ process_partial_specialization (tree decl)
     = tree_cons (specargs, tmpl,
                  DECL_TEMPLATE_SPECIALIZATIONS (maintmpl));
   TREE_TYPE (DECL_TEMPLATE_SPECIALIZATIONS (maintmpl)) = type;
+  /* Link the DECL_TEMPLATE_RESULT back to the partial TEMPLATE_DECL.  */
+  TI_PARTIAL_INFO (tinfo) = build_template_info (tmpl, NULL_TREE);
 
   for (inst = DECL_TEMPLATE_INSTANTIATIONS (maintmpl); inst;
        inst = TREE_CHAIN (inst))
@@ -5420,16 +5422,17 @@ process_partial_specialization (tree decl)
 	     && CLASSTYPE_IMPLICIT_INSTANTIATION (instance))
 	  : DECL_TEMPLATE_INSTANTIATION (instance))
 	{
-	  tree spec = most_specialized_partial_spec (instance, tf_none);
+	  tree partial_ti = most_specialized_partial_spec (instance, tf_none,
+							   /*rechecking=*/true);
 	  tree inst_decl = (DECL_P (instance)
 			    ? instance : TYPE_NAME (instance));
-	  if (!spec)
+	  if (!partial_ti)
 	    /* OK */;
-	  else if (spec == error_mark_node)
+	  else if (partial_ti == error_mark_node)
 	    permerror (input_location,
 		       "declaration of %qD ambiguates earlier template "
 		       "instantiation for %qD", decl, inst_decl);
-	  else if (TREE_VALUE (spec) == tmpl)
+	  else if (TI_TEMPLATE (partial_ti) == tmpl)
 	    permerror (input_location,
 		       "partial specialization of %qD after instantiation "
 		       "of %qD", decl, inst_decl);
@@ -12118,8 +12121,8 @@ instantiate_class_template (tree type)
 
 	 and supposing that we are instantiating S<int*>, ARGS will
 	 presently be {int*} -- but we need {int}.  */
-      pattern = TREE_TYPE (t);
-      args = TREE_PURPOSE (t);
+      pattern = TREE_TYPE (TI_TEMPLATE (t));
+      args = TI_ARGS (t);
     }
   else
     {
@@ -22098,6 +22101,7 @@ instantiate_template (tree tmpl, tree orig_args, tsubst_flags_t complain)
 
   tree pattern = DECL_TEMPLATE_RESULT (gen_tmpl);
 
+  tree partial_ti = NULL_TREE;
   fndecl = NULL_TREE;
   if (VAR_P (pattern))
     {
@@ -22105,13 +22109,13 @@ instantiate_template (tree tmpl, tree orig_args, tsubst_flags_t complain)
 	 specialization now, because the type of the variable could be
 	 different.  */
       tree tid = lookup_template_variable (tmpl, targ_ptr);
-      tree elt = most_specialized_partial_spec (tid, complain);
-      if (elt == error_mark_node)
+      partial_ti = most_specialized_partial_spec (tid, complain);
+      if (partial_ti == error_mark_node)
 	pattern = error_mark_node;
-      else if (elt)
+      else if (partial_ti)
 	{
-	  tree partial_tmpl = TREE_VALUE (elt);
-	  tree partial_args = TREE_PURPOSE (elt);
+	  tree partial_tmpl = TI_TEMPLATE (partial_ti);
+	  tree partial_args = TI_ARGS (partial_ti);
 	  tree partial_pat = DECL_TEMPLATE_RESULT (partial_tmpl);
 	  fndecl = tsubst (partial_pat, partial_args, complain, gen_tmpl);
 	}
@@ -22135,6 +22139,11 @@ instantiate_template (tree tmpl, tree orig_args, tsubst_flags_t complain)
   DECL_TI_TEMPLATE (fndecl) = tmpl;
   DECL_TI_ARGS (fndecl) = targ_ptr;
 
+  if (VAR_P (pattern))
+    /* Now that we we've formed this variable template specialization,
+       remember the result of most_specialized_partial_spec for it.  */
+    TI_PARTIAL_INFO (DECL_TEMPLATE_INFO (fndecl)) = partial_ti;
+
   set_instantiating_module (fndecl);
 
   /* Now we know the specialization, compute access previously
@@ -26000,10 +26009,12 @@ most_general_template (tree decl)
 
 /* Return the most specialized of the template partial specializations
    which can produce TARGET, a specialization of some class or variable
-   template.  The value returned is actually a TREE_LIST; the TREE_VALUE is
-   a TEMPLATE_DECL node corresponding to the partial specialization, while
-   the TREE_PURPOSE is the set of template arguments that must be
-   substituted into the template pattern in order to generate TARGET.
+   template.  The value returned is a TEMPLATE_INFO; the TI_TEMPLATE is a
+   TEMPLATE_DECL node corresponding to the partial specialization, while
+   the TI_ARGS is the set of template arguments that must be substituted
+   into the template pattern in order to generate TARGET.  We save the
+   result in the TI_PARTIAL_INFO of the corresponding TEMPLATE_INFO unless
+   RECHECKING is true.
 
    If the choice of partial specialization is ambiguous, a diagnostic
    is issued, and the error_mark_node is returned.  If there are no
@@ -26011,12 +26022,14 @@ most_general_template (tree decl)
    returned, indicating that the primary template should be used.  */
 
 tree
-most_specialized_partial_spec (tree target, tsubst_flags_t complain)
+most_specialized_partial_spec (tree target, tsubst_flags_t complain,
+			       bool rechecking /* = false */)
 {
+  tree tinfo = NULL_TREE;
   tree tmpl, args, decl;
   if (TYPE_P (target))
     {
-      tree tinfo = CLASSTYPE_TEMPLATE_INFO (target);
+      tinfo = CLASSTYPE_TEMPLATE_INFO (target);
       tmpl = TI_TEMPLATE (tinfo);
       args = TI_ARGS (tinfo);
       decl = TYPE_NAME (target);
@@ -26029,7 +26042,7 @@ most_specialized_partial_spec (tree target, tsubst_flags_t complain)
     }
   else if (VAR_P (target))
     {
-      tree tinfo = DECL_TEMPLATE_INFO (target);
+      tinfo = DECL_TEMPLATE_INFO (target);
       tmpl = TI_TEMPLATE (tinfo);
       args = TI_ARGS (tinfo);
       decl = target;
@@ -26037,6 +26050,14 @@ most_specialized_partial_spec (tree target, tsubst_flags_t complain)
   else
     gcc_unreachable ();
 
+  if (!PRIMARY_TEMPLATE_P (tmpl))
+    return NULL_TREE;
+
+  if (!rechecking
+      && tinfo
+      && (VAR_P (target) || COMPLETE_TYPE_P (target)))
+    return TI_PARTIAL_INFO (tinfo);
+
   tree main_tmpl = most_general_template (tmpl);
   tree specs = DECL_TEMPLATE_SPECIALIZATIONS (main_tmpl);
   if (!specs)
@@ -26086,10 +26107,7 @@ most_specialized_partial_spec (tree target, tsubst_flags_t complain)
 
 	  /* Keep the candidate only if its constraints are satisfied.  */
 	  if (constraints_satisfied_p (ospec_tmpl, spec_args))
-            {
-	      list = tree_cons (spec_args, ospec_tmpl, list);
-              TREE_TYPE (list) = TREE_TYPE (t);
-            }
+	    list = tree_cons (spec_args, ospec_tmpl, list);
 	}
     }
 
@@ -26151,7 +26169,10 @@ most_specialized_partial_spec (tree target, tsubst_flags_t complain)
       return error_mark_node;
     }
 
-  return champ;
+  tree result = build_template_info (TREE_VALUE (champ), TREE_PURPOSE (champ));
+  if (!rechecking && tinfo)
+    TI_PARTIAL_INFO (tinfo) = result;
+  return result;
 }
 
 /* Explicitly instantiate DECL.  */
@@ -27043,11 +27064,11 @@ instantiate_decl (tree d, bool defer_ok, bool expl_inst_class_mem_p)
   if (variable_template_specialization_p (d))
     {
       /* Look up an explicit specialization, if any.  */
-      tree elt = most_specialized_partial_spec (d, tf_warning_or_error);
-      if (elt && elt != error_mark_node)
+      tree partial_ti = most_specialized_partial_spec (d, tf_warning_or_error);
+      if (partial_ti && partial_ti != error_mark_node)
 	{
-	  td = TREE_VALUE (elt);
-	  args = TREE_PURPOSE (elt);
+	  td = TI_TEMPLATE (partial_ti);
+	  args = TI_ARGS (partial_ti);
 	}
     }
 
diff --git a/gcc/cp/ptree.cc b/gcc/cp/ptree.cc
index e9b5066dc26..8ad853d6934 100644
--- a/gcc/cp/ptree.cc
+++ b/gcc/cp/ptree.cc
@@ -346,6 +346,9 @@ cxx_print_xnode (FILE *file, tree node, int indent)
     case TEMPLATE_INFO:
       print_node (file, "template", TI_TEMPLATE (node), indent+4);
       print_node (file, "args", TI_ARGS (node), indent+4);
+      if (TI_TEMPLATE (node)
+	  && PRIMARY_TEMPLATE_P (TI_TEMPLATE (node)))
+	print_node (file, "partial_info", TI_PARTIAL_INFO (node), indent+4);
       if (TI_PENDING_TEMPLATE_FLAG (node))
 	{
 	  indent_to (file, indent + 3);
-- 
2.41.0.199.ga9e066fa63