[PR,c++/80290] recycle tinst garbage sooner

Message ID ora7u6lmos.fsf@lxoliva.fsfla.org
State New
Headers show
Series
  • [PR,c++/80290] recycle tinst garbage sooner
Related show

Commit Message

Alexandre Oliva April 13, 2018, 11:18 p.m.
tinst_level objects are created during template instantiation, and
they're most often quite short-lived, but since there's no intervening
garbage collection, they accumulate throughout the pass while most by
far could be recycled after a short while.  The original testcase in
PR80290, for example, creates almost 55 million tinst_level objects,
all but 10 thousand of them without intervening GC, but we don't need
more than 284 of them live at a time.

Furthermore, in many cases, TREE_LIST objects are created to stand for
the decl in tinst_level.  In most cases, those can be recycled as soon
as the tinst_level object is recycled; in some relatively common
cases, they are modified and reused in up to 3 tinst_level objects.
In the same testcase, TREE_LISTs are used in all but 3 thousand of the
tinst_level objects, and we don't need more than 89 tinst_level
objects with TREE_LISTs live at a time.  Furthermore, all but 2
thousand of those are created without intervening GC.

This patch arranges for tinst_level objects to be refcounted (I've
seen as many as 20 live references to a single tinst_level object in
my testing), and for pending_template, tinst_level and TREE_LIST
objects that can be recycled to be added to freelists; that's much
faster than ggc_free()ing them and reallocating them shortly
thereafter.  In fact, the introduction of such freelists is what makes
this entire patch lighter-weight, when it comes to memory use, and
faster.  With refcounting alone, the total memory footprint was still
about the same, and we spent more time.

In order to further reduce memory use, I've arranged for us to create
TREE_LISTs lazily, only at points that really need them (when printing
error messages).  This grows tinst_level by an additional pointer, but
since a TREE_LIST holds a lot more than an extra pointer, and
tinst_levels with TREE_LISTs used to be allocated tens of thousands of
times more often than plain decl ones, we still save memory overall.

I was still not quite happy about growing memory use in cases that
used template classes but not template overload resolution, so I
changed the type of the errors field to unsigned short, from int.
With that change, in_system_header_p and refcount move into the same
word or half-word that used to hold errors, releasing a full word,
bringing tinst_level back to its original size, now without any
padding.

The errors field is only used to test whether we've had any errors
since the expansion of some template, to skip the expansion of further
templates.  If we get 2^16 errors or more, it is probably reasonable
to refrain from expanding further templates, even if we would expand
them before this change.

With these changes, compile time for the original testcase at -O0,
with default checking enabled, is cut down by some 3.7%, total GCable
memory allocation is cut down by almost 20%, and total memory use (as
reported by GNU time as maxresident) is cut down by slightly over 15%.

Regstrapped on i686- and x86_64-linux-gnu.  Ok to install?
(See below for an incremental patch that introduces some statistics
collection and reporting, that shows how I collected some of the data
above.  That one is not meant for inclusion)

for  gcc/cp/ChangeLog

	PR c++/80290
	* cp-tree.h (struct tinst_level): Split decl into tldcl and
	targs.  Add private split_list_p, tree_list_p, and not_list_p
	inline const predicates; to_list private member function
	declaration; list_p, get_node, and get_decl_maybe accessors,
	and refcount private data member.  Narrow errors to unsigned
	short.
	* error.c (print_instantiation_full_context): Use new
	accessors.
	(print_instantiation_partial_context_line): Likewise.
	* mangle.c (mangle_decl_string): Likewise.
	* pt.c (freelist): New template class.
	(tree_list_freelist_head): New var.
	(tree_list_freelist): New fn, along with specializations.
	(tinst_level_freelist_head): New var.
	(pending_template_freelist_head): Likewise.
	(tinst_level_freelist, pending_template_freelist): New fns.
	(tinst_level::to_list): Define.
	(inc_refcount_use, dec_refcount_use): New fns for tinst_level.
	(set_refcount_ptr): New template fn.
	(add_pending_template): Adjust for refcounting, freelists and
	new accessors.
	(neglectable_inst_p): Take a NULL d as a non-DECL.
	(limit_bad_template_recursion): Use new accessors.
	(push_tinst_level): New overload to create the list.
	(push_tinst_level_loc): Make it static, split decl into two
	args, adjust tests and initialization to cope with split
	lists, use freelist, adjust for refcounting.
	(push_tinst_level_loc): New wrapper with the old interface.
	(pop_tinst_level): Adjust for refcounting.
	(record_last_problematic_instantiation): Likewise.
	(reopen_tinst_level): Likewise.  Use new accessors.
	(instantiate_alias_template): Adjust for split list.
	(fn_type_unification): Likewise.
	(get_partial_spec_bindings): Likewise.
	(instantiate_pending_templates): Use new accessors.  Adjust
	for refcount.  Release pending_template to freelist.
	(instantiating_current_function_p): Use new accessors.
---
 gcc/cp/cp-tree.h |   59 ++++++++
 gcc/cp/error.c   |   10 +
 gcc/cp/mangle.c  |    2 
 gcc/cp/pt.c      |  386 +++++++++++++++++++++++++++++++++++++++++++++---------
 4 files changed, 379 insertions(+), 78 deletions(-)

Comments

Jason Merrill April 16, 2018, 3:48 p.m. | #1
On Fri, Apr 13, 2018, 5:19 PM Alexandre Oliva <aoliva@redhat.com> wrote:

> tinst_level objects are created during template instantiation, and
> they're most often quite short-lived, but since there's no intervening
> garbage collection, they accumulate throughout the pass while most by
> far could be recycled after a short while.  The original testcase in
> PR80290, for example, creates almost 55 million tinst_level objects,
> all but 10 thousand of them without intervening GC, but we don't need
> more than 284 of them live at a time.
>
> Furthermore, in many cases, TREE_LIST objects are created to stand for
> the decl in tinst_level.  In most cases, those can be recycled as soon
> as the tinst_level object is recycled; in some relatively common
> cases, they are modified and reused in up to 3 tinst_level objects.
> In the same testcase, TREE_LISTs are used in all but 3 thousand of the
> tinst_level objects, and we don't need more than 89 tinst_level
> objects with TREE_LISTs live at a time.  Furthermore, all but 2
> thousand of those are created without intervening GC.
>
> This patch arranges for tinst_level objects to be refcounted (I've
> seen as many as 20 live references to a single tinst_level object in
> my testing), and for pending_template, tinst_level and TREE_LIST
> objects that can be recycled to be added to freelists; that's much
> faster than ggc_free()ing them and reallocating them shortly
> thereafter.  In fact, the introduction of such freelists is what makes
> this entire patch lighter-weight, when it comes to memory use, and
> faster.  With refcounting alone, the total memory footprint was still
> about the same, and we spent more time.
>
> In order to further reduce memory use, I've arranged for us to create
> TREE_LISTs lazily, only at points that really need them (when printing
> error messages).  This grows tinst_level by an additional pointer, but
> since a TREE_LIST holds a lot more than an extra pointer, and
> tinst_levels with TREE_LISTs used to be allocated tens of thousands of
> times more often than plain decl ones, we still save memory overall.
>
> I was still not quite happy about growing memory use in cases that
> used template classes but not template overload resolution, so I
> changed the type of the errors field to unsigned short, from int.
> With that change, in_system_header_p and refcount move into the same
> word or half-word that used to hold errors, releasing a full word,
> bringing tinst_level back to its original size, now without any
> padding.
>
> The errors field is only used to test whether we've had any errors
> since the expansion of some template, to skip the expansion of further
> templates.  If we get 2^16 errors or more, it is probably reasonable
> to refrain from expanding further templates, even if we would expand
> them before this change.
>
> With these changes, compile time for the original testcase at -O0,
> with default checking enabled, is cut down by some 3.7%, total GCable
> memory allocation is cut down by almost 20%, and total memory use (as
> reported by GNU time as maxresident) is cut down by slightly over 15%.
>

Great!

Regstrapped on i686- and x86_64-linux-gnu.  Ok to install?
> (See below for an incremental patch that introduces some statistics
> collection and reporting, that shows how I collected some of the data
> above.  That one is not meant for inclusion)
>
> for  gcc/cp/ChangeLog
>
>         PR c++/80290
>         * cp-tree.h (struct tinst_level): Split decl into tldcl and
>         targs.  Add private split_list_p, tree_list_p, and not_list_p
>         inline const predicates; to_list private member function
>         declaration; list_p, get_node, and get_decl_maybe accessors,
>         and refcount private data member.  Narrow errors to unsigned
>         short.
>         * error.c (print_instantiation_full_context): Use new
>         accessors.
>         (print_instantiation_partial_context_line): Likewise.
>         * mangle.c (mangle_decl_string): Likewise.
>         * pt.c (freelist): New template class.
>         (tree_list_freelist_head): New var.
>         (tree_list_freelist): New fn, along with specializations.
>         (tinst_level_freelist_head): New var.
>         (pending_template_freelist_head): Likewise.
>         (tinst_level_freelist, pending_template_freelist): New fns.
>         (tinst_level::to_list): Define.
>         (inc_refcount_use, dec_refcount_use): New fns for tinst_level.
>         (set_refcount_ptr): New template fn.
>         (add_pending_template): Adjust for refcounting, freelists and
>         new accessors.
>         (neglectable_inst_p): Take a NULL d as a non-DECL.
>         (limit_bad_template_recursion): Use new accessors.
>         (push_tinst_level): New overload to create the list.
>         (push_tinst_level_loc): Make it static, split decl into two
>         args, adjust tests and initialization to cope with split
>         lists, use freelist, adjust for refcounting.
>         (push_tinst_level_loc): New wrapper with the old interface.
>         (pop_tinst_level): Adjust for refcounting.
>         (record_last_problematic_instantiation): Likewise.
>         (reopen_tinst_level): Likewise.  Use new accessors.
>         (instantiate_alias_template): Adjust for split list.
>         (fn_type_unification): Likewise.
>         (get_partial_spec_bindings): Likewise.
>         (instantiate_pending_templates): Use new accessors.  Adjust
>         for refcount.  Release pending_template to freelist.
>         (instantiating_current_function_p): Use new accessors.
> ---
>  gcc/cp/cp-tree.h |   59 ++++++++
>  gcc/cp/error.c   |   10 +
>  gcc/cp/mangle.c  |    2
>  gcc/cp/pt.c      |  386
> +++++++++++++++++++++++++++++++++++++++++++++---------
>  4 files changed, 379 insertions(+), 78 deletions(-)
>
> diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
> index d0f87603e98e..e9d9bab879bc 100644
> --- a/gcc/cp/cp-tree.h
> +++ b/gcc/cp/cp-tree.h
> @@ -5870,19 +5870,68 @@ struct GTY((chain_next ("%h.next"))) tinst_level {
>    /* The immediately deeper level in the chain.  */
>    struct tinst_level *next;
>
> -  /* The original node.  Can be either a DECL (for a function or static
> -     data member) or a TYPE (for a class), depending on what we were
> -     asked to instantiate.  */
> -  tree decl;
> +  /* The original node.  TLDCL can be a DECL (for a function or static
> +     data member), a TYPE (for a class), depending on what we were
> +     asked to instantiate, or a TREE_LIST with the template as PURPOSE
> +     and the template args as VALUE, if we are substituting for
> +     overload resolution.  In all these cases, TARGS is NULL.
> +     However, to avoid creating TREE_LIST objects for substitutions if
> +     we can help, we store PURPOSE and VALUE in TLDCL and TARGS,
> +     respectively.  So TLDCL stands for TREE_LIST or DECL (the
> +     template is a DECL too), whereas TARGS stands for the template
> +     arguments.  */
> +  tree tldcl, targs;
> +
> + private:
> +  /* Return TRUE iff the original node is a split list.  */
> +  bool split_list_p () const { return targs; }
> +
> +  /* Return TRUE iff the original node is a TREE_LIST object.  */
> +  bool tree_list_p () const
> +  {
> +    return !split_list_p () && TREE_CODE (tldcl) == TREE_LIST;
> +  }
> +
> +  /* Return TRUE iff the original node is not a list, split or not.  */
> +  bool not_list_p () const
> +  {
> +    return !split_list_p () && !tree_list_p ();
> +  }
> +
> +  /* Convert (in place) the original node from a split list to a
> +     TREE_LIST.  */
> +  tree to_list ();
> +
> + public:
> +  /* Return TRUE iff the original node is a list, split or not.  */
> +  bool list_p () const { return !not_list_p (); }
> +
> +  /* Return the original node; if it's a split list, make it a
> +     TREE_LIST first, so that it can be returned as a single tree
> +     object.  */
> +  tree get_node () const {
> +    if (!split_list_p ()) return tldcl;
> +    else return const_cast <tinst_level *>(this)->to_list ();
> +  }
>

This looks like a dangerous violation of const correctness, since it does
in fact modify the object.

+  /* Return the original node if it's a DECL or a TREE_LIST, but do
> +     NOT convert a split list to a TREE_LIST: return NULL instead.  */
> +  tree get_decl_maybe () const {
> +    if (!split_list_p ()) return tldcl;
> +    else return NULL_TREE;
> +  }
>
>    /* The location where the template is instantiated.  */
>    location_t locus;
>
>    /* errorcount+sorrycount when we pushed this level.  */
> -  int errors;
> +  unsigned short errors;
>
>    /* True if the location is in a system header.  */
>    bool in_system_header_p;
> +
> +  /* Count references to this object.  */
> +  unsigned char refcount;
>  };
>
>  bool decl_spec_seq_has_spec_p (const cp_decl_specifier_seq *,
> cp_decl_spec);
> diff --git a/gcc/cp/error.c b/gcc/cp/error.c
> index f27b700a4349..983ffdfedbb2 100644
> --- a/gcc/cp/error.c
> +++ b/gcc/cp/error.c
> @@ -3457,11 +3457,11 @@ print_instantiation_full_context
> (diagnostic_context *context)
>    if (p)
>      {
>        pp_verbatim (context->printer,
> -                  TREE_CODE (p->decl) == TREE_LIST
> +                  p->list_p ()
>                    ? _("%s: In substitution of %qS:\n")
>                    : _("%s: In instantiation of %q#D:\n"),
>                    LOCATION_FILE (location),
> -                  p->decl);
> +                  p->get_node ());
>
>        location = p->locus;
>        p = p->next;
> @@ -3492,18 +3492,18 @@ print_instantiation_partial_context_line
> (diagnostic_context *context,
>
>    if (t != NULL)
>      {
> -      if (TREE_CODE (t->decl) == TREE_LIST)
> +      if (t->list_p ())
>         pp_verbatim (context->printer,
>                      recursive_p
>                      ? _("recursively required by substitution of %qS\n")
>                      : _("required by substitution of %qS\n"),
> -                    t->decl);
> +                    t->get_node ());
>        else
>         pp_verbatim (context->printer,
>                      recursive_p
>                      ? _("recursively required from %q#D\n")
>                      : _("required from %q#D\n"),
> -                    t->decl);
> +                    t->get_node ());
>      }
>    else
>      {
> diff --git a/gcc/cp/mangle.c b/gcc/cp/mangle.c
> index a7f9d686345d..940f7ed87e20 100644
> --- a/gcc/cp/mangle.c
> +++ b/gcc/cp/mangle.c
> @@ -3777,7 +3777,7 @@ mangle_decl_string (const tree decl)
>    if (DECL_LANG_SPECIFIC (decl) && DECL_USE_TEMPLATE (decl))
>      {
>        struct tinst_level *tl = current_instantiation ();
> -      if ((!tl || tl->decl != decl)
> +      if ((!tl || tl->get_decl_maybe () != decl)
>           && push_tinst_level (decl))
>         {
>           template_p = true;
> diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
> index da8a5264d33e..2442f07095ca 100644
> --- a/gcc/cp/pt.c
> +++ b/gcc/cp/pt.c
> @@ -8731,6 +8731,252 @@ comp_template_args_porder (tree oargs, tree nargs)
>    return comp_template_args (oargs, nargs, NULL, NULL, true);
>  }
>
> +/* Implement a freelist interface for objects of type T.
> +
> +   Head is a separate object, rather than a regular member, so that we
> +   can define it as a GTY deletable pointer, which is highly
> +   desirable.  A data member could be declared that way, but then the
> +   containing object would implicitly get GTY((user)), which would
> +   prevent us from instantiating freelists as global objects.
> +   Although this way we can create freelist global objects, they're
> +   such thin wrappers that instantiating temporaries at every use
> +   loses nothing and saves permanent storage for the freelist object.
> +
> +   Member functions next, anew, poison and reinit have default
> +   implementations that work for most of the types we're interested
> +   in, but if they don't work for some type, they should be explicitly
> +   specialized.  See the comments before them for requirements, and
> +   the example specializations for the tree_list_freelist.  */
> +template <typename T>
> +class freelist
> +{
> +  /* Return the next object in a chain.  We could just do type
> +     punning, but if we access the object with its underlying type, we
> +     avoid strict-aliasing trouble.  This needs only work between
> +     poison and reinit.  */
> +  static T *&next (T *obj) { return obj->next; }
> +
> +  /* Return a newly allocated, uninitialized or minimally-initialized
> +     object of type T.  Any initialization performed by anew should
> +     either remain across the life of the object and the execution of
> +     poison, or be redone by reinit.  */
> +  static T *anew () { return ggc_alloc<T> (); }
> +
> +  /* Optionally scribble all over the bits holding the object, so that
> +     they become (mostly?) uninitialized memory.  This is called while
> +     preparing to make the object part of the free list.  */
> +  static void poison (T *obj) {
> +    T *p ATTRIBUTE_UNUSED = obj;
> +    T **q ATTRIBUTE_UNUSED = &next (obj);
> +
> +#ifdef ENABLE_GC_CHECKING
> +    /* Poison the data, to indicate the data is garbage.  */
> +    VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (p, sizeof (*p)));
> +    memset (p, 0xa5, sizeof (*p));
> +#endif
> +    /* Let valgrind know the object is free.  */
> +    VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (p, sizeof (*p)));
> +
> +    /* Let valgrind know the next portion of the object is available,
> +       but uninitialized.  */
> +    VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (q, sizeof (*q)));
> +  }
> +
> +  /* Bring an object that underwent at least one lifecycle after anew
> +     and before the most recent free and poison, back to a usable
> +     state, reinitializing whatever is needed for it to be
> +     functionally equivalent to an object just allocated and returned
> +     by anew.  This may poison or clear the next field, used by
> +     freelist housekeeping after poison was called.  */
> +  static void reinit (T *obj) {
> +    T **q ATTRIBUTE_UNUSED = &next (obj);
> +
> +#ifdef ENABLE_GC_CHECKING
> +    memset (q, 0xa5, sizeof (*q));
> +#endif
> +    /* Let valgrind know the entire object is available, but
> +       uninitialized.  */
> +    VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (obj, sizeof (*obj)));
> +  }
> +
> +  /* Reference a GTY-deletable pointer that points to the first object
> +     in the free list proper.  */
> +  T *&head;
> +public:
> +  /* Construct a freelist object chaining objects off of HEAD.  */
> +  freelist (T *&head) : head(head) {}
> +
> +  /* Add OBJ to the free object list.  The former head becomes OBJ's
> +     successor.  */
> +  void free (T *obj)
> +  {
> +    poison (obj);
> +    next (obj) = head;
> +    head = obj;
> +  }
> +
> +  /* Take an object from the free list, if one is available, or
> +     allocate a new one.  Objects taken from the free list should be
> +     regarded as filled with garbage, except for bits that are
> +     configured to be preserved across free and alloc.  */
> +  T *alloc ()
> +  {
> +    if (head)
> +      {
> +       T *obj = head;
> +       head = next (head);
> +       reinit (obj);
> +       return obj;
> +      }
> +    else
> +      return anew ();
> +  }
> +};
> +
> +/* Explicitly specialize the interfaces for freelist<tree_node>: we
> +   want to allocate a TREE_LIST using the usual interface, and ensure
> +   TREE_CHAIN remains functional.  Alas, we have to duplicate a bit of
> +   build_tree_list logic in reinit, so this could go out of sync.  */
> +template <>
> +inline tree &
> +freelist<tree_node>::next (tree obj) {
> +  return TREE_CHAIN (obj);
> +}
> +template <>
> +inline tree
> +freelist<tree_node>::anew () {
> +  return build_tree_list (NULL, NULL);
> +}
> +template <>
> +inline void
> +freelist<tree_node>::poison (tree obj ATTRIBUTE_UNUSED) {
> +  int size ATTRIBUTE_UNUSED = sizeof (tree_list);
> +  tree p ATTRIBUTE_UNUSED = obj;
> +  tree_base *b ATTRIBUTE_UNUSED = &obj->base;
> +  tree *q ATTRIBUTE_UNUSED = &next (obj);
> +
> +#ifdef ENABLE_GC_CHECKING
> +  gcc_checking_assert (TREE_CODE (obj) == TREE_LIST);
> +
> +  /* Poison the data, to indicate the data is garbage.  */
> +  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (p, size));
> +  memset (p, 0xa5, size);
> +#endif
> +  /* Let valgrind know the object is free.  */
> +  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (p, size));
> +  /* But we still want to use the TREE_CODE and TREE_CHAIN parts.  */
> +  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (b, sizeof (*b)));
> +  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (q, sizeof (*q)));
> +
> +#ifdef ENABLE_GC_CHECKING
> +  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (b, sizeof (*b)));
> +  /* Keep TREE_CHAIN functional.  */
> +  TREE_SET_CODE (obj, TREE_LIST);
> +#else
> +  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (b, sizeof (*b)));
> +#endif
> +}
> +template <>
> +inline void
> +freelist<tree_node>::reinit (tree obj ATTRIBUTE_UNUSED) {
> +  tree_base *b ATTRIBUTE_UNUSED = &obj->base;
> +
> +#ifdef ENABLE_GC_CHECKING
> +  gcc_checking_assert (TREE_CODE (obj) == TREE_LIST);
> +  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (obj, sizeof
> (tree_list)));
> +  memset (obj, 0, sizeof (tree_list));
> +#endif
> +
> +  /* Let valgrind know the entire object is available, but
> +     uninitialized.  */
> +  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (obj, sizeof
> (tree_list)));
> +
> +#ifdef ENABLE_GC_CHECKING
> +  TREE_SET_CODE (obj, TREE_LIST);
> +#else
> +  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (b, sizeof (*b)));
> +#endif
> +}
> +
> +/* Point to the first object in the TREE_LIST freelist.  */
> +static GTY((deletable)) tree tree_list_freelist_head;
> +/* Return the/an actual TREE_LIST freelist.  */
> +static inline freelist<tree_node>
> +tree_list_freelist () {
> +  return tree_list_freelist_head;
> +}
> +
> +/* Point to the first object in the tinst_level freelist.  */
> +static GTY((deletable)) tinst_level *tinst_level_freelist_head;
> +/* Return the/an actual tinst_level freelist.  */
> +static inline freelist<tinst_level>
> +tinst_level_freelist () {
> +  return tinst_level_freelist_head;
> +}
> +
> +/* Point to the first object in the pending_template freelist.  */
> +static GTY((deletable)) pending_template *pending_template_freelist_head;
> +/* Return the/an actual pending_template freelist.  */
> +static inline freelist<pending_template>
> +pending_template_freelist () {
> +  return pending_template_freelist_head;
> +}
> +
> +/* Build the TREE_LIST object out of a split list, store it
> +   permanently, and return it.  */
> +tree
> +tinst_level::to_list ()
> +{
> +  gcc_assert (split_list_p ());
> +  tree ret = tree_list_freelist ().alloc ();
> +  TREE_PURPOSE (ret) = tldcl;
> +  TREE_VALUE (ret) = targs;
> +  tldcl = ret;
> +  targs = NULL;
> +  gcc_assert (tree_list_p ());
> +  return ret;
> +}
> +
> +/* Increment OBJ's refcount.  */
> +static tinst_level *
> +inc_refcount_use (tinst_level *obj) {
> +  if (obj)
> +    {
> +      ++obj->refcount;
> +      gcc_assert (obj->refcount != 0);
> +    }
> +  return obj;
> +}
> +
> +/* Decrement OBJ's refcount.  If it reaches zero, release OBJ's DECL
> +   and OBJ, and start over with the tinst_level object that used to be
> +   referenced by OBJ's NEXT.  */
> +static void
> +dec_refcount_use (tinst_level *obj) {
> +  while (obj && !--obj->refcount)
> +    {
> +      gcc_assert (obj->refcount+1 != 0);
> +      tinst_level *next = obj->next;
> +      if (obj->list_p () && obj->get_decl_maybe ())
> +       tree_list_freelist ().free (obj->get_node ());
> +      tinst_level_freelist ().free (obj);
> +      obj = next;
> +    }
> +}
> +
> +/* Modify PTR so that it points to OBJ, adjusting the refcounts of OBJ
> +   and of the former PTR.  Omitting the second argument is equivalent
> +   to passing (T*)NULL; this is allowed because passing the
> +   zero-valued integral constant NULL confuses type deduction and/or
> +   overload resolution.  */
> +template <typename T>
> +static void
> +set_refcount_ptr (T *& ptr, T *obj = NULL) {
> +  T *save = ptr;
> +  ptr = inc_refcount_use (obj);
> +  dec_refcount_use (save);
> +}
> +
>  static void
>  add_pending_template (tree d)
>  {
> @@ -8746,14 +8992,17 @@ add_pending_template (tree d)
>    /* We are called both from instantiate_decl, where we've already had a
>       tinst_level pushed, and instantiate_template, where we haven't.
>       Compensate.  */
> -  level = !current_tinst_level || current_tinst_level->decl != d;
> +  gcc_assert (TREE_CODE (d) != TREE_LIST);
> +  level = !current_tinst_level
> +    || current_tinst_level->get_decl_maybe () != d;
>
>    if (level)
>      push_tinst_level (d);
>
> -  pt = ggc_alloc<pending_template> ();
> +  pt = pending_template_freelist ().alloc ();
>    pt->next = NULL;
> -  pt->tinst = current_tinst_level;
> +  pt->tinst = NULL;
> +  set_refcount_ptr (pt->tinst, current_tinst_level);
>    if (last_pending_template)
>      last_pending_template->next = pt;
>    else
> @@ -9810,7 +10059,7 @@ uses_outer_template_parms (tree decl)
>  static inline bool
>  neglectable_inst_p (tree d)
>  {
> -  return (DECL_P (d)
> +  return (d && DECL_P (d)
>           && !undeduced_auto_decl (d)
>           && !(TREE_CODE (d) == FUNCTION_DECL ? DECL_DECLARED_CONSTEXPR_P
> (d)
>                : decl_maybe_constant_var_p (d)));
> @@ -9828,7 +10077,7 @@ limit_bad_template_recursion (tree decl)
>      return false;
>
>    for (; lev; lev = lev->next)
> -    if (neglectable_inst_p (lev->decl))
> +    if (neglectable_inst_p (lev->get_decl_maybe ()))
>        break;
>
>    return (lev && errs > lev->errors);
> @@ -9840,20 +10089,11 @@ int depth_reached;
>
>  static GTY(()) struct tinst_level *last_error_tinst_level;
>
> -/* We're starting to instantiate D; record the template instantiation
> context
> -   for diagnostics and to restore it later.  */
> -
> -bool
> -push_tinst_level (tree d)
> -{
> -  return push_tinst_level_loc (d, input_location);
> -}
> -
>  /* We're starting to instantiate D; record the template instantiation
> context
>     at LOC for diagnostics and to restore it later.  */
>
> -bool
> -push_tinst_level_loc (tree d, location_t loc)
> +static bool
> +push_tinst_level_loc (tree tldcl, tree targs, location_t loc)
>  {
>    struct tinst_level *new_level;
>
> @@ -9871,23 +10111,26 @@ push_tinst_level_loc (tree d, location_t loc)
>    /* If the current instantiation caused problems, don't let it
> instantiate
>       anything else.  Do allow deduction substitution and decls usable in
>       constant expressions.  */
> -  if (limit_bad_template_recursion (d))
> +  if (!targs && limit_bad_template_recursion (tldcl))
>      return false;
>
>    /* When not -quiet, dump template instantiations other than functions,
> since
>       announce_function will take care of those.  */
> -  if (!quiet_flag
> -      && TREE_CODE (d) != TREE_LIST
> -      && TREE_CODE (d) != FUNCTION_DECL)
> -    fprintf (stderr, " %s", decl_as_string (d, TFF_DECL_SPECIFIERS));
> -
> -  new_level = ggc_alloc<tinst_level> ();
> -  new_level->decl = d;
> +  if (!quiet_flag && !targs
> +      && TREE_CODE (tldcl) != TREE_LIST
> +      && TREE_CODE (tldcl) != FUNCTION_DECL)
> +    fprintf (stderr, " %s", decl_as_string (tldcl, TFF_DECL_SPECIFIERS));
> +
> +  new_level = tinst_level_freelist ().alloc ();
> +  new_level->tldcl = tldcl;
> +  new_level->targs = targs;
>    new_level->locus = loc;
>    new_level->errors = errorcount+sorrycount;
>    new_level->in_system_header_p = in_system_header_at (input_location);
> -  new_level->next = current_tinst_level;
> -  current_tinst_level = new_level;
> +  new_level->next = NULL;
> +  new_level->refcount = 0;
> +  set_refcount_ptr (new_level->next, current_tinst_level);
> +  set_refcount_ptr (current_tinst_level, new_level);
>
>    ++tinst_depth;
>    if (GATHER_STATISTICS && (tinst_depth > depth_reached))
> @@ -9896,6 +10139,34 @@ push_tinst_level_loc (tree d, location_t loc)
>    return true;
>  }
>
> +/* We're starting substitution of TMPL<ARGS>; record the template
> +   substitution context for diagnostics and to restore it later.  */
> +
> +static bool
> +push_tinst_level (tree tmpl, tree args)
> +{
> +  return push_tinst_level_loc (tmpl, args, input_location);
> +}
> +
> +/* We're starting to instantiate D; record INPUT_LOCATION and the
> +   template instantiation context for diagnostics and to restore it
> +   later.  */
> +
> +bool
> +push_tinst_level (tree d)
> +{
> +  return push_tinst_level_loc (d, input_location);
> +}
> +
> +/* Likewise, but record LOC as the program location.  */
> +
> +bool
> +push_tinst_level_loc (tree d, location_t loc)
> +{
> +  gcc_assert (TREE_CODE (d) != TREE_LIST);
> +  return push_tinst_level_loc (d, NULL, loc);
> +}
> +
>  /* We're done instantiating this template; return to the instantiation
>     context.  */
>
> @@ -9905,7 +10176,7 @@ pop_tinst_level (void)
>    /* Restore the filename and line number stashed away when we started
>       this instantiation.  */
>    input_location = current_tinst_level->locus;
> -  current_tinst_level = current_tinst_level->next;
> +  set_refcount_ptr (current_tinst_level, current_tinst_level->next);
>    --tinst_depth;
>  }
>
> @@ -9922,11 +10193,11 @@ reopen_tinst_level (struct tinst_level *level)
>    for (t = level; t; t = t->next)
>      ++tinst_depth;
>
> -  current_tinst_level = level;
> +  set_refcount_ptr (current_tinst_level, level);
>    pop_tinst_level ();
>    if (current_tinst_level)
>      current_tinst_level->errors = errorcount+sorrycount;
> -  return level->decl;
> +  return level->get_decl_maybe ();
>  }
>
>  /* Returns the TINST_LEVEL which gives the original instantiation
> @@ -18983,16 +19254,10 @@ instantiate_template (tree tmpl, tree orig_args,
> tsubst_flags_t complain)
>  static tree
>  instantiate_alias_template (tree tmpl, tree args, tsubst_flags_t complain)
>  {
> -  struct pending_template *old_last_pend = last_pending_template;
> -  struct tinst_level *old_error_tinst = last_error_tinst_level;
>    if (tmpl == error_mark_node || args == error_mark_node)
>      return error_mark_node;
> -  tree tinst = build_tree_list (tmpl, args);
> -  if (!push_tinst_level (tinst))
> -    {
> -      ggc_free (tinst);
> -      return error_mark_node;
> -    }
> +  if (!push_tinst_level (tmpl, args))
> +    return error_mark_node;
>
>    args =
>      coerce_innermost_template_parms (DECL_TEMPLATE_PARMS (tmpl),
> @@ -19002,11 +19267,6 @@ instantiate_alias_template (tree tmpl, tree args,
> tsubst_flags_t complain)
>
>    tree r = instantiate_template (tmpl, args, complain);
>    pop_tinst_level ();
> -  /* We can't free this if a pending_template entry or
> last_error_tinst_level
> -     is pointing at it.  */
> -  if (last_pending_template == old_last_pend
> -      && last_error_tinst_level == old_error_tinst)
> -    ggc_free (tinst);
>
>    return r;
>  }
> @@ -19096,15 +19356,12 @@ fn_type_unification (tree fn,
>    tsubst_flags_t complain = (explain_p ? tf_warning_or_error : tf_none);
>    bool ok;
>    static int deduction_depth;
> -  struct pending_template *old_last_pend = last_pending_template;
> -  struct tinst_level *old_error_tinst = last_error_tinst_level;
>
>    tree orig_fn = fn;
>    if (flag_new_inheriting_ctors)
>      fn = strip_inheriting_ctors (fn);
>
>    tree tparms = DECL_INNERMOST_TEMPLATE_PARMS (fn);
> -  tree tinst;
>    tree r = error_mark_node;
>
>    tree full_targs = targs;
> @@ -19130,7 +19387,6 @@ fn_type_unification (tree fn,
>       This is, of course, not reentrant.  */
>    if (excessive_deduction_depth)
>      return error_mark_node;
> -  tinst = build_tree_list (fn, NULL_TREE);
>    ++deduction_depth;
>
>    gcc_assert (TREE_CODE (fn) == TEMPLATE_DECL);
> @@ -19223,8 +19479,7 @@ fn_type_unification (tree fn,
>              }
>          }
>
> -      TREE_VALUE (tinst) = explicit_targs;
> -      if (!push_tinst_level (tinst))
> +      if (!push_tinst_level (fn, explicit_targs))
>         {
>           excessive_deduction_depth = true;
>           goto fail;
> @@ -19279,12 +19534,11 @@ fn_type_unification (tree fn,
>       callers must be ready to deal with unification failures in any
>       event.  */
>
> -  TREE_VALUE (tinst) = targs;
>    /* If we aren't explaining yet, push tinst context so we can see where
>       any errors (e.g. from class instantiations triggered by instantiation
>       of default template arguments) come from.  If we are explaining, this
>       context is redundant.  */
> -  if (!explain_p && !push_tinst_level (tinst))
> +  if (!explain_p && !push_tinst_level (fn, targs))
>      {
>        excessive_deduction_depth = true;
>        goto fail;
> @@ -19340,8 +19594,7 @@ fn_type_unification (tree fn,
>       the corresponding deduced argument values.  If the
>       substitution results in an invalid type, as described above,
>       type deduction fails.  */
> -  TREE_VALUE (tinst) = targs;
> -  if (!push_tinst_level (tinst))
> +  if (!push_tinst_level (fn, targs))
>      {
>        excessive_deduction_depth = true;
>        goto fail;
> @@ -19407,12 +19660,6 @@ fn_type_unification (tree fn,
>         excessive_deduction_depth = false;
>      }
>
> -  /* We can't free this if a pending_template entry or
> last_error_tinst_level
> -     is pointing at it.  */
> -  if (last_pending_template == old_last_pend
> -      && last_error_tinst_level == old_error_tinst)
> -    ggc_free (tinst);
> -
>    return r;
>  }
>
> @@ -22382,8 +22629,7 @@ get_partial_spec_bindings (tree tmpl, tree
> spec_tmpl, tree args)
>         return NULL_TREE;
>        }
>
> -  tree tinst = build_tree_list (spec_tmpl, deduced_args);
> -  if (!push_tinst_level (tinst))
> +  if (!push_tinst_level (spec_tmpl, deduced_args))
>      {
>        excessive_deduction_depth = true;
>        return NULL_TREE;
> @@ -23764,7 +24010,7 @@ instantiate_pending_templates (int retries)
>       to avoid infinite loop.  */
>    if (pending_templates && retries >= max_tinst_depth)
>      {
> -      tree decl = pending_templates->tinst->decl;
> +      tree decl = pending_templates->tinst->get_decl_maybe ();
>
>        fatal_error (input_location,
>                    "template instantiation depth exceeds maximum of %d"
> @@ -23827,16 +24073,21 @@ instantiate_pending_templates (int retries)
>             }
>
>           if (complete)
> -           /* If INSTANTIATION has been instantiated, then we don't
> -              need to consider it again in the future.  */
> -           *t = (*t)->next;
> +           {
> +             /* If INSTANTIATION has been instantiated, then we don't
> +                need to consider it again in the future.  */
> +             struct pending_template *drop = *t;
> +             *t = (*t)->next;
> +             set_refcount_ptr (drop->tinst);
> +             pending_template_freelist ().free (drop);
> +           }
>           else
>             {
>               last = *t;
>               t = &(*t)->next;
>             }
>           tinst_depth = 0;
> -         current_tinst_level = NULL;
> +         set_refcount_ptr (current_tinst_level);
>         }
>        last_pending_template = last;
>      }
> @@ -24084,7 +24335,7 @@ problematic_instantiation_changed (void)
>  void
>  record_last_problematic_instantiation (void)
>  {
> -  last_error_tinst_level = current_tinst_level;
> +  set_refcount_ptr (last_error_tinst_level, current_tinst_level);
>  }
>
>  struct tinst_level *
> @@ -24100,7 +24351,8 @@ bool
>  instantiating_current_function_p (void)
>  {
>    return (current_instantiation ()
> -         && current_instantiation ()->decl == current_function_decl);
> +         && (current_instantiation ()->get_decl_maybe ()
> +             == current_function_decl));
>  }
>
>  /* [temp.param] Check that template non-type parm TYPE is of an allowable
>
>
>
> Just FTR.  count tinst_level objs et al
>
> ---
>  gcc/cp/cp-tree.h |   50 ++++++++++++++++++++++++++++++++++++++++++++++++++
>  gcc/cp/pt.c      |   25 ++++++++++++++++++++++---
>  2 files changed, 72 insertions(+), 3 deletions(-)
>
> diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
> index e9d9bab879bc..38de9b600f0d 100644
> --- a/gcc/cp/cp-tree.h
> +++ b/gcc/cp/cp-tree.h
> @@ -5865,6 +5865,49 @@ struct cp_declarator {
>    } u;
>  };
>
> +  struct consctr {
> +    unsigned ctor, ctorl, dtor, dtorl, maxactive, maxactivel,
> +      lastmark, lastmarkl, longestseq, longestseql, maxcnt, reused;
> +    bool toreport;
> +    void operator++() {
> +      toreport = true;
> +      ctor++;
> +      maxactive = MAX (maxactive, ctor - dtor);
> +      longestseq = MAX (longestseq, ctor - lastmark);
> +    }
> +    void operator--() { toreport = true; dtor++; }
> +    void operator+() {
> +      toreport = true;
> +      ctorl++;
> +      maxactivel = MAX (maxactivel, ctorl - dtorl);
> +      longestseql = MAX (longestseql, ctorl - lastmarkl);
> +    }
> +    void operator-() {
> +      toreport = true;
> +      dtorl++;
> +    }
> +    void operator*() { report(); lastmark = ctor; lastmarkl = ctorl; }
> +    void operator=(unsigned i) {
> +      if (i > maxcnt)
> +       toreport = true;
> +      maxcnt = MAX (maxcnt, i);
> +    }
> +    void operator!() {
> +      toreport = true;
> +      reused++;
> +    }
> +    ~consctr() { report (); }
> +    void report() {
> +      if (toreport) {
> +       printf ("TINST: ctor %u dtor %u max %u end %u long %u LST: ctor %u
> dtor %u max %u end %u long %u REFS: %u reused: %u\n",
> +               ctor, dtor, maxactive, ctor - dtor, longestseq,
> +               ctorl, dtorl, maxactivel, ctorl - dtorl, longestseql,
> +               maxcnt, reused);
> +       toreport = false;
> +      }
> +    }
> +  };
> +
>  /* A level of template instantiation.  */
>  struct GTY((chain_next ("%h.next"))) tinst_level {
>    /* The immediately deeper level in the chain.  */
> @@ -5932,6 +5975,13 @@ struct GTY((chain_next ("%h.next"))) tinst_level {
>
>    /* Count references to this object.  */
>    unsigned char refcount;
> +
> +  static struct consctr consctr;
> +
> +  static int resetctr () {
> +    *consctr;
> +    return 1;
> +  }
>  };
>
>  bool decl_spec_seq_has_spec_p (const cp_decl_specifier_seq *,
> cp_decl_spec);
> diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
> index 75ed73890c4f..4db3bd49bf3f 100644
> --- a/gcc/cp/pt.c
> +++ b/gcc/cp/pt.c
> @@ -8909,6 +8909,7 @@ tinst_level::to_list ()
>    tldcl = ret;
>    targs = NULL;
>    gcc_assert (tree_list_p ());
> +  +consctr;
>    return ret;
>  }
>
> @@ -8917,7 +8918,7 @@ static tinst_level *
>  inc_refcount_use (tinst_level *obj) {
>    if (obj)
>      {
> -      ++obj->refcount;
> +      obj->consctr = ++obj->refcount;
>        gcc_assert (obj->refcount != 0);
>      }
>    return obj;
> @@ -8930,10 +8931,14 @@ static void
>  dec_refcount_use (tinst_level *obj) {
>    while (obj && !--obj->refcount)
>      {
> +      --obj->consctr;
>        gcc_assert (obj->refcount+1 != 0);
>        tinst_level *next = obj->next;
>        if (obj->list_p () && obj->get_decl_maybe ())
> -       tree_list_freelist ().free (obj->get_node ());
> +       {
> +         -obj->consctr;
> +         tree_list_freelist ().free (obj->get_node ());
> +       }
>        tinst_level_freelist ().free (obj);
>        obj = next;
>      }
> @@ -10062,7 +10067,14 @@ static int tinst_depth;
>  extern int max_tinst_depth;
>  int depth_reached;
>
> -static GTY(()) struct tinst_level *last_error_tinst_level;
> +static GTY(()) struct tinst_level * last_error_tinst_level;
> +
> +struct consctr tinst_level::consctr;
> +static hash_set<tinst_level *> used_ptrs;
> +
> +struct GTY(()) resetter {};
> +static GTY((length ("tinst_level::resetctr ()")))
> +  struct resetter *tinst_resetter;
>
>  /* We're starting to instantiate D; record the template instantiation
> context
>     at LOC for diagnostics and to restore it later.  */
> @@ -10096,6 +10108,9 @@ push_tinst_level_loc (tree tldcl, tree targs,
> location_t loc)
>        && TREE_CODE (tldcl) != FUNCTION_DECL)
>      fprintf (stderr, " %s", decl_as_string (tldcl, TFF_DECL_SPECIFIERS));
>
> +  if (!tinst_resetter)
> +    tinst_resetter = ggc_cleared_alloc<resetter>();
> +
>    new_level = tinst_level_freelist ().alloc ();
>    new_level->tldcl = tldcl;
>    new_level->targs = targs;
> @@ -10104,9 +10119,13 @@ push_tinst_level_loc (tree tldcl, tree targs,
> location_t loc)
>    new_level->in_system_header_p = in_system_header_at (input_location);
>    new_level->next = NULL;
>    new_level->refcount = 0;
> +  ++new_level->consctr;
>    set_refcount_ptr (new_level->next, current_tinst_level);
>    set_refcount_ptr (current_tinst_level, new_level);
>
> +  if (!used_ptrs.add (new_level))
> +    !tinst_level::consctr;
> +
>    ++tinst_depth;
>    if (GATHER_STATISTICS && (tinst_depth > depth_reached))
>      depth_reached = tinst_depth;
>
>
> --
> Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
> You must be the change you wish to see in the world. -- Gandhi
> Be Free! -- http://FSFLA.org/   FSF Latin America board member
> Free Software Evangelist|Red Hat Brasil GNU Toolchain Engineer
>
Alexandre Oliva April 16, 2018, 9:19 p.m. | #2
On Apr 16, 2018, Jason Merrill <jason@redhat.com> wrote:

> On Fri, Apr 13, 2018, 5:19 PM Alexandre Oliva <aoliva@redhat.com> wrote:
>> +  tree get_node () const {
>> +    if (!split_list_p ()) return tldcl;
>> +    else return const_cast <tinst_level *>(this)->to_list ();
>> +  }

> This looks like a dangerous violation of const correctness, since it does
> in fact modify the object.

Well...  We know the object's actual type is not const, since we
allocate all objects of this type from GCable memory.  Conceptually, the
object is not modified, we're just lazily performing an expensive
rearrangement of the internal representation that we would have done
upfront if we weren't trying to save that expense.  This would be a
perfect case for mutable, if only gengtype didn't get confused by it.


OTOH, we could drop a tiny amount of constification in error.c and avoid
the problem altogether, as in the following incremental patch:

 gcc/cp/cp-tree.h |    4 ++--
 gcc/cp/error.c   |    2 +-
 2 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index e9d9bab879bc..26a50ac136dd 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -5909,9 +5909,9 @@ struct GTY((chain_next ("%h.next"))) tinst_level {
   /* Return the original node; if it's a split list, make it a
      TREE_LIST first, so that it can be returned as a single tree
      object.  */
-  tree get_node () const {
+  tree get_node () {
     if (!split_list_p ()) return tldcl;
-    else return const_cast <tinst_level *>(this)->to_list ();
+    else return to_list ();
   }
 
   /* Return the original node if it's a DECL or a TREE_LIST, but do
diff --git a/gcc/cp/error.c b/gcc/cp/error.c
index 983ffdfedbb2..95b8b84f34ab 100644
--- a/gcc/cp/error.c
+++ b/gcc/cp/error.c
@@ -3475,7 +3475,7 @@ print_instantiation_full_context (diagnostic_context *context)
 
 static void
 print_instantiation_partial_context_line (diagnostic_context *context,
-					  const struct tinst_level *t,
+					  struct tinst_level *t,
 					  location_t loc, bool recursive_p)
 {
   if (loc == UNKNOWN_LOCATION)


Does this incremental change make it ok (pending retesting), or should I
look into adding mutable support to gengtype, or something else?
Jason Merrill April 17, 2018, 12:05 a.m. | #3
On Mon, Apr 16, 2018, 3:20 PM Alexandre Oliva <aoliva@redhat.com> wrote:

> On Apr 16, 2018, Jason Merrill <jason@redhat.com> wrote:
>
> > On Fri, Apr 13, 2018, 5:19 PM Alexandre Oliva <aoliva@redhat.com> wrote:
> >> +  tree get_node () const {
> >> +    if (!split_list_p ()) return tldcl;
> >> +    else return const_cast <tinst_level *>(this)->to_list ();
> >> +  }
>
> > This looks like a dangerous violation of const correctness, since it does
> > in fact modify the object.
>
> Well...  We know the object's actual type is not const, since we
> allocate all objects of this type from GCable memory.  Conceptually, the
> object is not modified, we're just lazily performing an expensive
> rearrangement of the internal representation that we would have done
> upfront if we weren't trying to save that expense.  This would be a
> perfect case for mutable, if only gengtype didn't get confused by it.
>
>
> OTOH, we could drop a tiny amount of constification in error.c and avoid
> the problem altogether, as in the following incremental patch:
>
>  gcc/cp/cp-tree.h |    4 ++--
>  gcc/cp/error.c   |    2 +-
>  2 files changed, 3 insertions(+), 3 deletions(-)
>
> diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
> index e9d9bab879bc..26a50ac136dd 100644
> --- a/gcc/cp/cp-tree.h
> +++ b/gcc/cp/cp-tree.h
> @@ -5909,9 +5909,9 @@ struct GTY((chain_next ("%h.next"))) tinst_level {
>    /* Return the original node; if it's a split list, make it a
>       TREE_LIST first, so that it can be returned as a single tree
>       object.  */
> -  tree get_node () const {
> +  tree get_node () {
>      if (!split_list_p ()) return tldcl;
> -    else return const_cast <tinst_level *>(this)->to_list ();
> +    else return to_list ();
>    }
>
>    /* Return the original node if it's a DECL or a TREE_LIST, but do
> diff --git a/gcc/cp/error.c b/gcc/cp/error.c
> index 983ffdfedbb2..95b8b84f34ab 100644
> --- a/gcc/cp/error.c
> +++ b/gcc/cp/error.c
> @@ -3475,7 +3475,7 @@ print_instantiation_full_context (diagnostic_context
> *context)
>
>  static void
>  print_instantiation_partial_context_line (diagnostic_context *context,
> -                                         const struct tinst_level *t,
> +                                         struct tinst_level *t,
>                                           location_t loc, bool recursive_p)
>  {
>    if (loc == UNKNOWN_LOCATION)
>
>
> Does this incremental change make it ok (pending retesting), or should I
> look into adding mutable support to gengtype, or something else?
>

This change looks good. One other nit: get_decl_maybe can also return a
list, so the name seems wrong. And this line

+      if (obj->list_p () && obj->get_decl_maybe ())

could be

  if (tree_list_p ())

I think, and then get_decl_maybe wouldn't need to return a list anymore?

Jason
Alexandre Oliva April 17, 2018, 1:45 a.m. | #4
On Apr 16, 2018, Jason Merrill <jason@redhat.com> wrote:

> This change looks good. One other nit: get_decl_maybe can also return a
> list, so the name seems wrong.

Uhh, it's "give me the decl if you got one, but it's ok if you give me a
list" (the latter is what makes it _maybe).  It replaces what used to be
called just 'decl'.  Maybe wrong is a bit too strong, but...  do you
have any suggestion?  get_decl_or_tree_list_but_dont_build_the_list is a
bit too long IMHO ;-)

> And this line

> +      if (obj->list_p () && obj->get_decl_maybe ())

> could be

>   if (tree_list_p ())

It could if we made tree_list_p public.  It's private because that's an
internal implementation detail, though it's one that happens to leak
through the combination of calls above.

> I think, and then get_decl_maybe wouldn't need to return a list anymore?

That's backwards.  It doesn't need to; the point of get_decl_maybe is to
make as simple a test as possible and return fast, without having to
look in the "decl" to find out what it is.  I even considered making it
return tldcl unconditionally, but that would just cause trouble for the
various pieces of code that used to compare tinst_level::decls for
equality, and would now get false positives out of split lists sharing
the same tmpl decl in the first element of the list.  Testing targs in
get_decl_maybe to avoid returning a partial former decl rules out this
case and is as cheap as it gets.

Do we need more detailed comments, besides a name change?
Jason Merrill April 17, 2018, 3:30 a.m. | #5
On Mon, Apr 16, 2018 at 9:45 PM, Alexandre Oliva <aoliva@redhat.com> wrote:
> On Apr 16, 2018, Jason Merrill <jason@redhat.com> wrote:
>
>> This change looks good. One other nit: get_decl_maybe can also return a
>> list, so the name seems wrong.
>
> Uhh, it's "give me the decl if you got one, but it's ok if you give me a
> list" (the latter is what makes it _maybe).  It replaces what used to be
> called just 'decl'.  Maybe wrong is a bit too strong, but...  do you
> have any suggestion?  get_decl_or_tree_list_but_dont_build_the_list is a
> bit too long IMHO ;-)

I was thinking maybe_get_node, since it returns either the same as
get_node or null (and maybe usually comes early in a function name).

>> And this line
>
>> +      if (obj->list_p () && obj->get_decl_maybe ())
>
>> could be
>
>>   if (tree_list_p ())
>
> It could if we made tree_list_p public.  It's private because that's an
> internal implementation detail, though it's one that happens to leak
> through the combination of calls above.

I suppose better would be for

+      if (obj->list_p () && obj->get_decl_maybe ())
+       tree_list_freelist ().free (obj->get_node ());

to be e.g.

  obj->maybe_free_list();

Or put the list handling in a destructor for tinst_level, and have
freelist use placement new and explicit destruction.

Jason
Alexandre Oliva April 17, 2018, 5:25 p.m. | #6
On Apr 17, 2018, Jason Merrill <jason@redhat.com> wrote:

> I was thinking maybe_get_node

'k

> I suppose better would be for

> +      if (obj->list_p () && obj->get_decl_maybe ())
> +       tree_list_freelist ().free (obj->get_node ());

> to be e.g.

> obj-> maybe_free_list();

Any objections to making dec_refcount_use a friend of tinst_level's?
Otherwise, I'd rather add a free() member function (or maybe static
member function) to free both the TREE_LIST and the tinst_level objects.
Otherwise, maybe_free_list would leave the object in an inconsistent
state, pointing to a freed TREE_LIST, or it could undo to_list, though
it's not supposed to be reversible in the lifetime of the object.
free()ing the entire object along with the TREE_LIST addresses that
concern.  But then, dec_refcount_use does that and then some...

> Or put the list handling in a destructor for tinst_level, and have
> freelist use placement new and explicit destruction.

A destructor would enable finalization in GGC, I don't think we want to
do that.
Jason Merrill April 18, 2018, 1:19 a.m. | #7
On Tue, Apr 17, 2018, 10:25 AM Alexandre Oliva <aoliva@redhat.com> wrote:

> On Apr 17, 2018, Jason Merrill <jason@redhat.com> wrote:
>
> > I was thinking maybe_get_node
>
> 'k
>
> > I suppose better would be for
>
> > +      if (obj->list_p () && obj->get_decl_maybe ())
> > +       tree_list_freelist ().free (obj->get_node ());
>
> > to be e.g.
>
> > obj-> maybe_free_list();
>
> Any objections to making dec_refcount_use a friend of tinst_level's?
> Otherwise, I'd rather add a free() member function (or maybe static
> member function) to free both the TREE_LIST and the tinst_level objects.
>

Either of those sounds fine.

Otherwise, maybe_free_list would leave the object in an inconsistent
> state, pointing to a freed TREE_LIST, or it could undo to_list, though
> it's not supposed to be reversible in the lifetime of the object.
> free()ing the entire object along with the TREE_LIST addresses that
> concern.  But then, dec_refcount_use does that and then some...
>
> > Or put the list handling in a destructor for tinst_level, and have
> > freelist use placement new and explicit destruction.
>
> A destructor would enable finalization in GGC, I don't think we want to
> do that.
>
> --
> Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
> You must be the change you wish to see in the world. -- Gandhi
> Be Free! -- http://FSFLA.org/   FSF Latin America board member
> Free Software Evangelist|Red Hat Brasil GNU Toolchain Engineer
>
Alexandre Oliva April 18, 2018, 3:29 a.m. | #8
On Apr 17, 2018, Jason Merrill <jason@redhat.com> wrote:

>> Any objections to making dec_refcount_use a friend of tinst_level's?
>> Otherwise, I'd rather add a free() member function (or maybe static
>> member function) to free both the TREE_LIST and the tinst_level objects.

> Either of those sounds fine.

Here's the additional incremental patch I'm testing.

I've added a number of line breaks before opening braces in function
definitions, that had escaped my attention in the initial patch
submission.

---
 gcc/cp/cp-tree.h |    5 ++++-
 gcc/cp/mangle.c  |    2 +-
 gcc/cp/pt.c      |   56 ++++++++++++++++++++++++++++++++++++------------------
 3 files changed, 42 insertions(+), 21 deletions(-)

diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 26a50ac136dd..7031c79b35db 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -5903,6 +5903,9 @@ struct GTY((chain_next ("%h.next"))) tinst_level {
   tree to_list ();
 
  public:
+  /* Release storage for OBJ and node, if it's a TREE_LIST.  */
+  static void free(tinst_level *obj);
+
   /* Return TRUE iff the original node is a list, split or not.  */
   bool list_p () const { return !not_list_p (); }
 
@@ -5916,7 +5919,7 @@ struct GTY((chain_next ("%h.next"))) tinst_level {
 
   /* Return the original node if it's a DECL or a TREE_LIST, but do
      NOT convert a split list to a TREE_LIST: return NULL instead.  */
-  tree get_decl_maybe () const {
+  tree maybe_get_node () const {
     if (!split_list_p ()) return tldcl;
     else return NULL_TREE;
   }
diff --git a/gcc/cp/mangle.c b/gcc/cp/mangle.c
index 940f7ed87e20..2f65709d7d8c 100644
--- a/gcc/cp/mangle.c
+++ b/gcc/cp/mangle.c
@@ -3777,7 +3777,7 @@ mangle_decl_string (const tree decl)
   if (DECL_LANG_SPECIFIC (decl) && DECL_USE_TEMPLATE (decl))
     {
       struct tinst_level *tl = current_instantiation ();
-      if ((!tl || tl->get_decl_maybe () != decl)
+      if ((!tl || tl->maybe_get_node () != decl)
 	  && push_tinst_level (decl))
 	{
 	  template_p = true;
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index 2442f07095ca..79563dfa5334 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -50,7 +50,8 @@ typedef int (*tree_fn_t) (tree, void*);
 /* The PENDING_TEMPLATES is a TREE_LIST of templates whose
    instantiations have been deferred, either because their definitions
    were not yet available, or because we were putting off doing the work.  */
-struct GTY ((chain_next ("%h.next"))) pending_template {
+struct GTY ((chain_next ("%h.next"))) pending_template
+{
   struct pending_template *next;
   struct tinst_level *tinst;
 };
@@ -8839,17 +8840,20 @@ public:
    build_tree_list logic in reinit, so this could go out of sync.  */
 template <>
 inline tree &
-freelist<tree_node>::next (tree obj) {
+freelist<tree_node>::next (tree obj)
+{
   return TREE_CHAIN (obj);
 }
 template <>
 inline tree
-freelist<tree_node>::anew () {
+freelist<tree_node>::anew ()
+{
   return build_tree_list (NULL, NULL);
 }
 template <>
 inline void
-freelist<tree_node>::poison (tree obj ATTRIBUTE_UNUSED) {
+freelist<tree_node>::poison (tree obj ATTRIBUTE_UNUSED)
+{
   int size ATTRIBUTE_UNUSED = sizeof (tree_list);
   tree p ATTRIBUTE_UNUSED = obj;
   tree_base *b ATTRIBUTE_UNUSED = &obj->base;
@@ -8878,7 +8882,8 @@ freelist<tree_node>::poison (tree obj ATTRIBUTE_UNUSED) {
 }
 template <>
 inline void
-freelist<tree_node>::reinit (tree obj ATTRIBUTE_UNUSED) {
+freelist<tree_node>::reinit (tree obj ATTRIBUTE_UNUSED)
+{
   tree_base *b ATTRIBUTE_UNUSED = &obj->base;
 
 #ifdef ENABLE_GC_CHECKING
@@ -8902,7 +8907,8 @@ freelist<tree_node>::reinit (tree obj ATTRIBUTE_UNUSED) {
 static GTY((deletable)) tree tree_list_freelist_head;
 /* Return the/an actual TREE_LIST freelist.  */
 static inline freelist<tree_node>
-tree_list_freelist () {
+tree_list_freelist ()
+{
   return tree_list_freelist_head;
 }
 
@@ -8910,7 +8916,8 @@ tree_list_freelist () {
 static GTY((deletable)) tinst_level *tinst_level_freelist_head;
 /* Return the/an actual tinst_level freelist.  */
 static inline freelist<tinst_level>
-tinst_level_freelist () {
+tinst_level_freelist ()
+{
   return tinst_level_freelist_head;
 }
 
@@ -8918,7 +8925,8 @@ tinst_level_freelist () {
 static GTY((deletable)) pending_template *pending_template_freelist_head;
 /* Return the/an actual pending_template freelist.  */
 static inline freelist<pending_template>
-pending_template_freelist () {
+pending_template_freelist ()
+{
   return pending_template_freelist_head;
 }
 
@@ -8939,7 +8947,8 @@ tinst_level::to_list ()
 
 /* Increment OBJ's refcount.  */
 static tinst_level *
-inc_refcount_use (tinst_level *obj) {
+inc_refcount_use (tinst_level *obj)
+{
   if (obj)
     {
       ++obj->refcount;
@@ -8948,18 +8957,26 @@ inc_refcount_use (tinst_level *obj) {
   return obj;
 }
 
+/* Release storage for OBJ and node, if it's a TREE_LIST.  */
+void
+tinst_level::free (tinst_level *obj)
+{
+  if (obj->tree_list_p ())
+    tree_list_freelist ().free (obj->get_node ());
+  tinst_level_freelist ().free (obj);
+}
+
 /* Decrement OBJ's refcount.  If it reaches zero, release OBJ's DECL
    and OBJ, and start over with the tinst_level object that used to be
    referenced by OBJ's NEXT.  */
 static void
-dec_refcount_use (tinst_level *obj) {
+dec_refcount_use (tinst_level *obj)
+{
   while (obj && !--obj->refcount)
     {
       gcc_assert (obj->refcount+1 != 0);
       tinst_level *next = obj->next;
-      if (obj->list_p () && obj->get_decl_maybe ())
-	tree_list_freelist ().free (obj->get_node ());
-      tinst_level_freelist ().free (obj);
+      tinst_level::free (obj);
       obj = next;
     }
 }
@@ -8971,7 +8988,8 @@ dec_refcount_use (tinst_level *obj) {
    overload resolution.  */
 template <typename T>
 static void
-set_refcount_ptr (T *& ptr, T *obj = NULL) {
+set_refcount_ptr (T *& ptr, T *obj = NULL)
+{
   T *save = ptr;
   ptr = inc_refcount_use (obj);
   dec_refcount_use (save);
@@ -8994,7 +9012,7 @@ add_pending_template (tree d)
      Compensate.  */
   gcc_assert (TREE_CODE (d) != TREE_LIST);
   level = !current_tinst_level
-    || current_tinst_level->get_decl_maybe () != d;
+    || current_tinst_level->maybe_get_node () != d;
 
   if (level)
     push_tinst_level (d);
@@ -10077,7 +10095,7 @@ limit_bad_template_recursion (tree decl)
     return false;
 
   for (; lev; lev = lev->next)
-    if (neglectable_inst_p (lev->get_decl_maybe ()))
+    if (neglectable_inst_p (lev->maybe_get_node ()))
       break;
 
   return (lev && errs > lev->errors);
@@ -10197,7 +10215,7 @@ reopen_tinst_level (struct tinst_level *level)
   pop_tinst_level ();
   if (current_tinst_level)
     current_tinst_level->errors = errorcount+sorrycount;
-  return level->get_decl_maybe ();
+  return level->maybe_get_node ();
 }
 
 /* Returns the TINST_LEVEL which gives the original instantiation
@@ -24010,7 +24028,7 @@ instantiate_pending_templates (int retries)
      to avoid infinite loop.  */
   if (pending_templates && retries >= max_tinst_depth)
     {
-      tree decl = pending_templates->tinst->get_decl_maybe ();
+      tree decl = pending_templates->tinst->maybe_get_node ();
 
       fatal_error (input_location,
 		   "template instantiation depth exceeds maximum of %d"
@@ -24351,7 +24369,7 @@ bool
 instantiating_current_function_p (void)
 {
   return (current_instantiation ()
-	  && (current_instantiation ()->get_decl_maybe ()
+	  && (current_instantiation ()->maybe_get_node ()
 	      == current_function_decl));
 }
Jason Merrill April 18, 2018, 4:59 a.m. | #9
Ok, thanks.

On Tue, Apr 17, 2018, 9:29 PM Alexandre Oliva <aoliva@redhat.com> wrote:

> On Apr 17, 2018, Jason Merrill <jason@redhat.com> wrote:
>
> >> Any objections to making dec_refcount_use a friend of tinst_level's?
> >> Otherwise, I'd rather add a free() member function (or maybe static
> >> member function) to free both the TREE_LIST and the tinst_level objects.
>
> > Either of those sounds fine.
>
> Here's the additional incremental patch I'm testing.
>
> I've added a number of line breaks before opening braces in function
> definitions, that had escaped my attention in the initial patch
> submission.
>
> ---
>  gcc/cp/cp-tree.h |    5 ++++-
>  gcc/cp/mangle.c  |    2 +-
>  gcc/cp/pt.c      |   56
> ++++++++++++++++++++++++++++++++++++------------------
>  3 files changed, 42 insertions(+), 21 deletions(-)
>
> diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
> index 26a50ac136dd..7031c79b35db 100644
> --- a/gcc/cp/cp-tree.h
> +++ b/gcc/cp/cp-tree.h
> @@ -5903,6 +5903,9 @@ struct GTY((chain_next ("%h.next"))) tinst_level {
>    tree to_list ();
>
>   public:
> +  /* Release storage for OBJ and node, if it's a TREE_LIST.  */
> +  static void free(tinst_level *obj);
> +
>    /* Return TRUE iff the original node is a list, split or not.  */
>    bool list_p () const { return !not_list_p (); }
>
> @@ -5916,7 +5919,7 @@ struct GTY((chain_next ("%h.next"))) tinst_level {
>
>    /* Return the original node if it's a DECL or a TREE_LIST, but do
>       NOT convert a split list to a TREE_LIST: return NULL instead.  */
> -  tree get_decl_maybe () const {
> +  tree maybe_get_node () const {
>      if (!split_list_p ()) return tldcl;
>      else return NULL_TREE;
>    }
> diff --git a/gcc/cp/mangle.c b/gcc/cp/mangle.c
> index 940f7ed87e20..2f65709d7d8c 100644
> --- a/gcc/cp/mangle.c
> +++ b/gcc/cp/mangle.c
> @@ -3777,7 +3777,7 @@ mangle_decl_string (const tree decl)
>    if (DECL_LANG_SPECIFIC (decl) && DECL_USE_TEMPLATE (decl))
>      {
>        struct tinst_level *tl = current_instantiation ();
> -      if ((!tl || tl->get_decl_maybe () != decl)
> +      if ((!tl || tl->maybe_get_node () != decl)
>           && push_tinst_level (decl))
>         {
>           template_p = true;
> diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
> index 2442f07095ca..79563dfa5334 100644
> --- a/gcc/cp/pt.c
> +++ b/gcc/cp/pt.c
> @@ -50,7 +50,8 @@ typedef int (*tree_fn_t) (tree, void*);
>  /* The PENDING_TEMPLATES is a TREE_LIST of templates whose
>     instantiations have been deferred, either because their definitions
>     were not yet available, or because we were putting off doing the
> work.  */
> -struct GTY ((chain_next ("%h.next"))) pending_template {
> +struct GTY ((chain_next ("%h.next"))) pending_template
> +{
>    struct pending_template *next;
>    struct tinst_level *tinst;
>  };
> @@ -8839,17 +8840,20 @@ public:
>     build_tree_list logic in reinit, so this could go out of sync.  */
>  template <>
>  inline tree &
> -freelist<tree_node>::next (tree obj) {
> +freelist<tree_node>::next (tree obj)
> +{
>    return TREE_CHAIN (obj);
>  }
>  template <>
>  inline tree
> -freelist<tree_node>::anew () {
> +freelist<tree_node>::anew ()
> +{
>    return build_tree_list (NULL, NULL);
>  }
>  template <>
>  inline void
> -freelist<tree_node>::poison (tree obj ATTRIBUTE_UNUSED) {
> +freelist<tree_node>::poison (tree obj ATTRIBUTE_UNUSED)
> +{
>    int size ATTRIBUTE_UNUSED = sizeof (tree_list);
>    tree p ATTRIBUTE_UNUSED = obj;
>    tree_base *b ATTRIBUTE_UNUSED = &obj->base;
> @@ -8878,7 +8882,8 @@ freelist<tree_node>::poison (tree obj
> ATTRIBUTE_UNUSED) {
>  }
>  template <>
>  inline void
> -freelist<tree_node>::reinit (tree obj ATTRIBUTE_UNUSED) {
> +freelist<tree_node>::reinit (tree obj ATTRIBUTE_UNUSED)
> +{
>    tree_base *b ATTRIBUTE_UNUSED = &obj->base;
>
>  #ifdef ENABLE_GC_CHECKING
> @@ -8902,7 +8907,8 @@ freelist<tree_node>::reinit (tree obj
> ATTRIBUTE_UNUSED) {
>  static GTY((deletable)) tree tree_list_freelist_head;
>  /* Return the/an actual TREE_LIST freelist.  */
>  static inline freelist<tree_node>
> -tree_list_freelist () {
> +tree_list_freelist ()
> +{
>    return tree_list_freelist_head;
>  }
>
> @@ -8910,7 +8916,8 @@ tree_list_freelist () {
>  static GTY((deletable)) tinst_level *tinst_level_freelist_head;
>  /* Return the/an actual tinst_level freelist.  */
>  static inline freelist<tinst_level>
> -tinst_level_freelist () {
> +tinst_level_freelist ()
> +{
>    return tinst_level_freelist_head;
>  }
>
> @@ -8918,7 +8925,8 @@ tinst_level_freelist () {
>  static GTY((deletable)) pending_template *pending_template_freelist_head;
>  /* Return the/an actual pending_template freelist.  */
>  static inline freelist<pending_template>
> -pending_template_freelist () {
> +pending_template_freelist ()
> +{
>    return pending_template_freelist_head;
>  }
>
> @@ -8939,7 +8947,8 @@ tinst_level::to_list ()
>
>  /* Increment OBJ's refcount.  */
>  static tinst_level *
> -inc_refcount_use (tinst_level *obj) {
> +inc_refcount_use (tinst_level *obj)
> +{
>    if (obj)
>      {
>        ++obj->refcount;
> @@ -8948,18 +8957,26 @@ inc_refcount_use (tinst_level *obj) {
>    return obj;
>  }
>
> +/* Release storage for OBJ and node, if it's a TREE_LIST.  */
> +void
> +tinst_level::free (tinst_level *obj)
> +{
> +  if (obj->tree_list_p ())
> +    tree_list_freelist ().free (obj->get_node ());
> +  tinst_level_freelist ().free (obj);
> +}
> +
>  /* Decrement OBJ's refcount.  If it reaches zero, release OBJ's DECL
>     and OBJ, and start over with the tinst_level object that used to be
>     referenced by OBJ's NEXT.  */
>  static void
> -dec_refcount_use (tinst_level *obj) {
> +dec_refcount_use (tinst_level *obj)
> +{
>    while (obj && !--obj->refcount)
>      {
>        gcc_assert (obj->refcount+1 != 0);
>        tinst_level *next = obj->next;
> -      if (obj->list_p () && obj->get_decl_maybe ())
> -       tree_list_freelist ().free (obj->get_node ());
> -      tinst_level_freelist ().free (obj);
> +      tinst_level::free (obj);
>        obj = next;
>      }
>  }
> @@ -8971,7 +8988,8 @@ dec_refcount_use (tinst_level *obj) {
>     overload resolution.  */
>  template <typename T>
>  static void
> -set_refcount_ptr (T *& ptr, T *obj = NULL) {
> +set_refcount_ptr (T *& ptr, T *obj = NULL)
> +{
>    T *save = ptr;
>    ptr = inc_refcount_use (obj);
>    dec_refcount_use (save);
> @@ -8994,7 +9012,7 @@ add_pending_template (tree d)
>       Compensate.  */
>    gcc_assert (TREE_CODE (d) != TREE_LIST);
>    level = !current_tinst_level
> -    || current_tinst_level->get_decl_maybe () != d;
> +    || current_tinst_level->maybe_get_node () != d;
>
>    if (level)
>      push_tinst_level (d);
> @@ -10077,7 +10095,7 @@ limit_bad_template_recursion (tree decl)
>      return false;
>
>    for (; lev; lev = lev->next)
> -    if (neglectable_inst_p (lev->get_decl_maybe ()))
> +    if (neglectable_inst_p (lev->maybe_get_node ()))
>        break;
>
>    return (lev && errs > lev->errors);
> @@ -10197,7 +10215,7 @@ reopen_tinst_level (struct tinst_level *level)
>    pop_tinst_level ();
>    if (current_tinst_level)
>      current_tinst_level->errors = errorcount+sorrycount;
> -  return level->get_decl_maybe ();
> +  return level->maybe_get_node ();
>  }
>
>  /* Returns the TINST_LEVEL which gives the original instantiation
> @@ -24010,7 +24028,7 @@ instantiate_pending_templates (int retries)
>       to avoid infinite loop.  */
>    if (pending_templates && retries >= max_tinst_depth)
>      {
> -      tree decl = pending_templates->tinst->get_decl_maybe ();
> +      tree decl = pending_templates->tinst->maybe_get_node ();
>
>        fatal_error (input_location,
>                    "template instantiation depth exceeds maximum of %d"
> @@ -24351,7 +24369,7 @@ bool
>  instantiating_current_function_p (void)
>  {
>    return (current_instantiation ()
> -         && (current_instantiation ()->get_decl_maybe ()
> +         && (current_instantiation ()->maybe_get_node ()
>               == current_function_decl));
>  }
>
> --
> Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
> You must be the change you wish to see in the world. -- Gandhi
> Be Free! -- http://FSFLA.org/   FSF Latin America board member
> Free Software Evangelist|Red Hat Brasil GNU Toolchain Engineer
>
Alexandre Oliva April 18, 2018, 6 a.m. | #10
On Apr 18, 2018, Jason Merrill <jason@redhat.com> wrote:

> Ok, thanks.

Thanks, here's the consolidated patch I installed.


tinst_level objects are created during template instantiation, and
they're most often quite short-lived, but since there's no intervening
garbage collection, they accumulate throughout the pass while most by
far could be recycled after a short while.  The original testcase in
PR80290, for example, creates almost 55 million tinst_level objects,
all but 10 thousand of them without intervening GC, but we don't need
more than 284 of them live at a time.

Furthermore, in many cases, TREE_LIST objects are created to stand for
the decl in tinst_level.  In most cases, those can be recycled as soon
as the tinst_level object is recycled; in some relatively common
cases, they are modified and reused in up to 3 tinst_level objects.
In the same testcase, TREE_LISTs are used in all but 3 thousand of the
tinst_level objects, and we don't need more than 89 tinst_level
objects with TREE_LISTs live at a time.  Furthermore, all but 2
thousand of those are created without intervening GC.

This patch arranges for tinst_level objects to be refcounted (I've
seen as many as 20 live references to a single tinst_level object in
my testing), and for pending_template, tinst_level and TREE_LIST
objects that can be recycled to be added to freelists; that's much
faster than ggc_free()ing them and reallocating them shortly
thereafter.  In fact, the introduction of such freelists is what makes
this entire patch lighter-weight, when it comes to memory use, and
faster.  With refcounting alone, the total memory footprint was still
about the same, and we spent more time.

In order to further reduce memory use, I've arranged for us to create
TREE_LISTs lazily, only at points that really need them (when printing
error messages).  This grows tinst_level by an additional pointer, but
since a TREE_LIST holds a lot more than an extra pointer, and
tinst_levels with TREE_LISTs used to be allocated tens of thousands of
times more often than plain decl ones, we still save memory overall.

I was still not quite happy about growing memory use in cases that
used template classes but not template overload resolution, so I
changed the type of the errors field to unsigned short, from int.
With that change, in_system_header_p and refcount move into the same
word or half-word that used to hold errors, releasing a full word,
bringing tinst_level back to its original size, now without any
padding.

The errors field is only used to test whether we've had any errors
since the expansion of some template, to skip the expansion of further
templates.  If we get 2^16 errors or more, it is probably reasonable
to refrain from expanding further templates, even if we would expand
them before this change.

With these changes, compile time for the original testcase at -O0,
with default checking enabled, is cut down by some 3.7%, total GCable
memory allocation is cut down by almost 20%, and total memory use (as
reported by GNU time as maxresident) is cut down by slightly over 15%.


for  gcc/cp/ChangeLog

	PR c++/80290
	* cp-tree.h (struct tinst_level): Split decl into tldcl and
	targs.  Add private split_list_p, tree_list_p, and not_list_p
	inline const predicates; to_list private member function
	declaration; free public member function declaration; list_p,
	get_node and maybe_get_node accessors, and refcount data
	member.  Narrow errors to unsigned short.
	* error.c (print_instantiation_full_context): Use new
	accessors.
	(print_instantiation_partial_context_line): Likewise.  Drop
	const from tinst_level-typed parameter.
	* mangle.c (mangle_decl_string): Likewise.
	* pt.c (freelist): New template class.
	(tree_list_freelist_head): New var.
	(tree_list_freelist): New fn, along with specializations.
	(tinst_level_freelist_head): New var.
	(pending_template_freelist_head): Likewise.
	(tinst_level_freelist, pending_template_freelist): New fns.
	(tinst_level::to_list, tinst_level::free): Define.
	(inc_refcount_use, dec_refcount_use): New fns for tinst_level.
	(set_refcount_ptr): New template fn.
	(add_pending_template): Adjust for refcounting, freelists and
	new accessors.
	(neglectable_inst_p): Take a NULL d as a non-DECL.
	(limit_bad_template_recursion): Use new accessors.
	(push_tinst_level): New overload to create the list.
	(push_tinst_level_loc): Make it static, split decl into two
	args, adjust tests and initialization to cope with split
	lists, use freelist, adjust for refcounting.
	(push_tinst_level_loc): New wrapper with the old interface.
	(pop_tinst_level): Adjust for refcounting.
	(record_last_problematic_instantiation): Likewise.
	(reopen_tinst_level): Likewise.  Use new accessors.
	(instantiate_alias_template): Adjust for split list.
	(fn_type_unification): Likewise.
	(get_partial_spec_bindings): Likewise.
	(instantiate_pending_templates): Use new accessors.  Adjust
	for refcount.  Release pending_template to freelist.
	(instantiating_current_function_p): Use new accessors.
---
 gcc/cp/cp-tree.h |   62 ++++++++
 gcc/cp/error.c   |   12 +-
 gcc/cp/mangle.c  |    2 
 gcc/cp/pt.c      |  406 +++++++++++++++++++++++++++++++++++++++++++++---------
 4 files changed, 402 insertions(+), 80 deletions(-)

diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index d0f87603e98e..7031c79b35db 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -5870,19 +5870,71 @@ struct GTY((chain_next ("%h.next"))) tinst_level {
   /* The immediately deeper level in the chain.  */
   struct tinst_level *next;
 
-  /* The original node.  Can be either a DECL (for a function or static
-     data member) or a TYPE (for a class), depending on what we were
-     asked to instantiate.  */
-  tree decl;
+  /* The original node.  TLDCL can be a DECL (for a function or static
+     data member), a TYPE (for a class), depending on what we were
+     asked to instantiate, or a TREE_LIST with the template as PURPOSE
+     and the template args as VALUE, if we are substituting for
+     overload resolution.  In all these cases, TARGS is NULL.
+     However, to avoid creating TREE_LIST objects for substitutions if
+     we can help, we store PURPOSE and VALUE in TLDCL and TARGS,
+     respectively.  So TLDCL stands for TREE_LIST or DECL (the
+     template is a DECL too), whereas TARGS stands for the template
+     arguments.  */
+  tree tldcl, targs;
+
+ private:
+  /* Return TRUE iff the original node is a split list.  */
+  bool split_list_p () const { return targs; }
+
+  /* Return TRUE iff the original node is a TREE_LIST object.  */
+  bool tree_list_p () const
+  {
+    return !split_list_p () && TREE_CODE (tldcl) == TREE_LIST;
+  }
+
+  /* Return TRUE iff the original node is not a list, split or not.  */
+  bool not_list_p () const
+  {
+    return !split_list_p () && !tree_list_p ();
+  }
+
+  /* Convert (in place) the original node from a split list to a
+     TREE_LIST.  */
+  tree to_list ();
+
+ public:
+  /* Release storage for OBJ and node, if it's a TREE_LIST.  */
+  static void free(tinst_level *obj);
+
+  /* Return TRUE iff the original node is a list, split or not.  */
+  bool list_p () const { return !not_list_p (); }
+
+  /* Return the original node; if it's a split list, make it a
+     TREE_LIST first, so that it can be returned as a single tree
+     object.  */
+  tree get_node () {
+    if (!split_list_p ()) return tldcl;
+    else return to_list ();
+  }
+
+  /* Return the original node if it's a DECL or a TREE_LIST, but do
+     NOT convert a split list to a TREE_LIST: return NULL instead.  */
+  tree maybe_get_node () const {
+    if (!split_list_p ()) return tldcl;
+    else return NULL_TREE;
+  }
 
   /* The location where the template is instantiated.  */
   location_t locus;
 
   /* errorcount+sorrycount when we pushed this level.  */
-  int errors;
+  unsigned short errors;
 
   /* True if the location is in a system header.  */
   bool in_system_header_p;
+
+  /* Count references to this object.  */
+  unsigned char refcount;
 };
 
 bool decl_spec_seq_has_spec_p (const cp_decl_specifier_seq *, cp_decl_spec);
diff --git a/gcc/cp/error.c b/gcc/cp/error.c
index f27b700a4349..95b8b84f34ab 100644
--- a/gcc/cp/error.c
+++ b/gcc/cp/error.c
@@ -3457,11 +3457,11 @@ print_instantiation_full_context (diagnostic_context *context)
   if (p)
     {
       pp_verbatim (context->printer,
-		   TREE_CODE (p->decl) == TREE_LIST
+		   p->list_p ()
 		   ? _("%s: In substitution of %qS:\n")
 		   : _("%s: In instantiation of %q#D:\n"),
 		   LOCATION_FILE (location),
-		   p->decl);
+		   p->get_node ());
 
       location = p->locus;
       p = p->next;
@@ -3475,7 +3475,7 @@ print_instantiation_full_context (diagnostic_context *context)
 
 static void
 print_instantiation_partial_context_line (diagnostic_context *context,
-					  const struct tinst_level *t,
+					  struct tinst_level *t,
 					  location_t loc, bool recursive_p)
 {
   if (loc == UNKNOWN_LOCATION)
@@ -3492,18 +3492,18 @@ print_instantiation_partial_context_line (diagnostic_context *context,
 
   if (t != NULL)
     {
-      if (TREE_CODE (t->decl) == TREE_LIST)
+      if (t->list_p ())
 	pp_verbatim (context->printer,
 		     recursive_p
 		     ? _("recursively required by substitution of %qS\n")
 		     : _("required by substitution of %qS\n"),
-		     t->decl);
+		     t->get_node ());
       else
 	pp_verbatim (context->printer,
 		     recursive_p
 		     ? _("recursively required from %q#D\n")
 		     : _("required from %q#D\n"),
-		     t->decl);
+		     t->get_node ());
     }
   else
     {
diff --git a/gcc/cp/mangle.c b/gcc/cp/mangle.c
index a7f9d686345d..2f65709d7d8c 100644
--- a/gcc/cp/mangle.c
+++ b/gcc/cp/mangle.c
@@ -3777,7 +3777,7 @@ mangle_decl_string (const tree decl)
   if (DECL_LANG_SPECIFIC (decl) && DECL_USE_TEMPLATE (decl))
     {
       struct tinst_level *tl = current_instantiation ();
-      if ((!tl || tl->decl != decl)
+      if ((!tl || tl->maybe_get_node () != decl)
 	  && push_tinst_level (decl))
 	{
 	  template_p = true;
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index da8a5264d33e..79563dfa5334 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -50,7 +50,8 @@ typedef int (*tree_fn_t) (tree, void*);
 /* The PENDING_TEMPLATES is a TREE_LIST of templates whose
    instantiations have been deferred, either because their definitions
    were not yet available, or because we were putting off doing the work.  */
-struct GTY ((chain_next ("%h.next"))) pending_template {
+struct GTY ((chain_next ("%h.next"))) pending_template
+{
   struct pending_template *next;
   struct tinst_level *tinst;
 };
@@ -8731,6 +8732,269 @@ comp_template_args_porder (tree oargs, tree nargs)
   return comp_template_args (oargs, nargs, NULL, NULL, true);
 }
 
+/* Implement a freelist interface for objects of type T.
+
+   Head is a separate object, rather than a regular member, so that we
+   can define it as a GTY deletable pointer, which is highly
+   desirable.  A data member could be declared that way, but then the
+   containing object would implicitly get GTY((user)), which would
+   prevent us from instantiating freelists as global objects.
+   Although this way we can create freelist global objects, they're
+   such thin wrappers that instantiating temporaries at every use
+   loses nothing and saves permanent storage for the freelist object.
+
+   Member functions next, anew, poison and reinit have default
+   implementations that work for most of the types we're interested
+   in, but if they don't work for some type, they should be explicitly
+   specialized.  See the comments before them for requirements, and
+   the example specializations for the tree_list_freelist.  */
+template <typename T>
+class freelist
+{
+  /* Return the next object in a chain.  We could just do type
+     punning, but if we access the object with its underlying type, we
+     avoid strict-aliasing trouble.  This needs only work between
+     poison and reinit.  */
+  static T *&next (T *obj) { return obj->next; }
+
+  /* Return a newly allocated, uninitialized or minimally-initialized
+     object of type T.  Any initialization performed by anew should
+     either remain across the life of the object and the execution of
+     poison, or be redone by reinit.  */
+  static T *anew () { return ggc_alloc<T> (); }
+
+  /* Optionally scribble all over the bits holding the object, so that
+     they become (mostly?) uninitialized memory.  This is called while
+     preparing to make the object part of the free list.  */
+  static void poison (T *obj) {
+    T *p ATTRIBUTE_UNUSED = obj;
+    T **q ATTRIBUTE_UNUSED = &next (obj);
+
+#ifdef ENABLE_GC_CHECKING
+    /* Poison the data, to indicate the data is garbage.  */
+    VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (p, sizeof (*p)));
+    memset (p, 0xa5, sizeof (*p));
+#endif
+    /* Let valgrind know the object is free.  */
+    VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (p, sizeof (*p)));
+
+    /* Let valgrind know the next portion of the object is available,
+       but uninitialized.  */
+    VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (q, sizeof (*q)));
+  }
+
+  /* Bring an object that underwent at least one lifecycle after anew
+     and before the most recent free and poison, back to a usable
+     state, reinitializing whatever is needed for it to be
+     functionally equivalent to an object just allocated and returned
+     by anew.  This may poison or clear the next field, used by
+     freelist housekeeping after poison was called.  */
+  static void reinit (T *obj) {
+    T **q ATTRIBUTE_UNUSED = &next (obj);
+
+#ifdef ENABLE_GC_CHECKING
+    memset (q, 0xa5, sizeof (*q));
+#endif
+    /* Let valgrind know the entire object is available, but
+       uninitialized.  */
+    VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (obj, sizeof (*obj)));
+  }
+
+  /* Reference a GTY-deletable pointer that points to the first object
+     in the free list proper.  */
+  T *&head;
+public:
+  /* Construct a freelist object chaining objects off of HEAD.  */
+  freelist (T *&head) : head(head) {}
+
+  /* Add OBJ to the free object list.  The former head becomes OBJ's
+     successor.  */
+  void free (T *obj)
+  {
+    poison (obj);
+    next (obj) = head;
+    head = obj;
+  }
+
+  /* Take an object from the free list, if one is available, or
+     allocate a new one.  Objects taken from the free list should be
+     regarded as filled with garbage, except for bits that are
+     configured to be preserved across free and alloc.  */
+  T *alloc ()
+  {
+    if (head)
+      {
+	T *obj = head;
+	head = next (head);
+	reinit (obj);
+	return obj;
+      }
+    else
+      return anew ();
+  }
+};
+
+/* Explicitly specialize the interfaces for freelist<tree_node>: we
+   want to allocate a TREE_LIST using the usual interface, and ensure
+   TREE_CHAIN remains functional.  Alas, we have to duplicate a bit of
+   build_tree_list logic in reinit, so this could go out of sync.  */
+template <>
+inline tree &
+freelist<tree_node>::next (tree obj)
+{
+  return TREE_CHAIN (obj);
+}
+template <>
+inline tree
+freelist<tree_node>::anew ()
+{
+  return build_tree_list (NULL, NULL);
+}
+template <>
+inline void
+freelist<tree_node>::poison (tree obj ATTRIBUTE_UNUSED)
+{
+  int size ATTRIBUTE_UNUSED = sizeof (tree_list);
+  tree p ATTRIBUTE_UNUSED = obj;
+  tree_base *b ATTRIBUTE_UNUSED = &obj->base;
+  tree *q ATTRIBUTE_UNUSED = &next (obj);
+
+#ifdef ENABLE_GC_CHECKING
+  gcc_checking_assert (TREE_CODE (obj) == TREE_LIST);
+
+  /* Poison the data, to indicate the data is garbage.  */
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (p, size));
+  memset (p, 0xa5, size);
+#endif
+  /* Let valgrind know the object is free.  */
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (p, size));
+  /* But we still want to use the TREE_CODE and TREE_CHAIN parts.  */
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (b, sizeof (*b)));
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (q, sizeof (*q)));
+
+#ifdef ENABLE_GC_CHECKING
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (b, sizeof (*b)));
+  /* Keep TREE_CHAIN functional.  */
+  TREE_SET_CODE (obj, TREE_LIST);
+#else
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (b, sizeof (*b)));
+#endif
+}
+template <>
+inline void
+freelist<tree_node>::reinit (tree obj ATTRIBUTE_UNUSED)
+{
+  tree_base *b ATTRIBUTE_UNUSED = &obj->base;
+
+#ifdef ENABLE_GC_CHECKING
+  gcc_checking_assert (TREE_CODE (obj) == TREE_LIST);
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (obj, sizeof (tree_list)));
+  memset (obj, 0, sizeof (tree_list));
+#endif
+
+  /* Let valgrind know the entire object is available, but
+     uninitialized.  */
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (obj, sizeof (tree_list)));
+
+#ifdef ENABLE_GC_CHECKING
+  TREE_SET_CODE (obj, TREE_LIST);
+#else
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (b, sizeof (*b)));
+#endif
+}
+
+/* Point to the first object in the TREE_LIST freelist.  */
+static GTY((deletable)) tree tree_list_freelist_head;
+/* Return the/an actual TREE_LIST freelist.  */
+static inline freelist<tree_node>
+tree_list_freelist ()
+{
+  return tree_list_freelist_head;
+}
+
+/* Point to the first object in the tinst_level freelist.  */
+static GTY((deletable)) tinst_level *tinst_level_freelist_head;
+/* Return the/an actual tinst_level freelist.  */
+static inline freelist<tinst_level>
+tinst_level_freelist ()
+{
+  return tinst_level_freelist_head;
+}
+
+/* Point to the first object in the pending_template freelist.  */
+static GTY((deletable)) pending_template *pending_template_freelist_head;
+/* Return the/an actual pending_template freelist.  */
+static inline freelist<pending_template>
+pending_template_freelist ()
+{
+  return pending_template_freelist_head;
+}
+
+/* Build the TREE_LIST object out of a split list, store it
+   permanently, and return it.  */
+tree
+tinst_level::to_list ()
+{
+  gcc_assert (split_list_p ());
+  tree ret = tree_list_freelist ().alloc ();
+  TREE_PURPOSE (ret) = tldcl;
+  TREE_VALUE (ret) = targs;
+  tldcl = ret;
+  targs = NULL;
+  gcc_assert (tree_list_p ());
+  return ret;
+}
+
+/* Increment OBJ's refcount.  */
+static tinst_level *
+inc_refcount_use (tinst_level *obj)
+{
+  if (obj)
+    {
+      ++obj->refcount;
+      gcc_assert (obj->refcount != 0);
+    }
+  return obj;
+}
+
+/* Release storage for OBJ and node, if it's a TREE_LIST.  */
+void
+tinst_level::free (tinst_level *obj)
+{
+  if (obj->tree_list_p ())
+    tree_list_freelist ().free (obj->get_node ());
+  tinst_level_freelist ().free (obj);
+}
+
+/* Decrement OBJ's refcount.  If it reaches zero, release OBJ's DECL
+   and OBJ, and start over with the tinst_level object that used to be
+   referenced by OBJ's NEXT.  */
+static void
+dec_refcount_use (tinst_level *obj)
+{
+  while (obj && !--obj->refcount)
+    {
+      gcc_assert (obj->refcount+1 != 0);
+      tinst_level *next = obj->next;
+      tinst_level::free (obj);
+      obj = next;
+    }
+}
+
+/* Modify PTR so that it points to OBJ, adjusting the refcounts of OBJ
+   and of the former PTR.  Omitting the second argument is equivalent
+   to passing (T*)NULL; this is allowed because passing the
+   zero-valued integral constant NULL confuses type deduction and/or
+   overload resolution.  */
+template <typename T>
+static void
+set_refcount_ptr (T *& ptr, T *obj = NULL)
+{
+  T *save = ptr;
+  ptr = inc_refcount_use (obj);
+  dec_refcount_use (save);
+}
+
 static void
 add_pending_template (tree d)
 {
@@ -8746,14 +9010,17 @@ add_pending_template (tree d)
   /* We are called both from instantiate_decl, where we've already had a
      tinst_level pushed, and instantiate_template, where we haven't.
      Compensate.  */
-  level = !current_tinst_level || current_tinst_level->decl != d;
+  gcc_assert (TREE_CODE (d) != TREE_LIST);
+  level = !current_tinst_level
+    || current_tinst_level->maybe_get_node () != d;
 
   if (level)
     push_tinst_level (d);
 
-  pt = ggc_alloc<pending_template> ();
+  pt = pending_template_freelist ().alloc ();
   pt->next = NULL;
-  pt->tinst = current_tinst_level;
+  pt->tinst = NULL;
+  set_refcount_ptr (pt->tinst, current_tinst_level);
   if (last_pending_template)
     last_pending_template->next = pt;
   else
@@ -9810,7 +10077,7 @@ uses_outer_template_parms (tree decl)
 static inline bool
 neglectable_inst_p (tree d)
 {
-  return (DECL_P (d)
+  return (d && DECL_P (d)
 	  && !undeduced_auto_decl (d)
 	  && !(TREE_CODE (d) == FUNCTION_DECL ? DECL_DECLARED_CONSTEXPR_P (d)
 	       : decl_maybe_constant_var_p (d)));
@@ -9828,7 +10095,7 @@ limit_bad_template_recursion (tree decl)
     return false;
 
   for (; lev; lev = lev->next)
-    if (neglectable_inst_p (lev->decl))
+    if (neglectable_inst_p (lev->maybe_get_node ()))
       break;
 
   return (lev && errs > lev->errors);
@@ -9840,20 +10107,11 @@ int depth_reached;
 
 static GTY(()) struct tinst_level *last_error_tinst_level;
 
-/* We're starting to instantiate D; record the template instantiation context
-   for diagnostics and to restore it later.  */
-
-bool
-push_tinst_level (tree d)
-{
-  return push_tinst_level_loc (d, input_location);
-}
-
 /* We're starting to instantiate D; record the template instantiation context
    at LOC for diagnostics and to restore it later.  */
 
-bool
-push_tinst_level_loc (tree d, location_t loc)
+static bool
+push_tinst_level_loc (tree tldcl, tree targs, location_t loc)
 {
   struct tinst_level *new_level;
 
@@ -9871,23 +10129,26 @@ push_tinst_level_loc (tree d, location_t loc)
   /* If the current instantiation caused problems, don't let it instantiate
      anything else.  Do allow deduction substitution and decls usable in
      constant expressions.  */
-  if (limit_bad_template_recursion (d))
+  if (!targs && limit_bad_template_recursion (tldcl))
     return false;
 
   /* When not -quiet, dump template instantiations other than functions, since
      announce_function will take care of those.  */
-  if (!quiet_flag
-      && TREE_CODE (d) != TREE_LIST
-      && TREE_CODE (d) != FUNCTION_DECL)
-    fprintf (stderr, " %s", decl_as_string (d, TFF_DECL_SPECIFIERS));
-
-  new_level = ggc_alloc<tinst_level> ();
-  new_level->decl = d;
+  if (!quiet_flag && !targs
+      && TREE_CODE (tldcl) != TREE_LIST
+      && TREE_CODE (tldcl) != FUNCTION_DECL)
+    fprintf (stderr, " %s", decl_as_string (tldcl, TFF_DECL_SPECIFIERS));
+
+  new_level = tinst_level_freelist ().alloc ();
+  new_level->tldcl = tldcl;
+  new_level->targs = targs;
   new_level->locus = loc;
   new_level->errors = errorcount+sorrycount;
   new_level->in_system_header_p = in_system_header_at (input_location);
-  new_level->next = current_tinst_level;
-  current_tinst_level = new_level;
+  new_level->next = NULL;
+  new_level->refcount = 0;
+  set_refcount_ptr (new_level->next, current_tinst_level);
+  set_refcount_ptr (current_tinst_level, new_level);
 
   ++tinst_depth;
   if (GATHER_STATISTICS && (tinst_depth > depth_reached))
@@ -9896,6 +10157,34 @@ push_tinst_level_loc (tree d, location_t loc)
   return true;
 }
 
+/* We're starting substitution of TMPL<ARGS>; record the template
+   substitution context for diagnostics and to restore it later.  */
+
+static bool
+push_tinst_level (tree tmpl, tree args)
+{
+  return push_tinst_level_loc (tmpl, args, input_location);
+}
+
+/* We're starting to instantiate D; record INPUT_LOCATION and the
+   template instantiation context for diagnostics and to restore it
+   later.  */
+
+bool
+push_tinst_level (tree d)
+{
+  return push_tinst_level_loc (d, input_location);
+}
+
+/* Likewise, but record LOC as the program location.  */
+
+bool
+push_tinst_level_loc (tree d, location_t loc)
+{
+  gcc_assert (TREE_CODE (d) != TREE_LIST);
+  return push_tinst_level_loc (d, NULL, loc);
+}
+
 /* We're done instantiating this template; return to the instantiation
    context.  */
 
@@ -9905,7 +10194,7 @@ pop_tinst_level (void)
   /* Restore the filename and line number stashed away when we started
      this instantiation.  */
   input_location = current_tinst_level->locus;
-  current_tinst_level = current_tinst_level->next;
+  set_refcount_ptr (current_tinst_level, current_tinst_level->next);
   --tinst_depth;
 }
 
@@ -9922,11 +10211,11 @@ reopen_tinst_level (struct tinst_level *level)
   for (t = level; t; t = t->next)
     ++tinst_depth;
 
-  current_tinst_level = level;
+  set_refcount_ptr (current_tinst_level, level);
   pop_tinst_level ();
   if (current_tinst_level)
     current_tinst_level->errors = errorcount+sorrycount;
-  return level->decl;
+  return level->maybe_get_node ();
 }
 
 /* Returns the TINST_LEVEL which gives the original instantiation
@@ -18983,16 +19272,10 @@ instantiate_template (tree tmpl, tree orig_args, tsubst_flags_t complain)
 static tree
 instantiate_alias_template (tree tmpl, tree args, tsubst_flags_t complain)
 {
-  struct pending_template *old_last_pend = last_pending_template;
-  struct tinst_level *old_error_tinst = last_error_tinst_level;
   if (tmpl == error_mark_node || args == error_mark_node)
     return error_mark_node;
-  tree tinst = build_tree_list (tmpl, args);
-  if (!push_tinst_level (tinst))
-    {
-      ggc_free (tinst);
-      return error_mark_node;
-    }
+  if (!push_tinst_level (tmpl, args))
+    return error_mark_node;
 
   args =
     coerce_innermost_template_parms (DECL_TEMPLATE_PARMS (tmpl),
@@ -19002,11 +19285,6 @@ instantiate_alias_template (tree tmpl, tree args, tsubst_flags_t complain)
 
   tree r = instantiate_template (tmpl, args, complain);
   pop_tinst_level ();
-  /* We can't free this if a pending_template entry or last_error_tinst_level
-     is pointing at it.  */
-  if (last_pending_template == old_last_pend
-      && last_error_tinst_level == old_error_tinst)
-    ggc_free (tinst);
 
   return r;
 }
@@ -19096,15 +19374,12 @@ fn_type_unification (tree fn,
   tsubst_flags_t complain = (explain_p ? tf_warning_or_error : tf_none);
   bool ok;
   static int deduction_depth;
-  struct pending_template *old_last_pend = last_pending_template;
-  struct tinst_level *old_error_tinst = last_error_tinst_level;
 
   tree orig_fn = fn;
   if (flag_new_inheriting_ctors)
     fn = strip_inheriting_ctors (fn);
 
   tree tparms = DECL_INNERMOST_TEMPLATE_PARMS (fn);
-  tree tinst;
   tree r = error_mark_node;
 
   tree full_targs = targs;
@@ -19130,7 +19405,6 @@ fn_type_unification (tree fn,
      This is, of course, not reentrant.  */
   if (excessive_deduction_depth)
     return error_mark_node;
-  tinst = build_tree_list (fn, NULL_TREE);
   ++deduction_depth;
 
   gcc_assert (TREE_CODE (fn) == TEMPLATE_DECL);
@@ -19223,8 +19497,7 @@ fn_type_unification (tree fn,
             }
         }
 
-      TREE_VALUE (tinst) = explicit_targs;
-      if (!push_tinst_level (tinst))
+      if (!push_tinst_level (fn, explicit_targs))
 	{
 	  excessive_deduction_depth = true;
 	  goto fail;
@@ -19279,12 +19552,11 @@ fn_type_unification (tree fn,
      callers must be ready to deal with unification failures in any
      event.  */
 
-  TREE_VALUE (tinst) = targs;
   /* If we aren't explaining yet, push tinst context so we can see where
      any errors (e.g. from class instantiations triggered by instantiation
      of default template arguments) come from.  If we are explaining, this
      context is redundant.  */
-  if (!explain_p && !push_tinst_level (tinst))
+  if (!explain_p && !push_tinst_level (fn, targs))
     {
       excessive_deduction_depth = true;
       goto fail;
@@ -19340,8 +19612,7 @@ fn_type_unification (tree fn,
      the corresponding deduced argument values.  If the
      substitution results in an invalid type, as described above,
      type deduction fails.  */
-  TREE_VALUE (tinst) = targs;
-  if (!push_tinst_level (tinst))
+  if (!push_tinst_level (fn, targs))
     {
       excessive_deduction_depth = true;
       goto fail;
@@ -19407,12 +19678,6 @@ fn_type_unification (tree fn,
 	excessive_deduction_depth = false;
     }
 
-  /* We can't free this if a pending_template entry or last_error_tinst_level
-     is pointing at it.  */
-  if (last_pending_template == old_last_pend
-      && last_error_tinst_level == old_error_tinst)
-    ggc_free (tinst);
-
   return r;
 }
 
@@ -22382,8 +22647,7 @@ get_partial_spec_bindings (tree tmpl, tree spec_tmpl, tree args)
 	return NULL_TREE;
       }
 
-  tree tinst = build_tree_list (spec_tmpl, deduced_args);
-  if (!push_tinst_level (tinst))
+  if (!push_tinst_level (spec_tmpl, deduced_args))
     {
       excessive_deduction_depth = true;
       return NULL_TREE;
@@ -23764,7 +24028,7 @@ instantiate_pending_templates (int retries)
      to avoid infinite loop.  */
   if (pending_templates && retries >= max_tinst_depth)
     {
-      tree decl = pending_templates->tinst->decl;
+      tree decl = pending_templates->tinst->maybe_get_node ();
 
       fatal_error (input_location,
 		   "template instantiation depth exceeds maximum of %d"
@@ -23827,16 +24091,21 @@ instantiate_pending_templates (int retries)
 	    }
 
 	  if (complete)
-	    /* If INSTANTIATION has been instantiated, then we don't
-	       need to consider it again in the future.  */
-	    *t = (*t)->next;
+	    {
+	      /* If INSTANTIATION has been instantiated, then we don't
+		 need to consider it again in the future.  */
+	      struct pending_template *drop = *t;
+	      *t = (*t)->next;
+	      set_refcount_ptr (drop->tinst);
+	      pending_template_freelist ().free (drop);
+	    }
 	  else
 	    {
 	      last = *t;
 	      t = &(*t)->next;
 	    }
 	  tinst_depth = 0;
-	  current_tinst_level = NULL;
+	  set_refcount_ptr (current_tinst_level);
 	}
       last_pending_template = last;
     }
@@ -24084,7 +24353,7 @@ problematic_instantiation_changed (void)
 void
 record_last_problematic_instantiation (void)
 {
-  last_error_tinst_level = current_tinst_level;
+  set_refcount_ptr (last_error_tinst_level, current_tinst_level);
 }
 
 struct tinst_level *
@@ -24100,7 +24369,8 @@ bool
 instantiating_current_function_p (void)
 {
   return (current_instantiation ()
-	  && current_instantiation ()->decl == current_function_decl);
+	  && (current_instantiation ()->maybe_get_node ()
+	      == current_function_decl));
 }
 
 /* [temp.param] Check that template non-type parm TYPE is of an allowable
Alexandre Oliva April 19, 2018, 6:41 a.m. | #11
[adding list back]

On Apr 18, 2018, Jakub Jelinek <jakub@redhat.com> wrote:

> On Wed, Apr 18, 2018 at 12:29:03AM -0300, Alexandre Oliva wrote:
>> +  static void free(tinst_level *obj);
>                      ^
> 		     + missing space

Thanks, fixed with this patch:

diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index 7cd714b9e3ad..4475b228c2eb 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,3 +1,8 @@
+2018-04-19  Alexandre Oliva  <aoliva@redhat.com>
+
+	PR c++/80290
+	* cp-tree.h (tinst_level::free): Fix whitespace.
+
 2018-04-18  Paolo Carlini  <paolo.carlini@oracle.com>
 
 	PR c++/84630
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 7031c79b35db..8c5c84e22b22 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -5904,7 +5904,7 @@ struct GTY((chain_next ("%h.next"))) tinst_level {
 
  public:
   /* Release storage for OBJ and node, if it's a TREE_LIST.  */
-  static void free(tinst_level *obj);
+  static void free (tinst_level *obj);
 
   /* Return TRUE iff the original node is a list, split or not.  */
   bool list_p () const { return !not_list_p (); }

Patch

diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index d0f87603e98e..e9d9bab879bc 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -5870,19 +5870,68 @@  struct GTY((chain_next ("%h.next"))) tinst_level {
   /* The immediately deeper level in the chain.  */
   struct tinst_level *next;
 
-  /* The original node.  Can be either a DECL (for a function or static
-     data member) or a TYPE (for a class), depending on what we were
-     asked to instantiate.  */
-  tree decl;
+  /* The original node.  TLDCL can be a DECL (for a function or static
+     data member), a TYPE (for a class), depending on what we were
+     asked to instantiate, or a TREE_LIST with the template as PURPOSE
+     and the template args as VALUE, if we are substituting for
+     overload resolution.  In all these cases, TARGS is NULL.
+     However, to avoid creating TREE_LIST objects for substitutions if
+     we can help, we store PURPOSE and VALUE in TLDCL and TARGS,
+     respectively.  So TLDCL stands for TREE_LIST or DECL (the
+     template is a DECL too), whereas TARGS stands for the template
+     arguments.  */
+  tree tldcl, targs;
+
+ private:
+  /* Return TRUE iff the original node is a split list.  */
+  bool split_list_p () const { return targs; }
+
+  /* Return TRUE iff the original node is a TREE_LIST object.  */
+  bool tree_list_p () const
+  {
+    return !split_list_p () && TREE_CODE (tldcl) == TREE_LIST;
+  }
+
+  /* Return TRUE iff the original node is not a list, split or not.  */
+  bool not_list_p () const
+  {
+    return !split_list_p () && !tree_list_p ();
+  }
+
+  /* Convert (in place) the original node from a split list to a
+     TREE_LIST.  */
+  tree to_list ();
+
+ public:
+  /* Return TRUE iff the original node is a list, split or not.  */
+  bool list_p () const { return !not_list_p (); }
+
+  /* Return the original node; if it's a split list, make it a
+     TREE_LIST first, so that it can be returned as a single tree
+     object.  */
+  tree get_node () const {
+    if (!split_list_p ()) return tldcl;
+    else return const_cast <tinst_level *>(this)->to_list ();
+  }
+
+  /* Return the original node if it's a DECL or a TREE_LIST, but do
+     NOT convert a split list to a TREE_LIST: return NULL instead.  */
+  tree get_decl_maybe () const {
+    if (!split_list_p ()) return tldcl;
+    else return NULL_TREE;
+  }
 
   /* The location where the template is instantiated.  */
   location_t locus;
 
   /* errorcount+sorrycount when we pushed this level.  */
-  int errors;
+  unsigned short errors;
 
   /* True if the location is in a system header.  */
   bool in_system_header_p;
+
+  /* Count references to this object.  */
+  unsigned char refcount;
 };
 
 bool decl_spec_seq_has_spec_p (const cp_decl_specifier_seq *, cp_decl_spec);
diff --git a/gcc/cp/error.c b/gcc/cp/error.c
index f27b700a4349..983ffdfedbb2 100644
--- a/gcc/cp/error.c
+++ b/gcc/cp/error.c
@@ -3457,11 +3457,11 @@  print_instantiation_full_context (diagnostic_context *context)
   if (p)
     {
       pp_verbatim (context->printer,
-		   TREE_CODE (p->decl) == TREE_LIST
+		   p->list_p ()
 		   ? _("%s: In substitution of %qS:\n")
 		   : _("%s: In instantiation of %q#D:\n"),
 		   LOCATION_FILE (location),
-		   p->decl);
+		   p->get_node ());
 
       location = p->locus;
       p = p->next;
@@ -3492,18 +3492,18 @@  print_instantiation_partial_context_line (diagnostic_context *context,
 
   if (t != NULL)
     {
-      if (TREE_CODE (t->decl) == TREE_LIST)
+      if (t->list_p ())
 	pp_verbatim (context->printer,
 		     recursive_p
 		     ? _("recursively required by substitution of %qS\n")
 		     : _("required by substitution of %qS\n"),
-		     t->decl);
+		     t->get_node ());
       else
 	pp_verbatim (context->printer,
 		     recursive_p
 		     ? _("recursively required from %q#D\n")
 		     : _("required from %q#D\n"),
-		     t->decl);
+		     t->get_node ());
     }
   else
     {
diff --git a/gcc/cp/mangle.c b/gcc/cp/mangle.c
index a7f9d686345d..940f7ed87e20 100644
--- a/gcc/cp/mangle.c
+++ b/gcc/cp/mangle.c
@@ -3777,7 +3777,7 @@  mangle_decl_string (const tree decl)
   if (DECL_LANG_SPECIFIC (decl) && DECL_USE_TEMPLATE (decl))
     {
       struct tinst_level *tl = current_instantiation ();
-      if ((!tl || tl->decl != decl)
+      if ((!tl || tl->get_decl_maybe () != decl)
 	  && push_tinst_level (decl))
 	{
 	  template_p = true;
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index da8a5264d33e..2442f07095ca 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -8731,6 +8731,252 @@  comp_template_args_porder (tree oargs, tree nargs)
   return comp_template_args (oargs, nargs, NULL, NULL, true);
 }
 
+/* Implement a freelist interface for objects of type T.
+
+   Head is a separate object, rather than a regular member, so that we
+   can define it as a GTY deletable pointer, which is highly
+   desirable.  A data member could be declared that way, but then the
+   containing object would implicitly get GTY((user)), which would
+   prevent us from instantiating freelists as global objects.
+   Although this way we can create freelist global objects, they're
+   such thin wrappers that instantiating temporaries at every use
+   loses nothing and saves permanent storage for the freelist object.
+
+   Member functions next, anew, poison and reinit have default
+   implementations that work for most of the types we're interested
+   in, but if they don't work for some type, they should be explicitly
+   specialized.  See the comments before them for requirements, and
+   the example specializations for the tree_list_freelist.  */
+template <typename T>
+class freelist
+{
+  /* Return the next object in a chain.  We could just do type
+     punning, but if we access the object with its underlying type, we
+     avoid strict-aliasing trouble.  This needs only work between
+     poison and reinit.  */
+  static T *&next (T *obj) { return obj->next; }
+
+  /* Return a newly allocated, uninitialized or minimally-initialized
+     object of type T.  Any initialization performed by anew should
+     either remain across the life of the object and the execution of
+     poison, or be redone by reinit.  */
+  static T *anew () { return ggc_alloc<T> (); }
+
+  /* Optionally scribble all over the bits holding the object, so that
+     they become (mostly?) uninitialized memory.  This is called while
+     preparing to make the object part of the free list.  */
+  static void poison (T *obj) {
+    T *p ATTRIBUTE_UNUSED = obj;
+    T **q ATTRIBUTE_UNUSED = &next (obj);
+
+#ifdef ENABLE_GC_CHECKING
+    /* Poison the data, to indicate the data is garbage.  */
+    VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (p, sizeof (*p)));
+    memset (p, 0xa5, sizeof (*p));
+#endif
+    /* Let valgrind know the object is free.  */
+    VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (p, sizeof (*p)));
+
+    /* Let valgrind know the next portion of the object is available,
+       but uninitialized.  */
+    VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (q, sizeof (*q)));
+  }
+
+  /* Bring an object that underwent at least one lifecycle after anew
+     and before the most recent free and poison, back to a usable
+     state, reinitializing whatever is needed for it to be
+     functionally equivalent to an object just allocated and returned
+     by anew.  This may poison or clear the next field, used by
+     freelist housekeeping after poison was called.  */
+  static void reinit (T *obj) {
+    T **q ATTRIBUTE_UNUSED = &next (obj);
+
+#ifdef ENABLE_GC_CHECKING
+    memset (q, 0xa5, sizeof (*q));
+#endif
+    /* Let valgrind know the entire object is available, but
+       uninitialized.  */
+    VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (obj, sizeof (*obj)));
+  }
+
+  /* Reference a GTY-deletable pointer that points to the first object
+     in the free list proper.  */
+  T *&head;
+public:
+  /* Construct a freelist object chaining objects off of HEAD.  */
+  freelist (T *&head) : head(head) {}
+
+  /* Add OBJ to the free object list.  The former head becomes OBJ's
+     successor.  */
+  void free (T *obj)
+  {
+    poison (obj);
+    next (obj) = head;
+    head = obj;
+  }
+
+  /* Take an object from the free list, if one is available, or
+     allocate a new one.  Objects taken from the free list should be
+     regarded as filled with garbage, except for bits that are
+     configured to be preserved across free and alloc.  */
+  T *alloc ()
+  {
+    if (head)
+      {
+	T *obj = head;
+	head = next (head);
+	reinit (obj);
+	return obj;
+      }
+    else
+      return anew ();
+  }
+};
+
+/* Explicitly specialize the interfaces for freelist<tree_node>: we
+   want to allocate a TREE_LIST using the usual interface, and ensure
+   TREE_CHAIN remains functional.  Alas, we have to duplicate a bit of
+   build_tree_list logic in reinit, so this could go out of sync.  */
+template <>
+inline tree &
+freelist<tree_node>::next (tree obj) {
+  return TREE_CHAIN (obj);
+}
+template <>
+inline tree
+freelist<tree_node>::anew () {
+  return build_tree_list (NULL, NULL);
+}
+template <>
+inline void
+freelist<tree_node>::poison (tree obj ATTRIBUTE_UNUSED) {
+  int size ATTRIBUTE_UNUSED = sizeof (tree_list);
+  tree p ATTRIBUTE_UNUSED = obj;
+  tree_base *b ATTRIBUTE_UNUSED = &obj->base;
+  tree *q ATTRIBUTE_UNUSED = &next (obj);
+
+#ifdef ENABLE_GC_CHECKING
+  gcc_checking_assert (TREE_CODE (obj) == TREE_LIST);
+
+  /* Poison the data, to indicate the data is garbage.  */
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (p, size));
+  memset (p, 0xa5, size);
+#endif
+  /* Let valgrind know the object is free.  */
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (p, size));
+  /* But we still want to use the TREE_CODE and TREE_CHAIN parts.  */
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (b, sizeof (*b)));
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (q, sizeof (*q)));
+
+#ifdef ENABLE_GC_CHECKING
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (b, sizeof (*b)));
+  /* Keep TREE_CHAIN functional.  */
+  TREE_SET_CODE (obj, TREE_LIST);
+#else
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (b, sizeof (*b)));
+#endif
+}
+template <>
+inline void
+freelist<tree_node>::reinit (tree obj ATTRIBUTE_UNUSED) {
+  tree_base *b ATTRIBUTE_UNUSED = &obj->base;
+
+#ifdef ENABLE_GC_CHECKING
+  gcc_checking_assert (TREE_CODE (obj) == TREE_LIST);
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (obj, sizeof (tree_list)));
+  memset (obj, 0, sizeof (tree_list));
+#endif
+
+  /* Let valgrind know the entire object is available, but
+     uninitialized.  */
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (obj, sizeof (tree_list)));
+
+#ifdef ENABLE_GC_CHECKING
+  TREE_SET_CODE (obj, TREE_LIST);
+#else
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (b, sizeof (*b)));
+#endif
+}
+
+/* Point to the first object in the TREE_LIST freelist.  */
+static GTY((deletable)) tree tree_list_freelist_head;
+/* Return the/an actual TREE_LIST freelist.  */
+static inline freelist<tree_node>
+tree_list_freelist () {
+  return tree_list_freelist_head;
+}
+
+/* Point to the first object in the tinst_level freelist.  */
+static GTY((deletable)) tinst_level *tinst_level_freelist_head;
+/* Return the/an actual tinst_level freelist.  */
+static inline freelist<tinst_level>
+tinst_level_freelist () {
+  return tinst_level_freelist_head;
+}
+
+/* Point to the first object in the pending_template freelist.  */
+static GTY((deletable)) pending_template *pending_template_freelist_head;
+/* Return the/an actual pending_template freelist.  */
+static inline freelist<pending_template>
+pending_template_freelist () {
+  return pending_template_freelist_head;
+}
+
+/* Build the TREE_LIST object out of a split list, store it
+   permanently, and return it.  */
+tree
+tinst_level::to_list ()
+{
+  gcc_assert (split_list_p ());
+  tree ret = tree_list_freelist ().alloc ();
+  TREE_PURPOSE (ret) = tldcl;
+  TREE_VALUE (ret) = targs;
+  tldcl = ret;
+  targs = NULL;
+  gcc_assert (tree_list_p ());
+  return ret;
+}
+
+/* Increment OBJ's refcount.  */
+static tinst_level *
+inc_refcount_use (tinst_level *obj) {
+  if (obj)
+    {
+      ++obj->refcount;
+      gcc_assert (obj->refcount != 0);
+    }
+  return obj;
+}
+
+/* Decrement OBJ's refcount.  If it reaches zero, release OBJ's DECL
+   and OBJ, and start over with the tinst_level object that used to be
+   referenced by OBJ's NEXT.  */
+static void
+dec_refcount_use (tinst_level *obj) {
+  while (obj && !--obj->refcount)
+    {
+      gcc_assert (obj->refcount+1 != 0);
+      tinst_level *next = obj->next;
+      if (obj->list_p () && obj->get_decl_maybe ())
+	tree_list_freelist ().free (obj->get_node ());
+      tinst_level_freelist ().free (obj);
+      obj = next;
+    }
+}
+
+/* Modify PTR so that it points to OBJ, adjusting the refcounts of OBJ
+   and of the former PTR.  Omitting the second argument is equivalent
+   to passing (T*)NULL; this is allowed because passing the
+   zero-valued integral constant NULL confuses type deduction and/or
+   overload resolution.  */
+template <typename T>
+static void
+set_refcount_ptr (T *& ptr, T *obj = NULL) {
+  T *save = ptr;
+  ptr = inc_refcount_use (obj);
+  dec_refcount_use (save);
+}
+
 static void
 add_pending_template (tree d)
 {
@@ -8746,14 +8992,17 @@  add_pending_template (tree d)
   /* We are called both from instantiate_decl, where we've already had a
      tinst_level pushed, and instantiate_template, where we haven't.
      Compensate.  */
-  level = !current_tinst_level || current_tinst_level->decl != d;
+  gcc_assert (TREE_CODE (d) != TREE_LIST);
+  level = !current_tinst_level
+    || current_tinst_level->get_decl_maybe () != d;
 
   if (level)
     push_tinst_level (d);
 
-  pt = ggc_alloc<pending_template> ();
+  pt = pending_template_freelist ().alloc ();
   pt->next = NULL;
-  pt->tinst = current_tinst_level;
+  pt->tinst = NULL;
+  set_refcount_ptr (pt->tinst, current_tinst_level);
   if (last_pending_template)
     last_pending_template->next = pt;
   else
@@ -9810,7 +10059,7 @@  uses_outer_template_parms (tree decl)
 static inline bool
 neglectable_inst_p (tree d)
 {
-  return (DECL_P (d)
+  return (d && DECL_P (d)
 	  && !undeduced_auto_decl (d)
 	  && !(TREE_CODE (d) == FUNCTION_DECL ? DECL_DECLARED_CONSTEXPR_P (d)
 	       : decl_maybe_constant_var_p (d)));
@@ -9828,7 +10077,7 @@  limit_bad_template_recursion (tree decl)
     return false;
 
   for (; lev; lev = lev->next)
-    if (neglectable_inst_p (lev->decl))
+    if (neglectable_inst_p (lev->get_decl_maybe ()))
       break;
 
   return (lev && errs > lev->errors);
@@ -9840,20 +10089,11 @@  int depth_reached;
 
 static GTY(()) struct tinst_level *last_error_tinst_level;
 
-/* We're starting to instantiate D; record the template instantiation context
-   for diagnostics and to restore it later.  */
-
-bool
-push_tinst_level (tree d)
-{
-  return push_tinst_level_loc (d, input_location);
-}
-
 /* We're starting to instantiate D; record the template instantiation context
    at LOC for diagnostics and to restore it later.  */
 
-bool
-push_tinst_level_loc (tree d, location_t loc)
+static bool
+push_tinst_level_loc (tree tldcl, tree targs, location_t loc)
 {
   struct tinst_level *new_level;
 
@@ -9871,23 +10111,26 @@  push_tinst_level_loc (tree d, location_t loc)
   /* If the current instantiation caused problems, don't let it instantiate
      anything else.  Do allow deduction substitution and decls usable in
      constant expressions.  */
-  if (limit_bad_template_recursion (d))
+  if (!targs && limit_bad_template_recursion (tldcl))
     return false;
 
   /* When not -quiet, dump template instantiations other than functions, since
      announce_function will take care of those.  */
-  if (!quiet_flag
-      && TREE_CODE (d) != TREE_LIST
-      && TREE_CODE (d) != FUNCTION_DECL)
-    fprintf (stderr, " %s", decl_as_string (d, TFF_DECL_SPECIFIERS));
-
-  new_level = ggc_alloc<tinst_level> ();
-  new_level->decl = d;
+  if (!quiet_flag && !targs
+      && TREE_CODE (tldcl) != TREE_LIST
+      && TREE_CODE (tldcl) != FUNCTION_DECL)
+    fprintf (stderr, " %s", decl_as_string (tldcl, TFF_DECL_SPECIFIERS));
+
+  new_level = tinst_level_freelist ().alloc ();
+  new_level->tldcl = tldcl;
+  new_level->targs = targs;
   new_level->locus = loc;
   new_level->errors = errorcount+sorrycount;
   new_level->in_system_header_p = in_system_header_at (input_location);
-  new_level->next = current_tinst_level;
-  current_tinst_level = new_level;
+  new_level->next = NULL;
+  new_level->refcount = 0;
+  set_refcount_ptr (new_level->next, current_tinst_level);
+  set_refcount_ptr (current_tinst_level, new_level);
 
   ++tinst_depth;
   if (GATHER_STATISTICS && (tinst_depth > depth_reached))
@@ -9896,6 +10139,34 @@  push_tinst_level_loc (tree d, location_t loc)
   return true;
 }
 
+/* We're starting substitution of TMPL<ARGS>; record the template
+   substitution context for diagnostics and to restore it later.  */
+
+static bool
+push_tinst_level (tree tmpl, tree args)
+{
+  return push_tinst_level_loc (tmpl, args, input_location);
+}
+
+/* We're starting to instantiate D; record INPUT_LOCATION and the
+   template instantiation context for diagnostics and to restore it
+   later.  */
+
+bool
+push_tinst_level (tree d)
+{
+  return push_tinst_level_loc (d, input_location);
+}
+
+/* Likewise, but record LOC as the program location.  */
+
+bool
+push_tinst_level_loc (tree d, location_t loc)
+{
+  gcc_assert (TREE_CODE (d) != TREE_LIST);
+  return push_tinst_level_loc (d, NULL, loc);
+}
+
 /* We're done instantiating this template; return to the instantiation
    context.  */
 
@@ -9905,7 +10176,7 @@  pop_tinst_level (void)
   /* Restore the filename and line number stashed away when we started
      this instantiation.  */
   input_location = current_tinst_level->locus;
-  current_tinst_level = current_tinst_level->next;
+  set_refcount_ptr (current_tinst_level, current_tinst_level->next);
   --tinst_depth;
 }
 
@@ -9922,11 +10193,11 @@  reopen_tinst_level (struct tinst_level *level)
   for (t = level; t; t = t->next)
     ++tinst_depth;
 
-  current_tinst_level = level;
+  set_refcount_ptr (current_tinst_level, level);
   pop_tinst_level ();
   if (current_tinst_level)
     current_tinst_level->errors = errorcount+sorrycount;
-  return level->decl;
+  return level->get_decl_maybe ();
 }
 
 /* Returns the TINST_LEVEL which gives the original instantiation
@@ -18983,16 +19254,10 @@  instantiate_template (tree tmpl, tree orig_args, tsubst_flags_t complain)
 static tree
 instantiate_alias_template (tree tmpl, tree args, tsubst_flags_t complain)
 {
-  struct pending_template *old_last_pend = last_pending_template;
-  struct tinst_level *old_error_tinst = last_error_tinst_level;
   if (tmpl == error_mark_node || args == error_mark_node)
     return error_mark_node;
-  tree tinst = build_tree_list (tmpl, args);
-  if (!push_tinst_level (tinst))
-    {
-      ggc_free (tinst);
-      return error_mark_node;
-    }
+  if (!push_tinst_level (tmpl, args))
+    return error_mark_node;
 
   args =
     coerce_innermost_template_parms (DECL_TEMPLATE_PARMS (tmpl),
@@ -19002,11 +19267,6 @@  instantiate_alias_template (tree tmpl, tree args, tsubst_flags_t complain)
 
   tree r = instantiate_template (tmpl, args, complain);
   pop_tinst_level ();
-  /* We can't free this if a pending_template entry or last_error_tinst_level
-     is pointing at it.  */
-  if (last_pending_template == old_last_pend
-      && last_error_tinst_level == old_error_tinst)
-    ggc_free (tinst);
 
   return r;
 }
@@ -19096,15 +19356,12 @@  fn_type_unification (tree fn,
   tsubst_flags_t complain = (explain_p ? tf_warning_or_error : tf_none);
   bool ok;
   static int deduction_depth;
-  struct pending_template *old_last_pend = last_pending_template;
-  struct tinst_level *old_error_tinst = last_error_tinst_level;
 
   tree orig_fn = fn;
   if (flag_new_inheriting_ctors)
     fn = strip_inheriting_ctors (fn);
 
   tree tparms = DECL_INNERMOST_TEMPLATE_PARMS (fn);
-  tree tinst;
   tree r = error_mark_node;
 
   tree full_targs = targs;
@@ -19130,7 +19387,6 @@  fn_type_unification (tree fn,
      This is, of course, not reentrant.  */
   if (excessive_deduction_depth)
     return error_mark_node;
-  tinst = build_tree_list (fn, NULL_TREE);
   ++deduction_depth;
 
   gcc_assert (TREE_CODE (fn) == TEMPLATE_DECL);
@@ -19223,8 +19479,7 @@  fn_type_unification (tree fn,
             }
         }
 
-      TREE_VALUE (tinst) = explicit_targs;
-      if (!push_tinst_level (tinst))
+      if (!push_tinst_level (fn, explicit_targs))
 	{
 	  excessive_deduction_depth = true;
 	  goto fail;
@@ -19279,12 +19534,11 @@  fn_type_unification (tree fn,
      callers must be ready to deal with unification failures in any
      event.  */
 
-  TREE_VALUE (tinst) = targs;
   /* If we aren't explaining yet, push tinst context so we can see where
      any errors (e.g. from class instantiations triggered by instantiation
      of default template arguments) come from.  If we are explaining, this
      context is redundant.  */
-  if (!explain_p && !push_tinst_level (tinst))
+  if (!explain_p && !push_tinst_level (fn, targs))
     {
       excessive_deduction_depth = true;
       goto fail;
@@ -19340,8 +19594,7 @@  fn_type_unification (tree fn,
      the corresponding deduced argument values.  If the
      substitution results in an invalid type, as described above,
      type deduction fails.  */
-  TREE_VALUE (tinst) = targs;
-  if (!push_tinst_level (tinst))
+  if (!push_tinst_level (fn, targs))
     {
       excessive_deduction_depth = true;
       goto fail;
@@ -19407,12 +19660,6 @@  fn_type_unification (tree fn,
 	excessive_deduction_depth = false;
     }
 
-  /* We can't free this if a pending_template entry or last_error_tinst_level
-     is pointing at it.  */
-  if (last_pending_template == old_last_pend
-      && last_error_tinst_level == old_error_tinst)
-    ggc_free (tinst);
-
   return r;
 }
 
@@ -22382,8 +22629,7 @@  get_partial_spec_bindings (tree tmpl, tree spec_tmpl, tree args)
 	return NULL_TREE;
       }
 
-  tree tinst = build_tree_list (spec_tmpl, deduced_args);
-  if (!push_tinst_level (tinst))
+  if (!push_tinst_level (spec_tmpl, deduced_args))
     {
       excessive_deduction_depth = true;
       return NULL_TREE;
@@ -23764,7 +24010,7 @@  instantiate_pending_templates (int retries)
      to avoid infinite loop.  */
   if (pending_templates && retries >= max_tinst_depth)
     {
-      tree decl = pending_templates->tinst->decl;
+      tree decl = pending_templates->tinst->get_decl_maybe ();
 
       fatal_error (input_location,
 		   "template instantiation depth exceeds maximum of %d"
@@ -23827,16 +24073,21 @@  instantiate_pending_templates (int retries)
 	    }
 
 	  if (complete)
-	    /* If INSTANTIATION has been instantiated, then we don't
-	       need to consider it again in the future.  */
-	    *t = (*t)->next;
+	    {
+	      /* If INSTANTIATION has been instantiated, then we don't
+		 need to consider it again in the future.  */
+	      struct pending_template *drop = *t;
+	      *t = (*t)->next;
+	      set_refcount_ptr (drop->tinst);
+	      pending_template_freelist ().free (drop);
+	    }
 	  else
 	    {
 	      last = *t;
 	      t = &(*t)->next;
 	    }
 	  tinst_depth = 0;
-	  current_tinst_level = NULL;
+	  set_refcount_ptr (current_tinst_level);
 	}
       last_pending_template = last;
     }
@@ -24084,7 +24335,7 @@  problematic_instantiation_changed (void)
 void
 record_last_problematic_instantiation (void)
 {
-  last_error_tinst_level = current_tinst_level;
+  set_refcount_ptr (last_error_tinst_level, current_tinst_level);
 }
 
 struct tinst_level *
@@ -24100,7 +24351,8 @@  bool
 instantiating_current_function_p (void)
 {
   return (current_instantiation ()
-	  && current_instantiation ()->decl == current_function_decl);
+	  && (current_instantiation ()->get_decl_maybe ()
+	      == current_function_decl));
 }
 
 /* [temp.param] Check that template non-type parm TYPE is of an allowable



Just FTR.  count tinst_level objs et al

---
 gcc/cp/cp-tree.h |   50 ++++++++++++++++++++++++++++++++++++++++++++++++++
 gcc/cp/pt.c      |   25 ++++++++++++++++++++++---
 2 files changed, 72 insertions(+), 3 deletions(-)

diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index e9d9bab879bc..38de9b600f0d 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -5865,6 +5865,49 @@  struct cp_declarator {
   } u;
 };
 
+  struct consctr {
+    unsigned ctor, ctorl, dtor, dtorl, maxactive, maxactivel,
+      lastmark, lastmarkl, longestseq, longestseql, maxcnt, reused;
+    bool toreport;
+    void operator++() {
+      toreport = true;
+      ctor++;
+      maxactive = MAX (maxactive, ctor - dtor);
+      longestseq = MAX (longestseq, ctor - lastmark);
+    }
+    void operator--() { toreport = true; dtor++; }
+    void operator+() {
+      toreport = true;
+      ctorl++;
+      maxactivel = MAX (maxactivel, ctorl - dtorl);
+      longestseql = MAX (longestseql, ctorl - lastmarkl);
+    }
+    void operator-() {
+      toreport = true;
+      dtorl++;
+    }
+    void operator*() { report(); lastmark = ctor; lastmarkl = ctorl; }
+    void operator=(unsigned i) {
+      if (i > maxcnt)
+	toreport = true;
+      maxcnt = MAX (maxcnt, i);
+    }
+    void operator!() {
+      toreport = true;
+      reused++;
+    }
+    ~consctr() { report (); }
+    void report() {
+      if (toreport) {
+	printf ("TINST: ctor %u dtor %u max %u end %u long %u LST: ctor %u dtor %u max %u end %u long %u REFS: %u reused: %u\n",
+		ctor, dtor, maxactive, ctor - dtor, longestseq,
+		ctorl, dtorl, maxactivel, ctorl - dtorl, longestseql,
+		maxcnt, reused);
+	toreport = false;
+      }
+    }
+  };
+
 /* A level of template instantiation.  */
 struct GTY((chain_next ("%h.next"))) tinst_level {
   /* The immediately deeper level in the chain.  */
@@ -5932,6 +5975,13 @@  struct GTY((chain_next ("%h.next"))) tinst_level {
 
   /* Count references to this object.  */
   unsigned char refcount;
+
+  static struct consctr consctr;
+
+  static int resetctr () {
+    *consctr;
+    return 1;
+  }
 };
 
 bool decl_spec_seq_has_spec_p (const cp_decl_specifier_seq *, cp_decl_spec);
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index 75ed73890c4f..4db3bd49bf3f 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -8909,6 +8909,7 @@  tinst_level::to_list ()
   tldcl = ret;
   targs = NULL;
   gcc_assert (tree_list_p ());
+  +consctr;
   return ret;
 }
 
@@ -8917,7 +8918,7 @@  static tinst_level *
 inc_refcount_use (tinst_level *obj) {
   if (obj)
     {
-      ++obj->refcount;
+      obj->consctr = ++obj->refcount;
       gcc_assert (obj->refcount != 0);
     }
   return obj;
@@ -8930,10 +8931,14 @@  static void
 dec_refcount_use (tinst_level *obj) {
   while (obj && !--obj->refcount)
     {
+      --obj->consctr;
       gcc_assert (obj->refcount+1 != 0);
       tinst_level *next = obj->next;
       if (obj->list_p () && obj->get_decl_maybe ())
-	tree_list_freelist ().free (obj->get_node ());
+	{
+	  -obj->consctr;
+	  tree_list_freelist ().free (obj->get_node ());
+	}
       tinst_level_freelist ().free (obj);
       obj = next;
     }
@@ -10062,7 +10067,14 @@  static int tinst_depth;
 extern int max_tinst_depth;
 int depth_reached;
 
-static GTY(()) struct tinst_level *last_error_tinst_level;
+static GTY(()) struct tinst_level * last_error_tinst_level;
+
+struct consctr tinst_level::consctr;
+static hash_set<tinst_level *> used_ptrs;
+
+struct GTY(()) resetter {};
+static GTY((length ("tinst_level::resetctr ()")))
+  struct resetter *tinst_resetter;
 
 /* We're starting to instantiate D; record the template instantiation context
    at LOC for diagnostics and to restore it later.  */
@@ -10096,6 +10108,9 @@  push_tinst_level_loc (tree tldcl, tree targs, location_t loc)
       && TREE_CODE (tldcl) != FUNCTION_DECL)
     fprintf (stderr, " %s", decl_as_string (tldcl, TFF_DECL_SPECIFIERS));
 
+  if (!tinst_resetter)
+    tinst_resetter = ggc_cleared_alloc<resetter>();
+
   new_level = tinst_level_freelist ().alloc ();
   new_level->tldcl = tldcl;
   new_level->targs = targs;
@@ -10104,9 +10119,13 @@  push_tinst_level_loc (tree tldcl, tree targs, location_t loc)
   new_level->in_system_header_p = in_system_header_at (input_location);
   new_level->next = NULL;
   new_level->refcount = 0;
+  ++new_level->consctr;
   set_refcount_ptr (new_level->next, current_tinst_level);
   set_refcount_ptr (current_tinst_level, new_level);
 
+  if (!used_ptrs.add (new_level))
+    !tinst_level::consctr;
+
   ++tinst_depth;
   if (GATHER_STATISTICS && (tinst_depth > depth_reached))
     depth_reached = tinst_depth;