Re: [PATCH] Fix PR c++/70452 (regression in C++ parsing performance)

[Patrick Palka <patrick at parcs dot ath dot cx>]

On Fri, Apr 1, 2016 at 3:13 PM, Patrick Palka <patrick@parcs.ath.cx> wrote:
> Currently during constexpr CALL_EXPR evaluation we create a new copy of
> the callee function's body for each separate call with no attempt made
> at reusing the function body.  So when a function ends up getting called
> 10s of thousands of times durnig constexpr evaluuation, we end up
> creating 10s of thousands of copies of the function.
>
> This patch is an attempt at reusing these copies instead of having a new
> copy get created each call.  It implements a per-function freelist of
> the unshared body/parm/res copies that were created by copy_fn().  When
> a constexpr call is finished it pushes the body/parm/res trees to the
> freelist, and before a call is evaluated it tries to reuse the trees
> from the freelist, falling back to copy_fn() only if the freelist is
> empty.
>
> Consequently, instead of creating 10s of thousands of copies for 10s of
> thousands of calls, the number of copies that're made corresponds to the
> recursion depth of the function.  This makes sense because the reason we
> create copies in the first place (IIUC) is to ensure that recursive
> calls to a function do not share the same
> PARM_DECLs/VAR_DECLs/RESULT_DECLs.
>
> In order for this reuse to work properly in the presence of SAVE_EXPRs,
> we have to track each SAVE_EXPR (belonging to the callee) that we
> evaluate during the call and then forget its value after the call.
> constexpr-vla4.C is a new test that would fail if this patch had missed
> this SAVE_EXPR part.
>
> With this patch, the compile time of the test case in the PR gets cut
> from 3.5s to 2s and memory usage gets cut from 550M to 200M.
>
> I bootstrapped + regtested this change on x86_64-pc-linux-gnu, and also
> compile-tested it against boost with no regressions.
>
> gcc/cp/ChangeLog:
>
>         PR c++/70452
>         * constexpr.c (struct bpr_entry): New struct.
>         (struct constexpr_fundef): New field bpr_freelist.
>         (retrieve_constexpr_fundef): Initialize field bpr_freelist to
>         NULL.
>         (register_constexpr_fundef): Likewise.
>         (cxx_eval_call_expression): Check constexpr_fundef::bpr_freelist
>         for a reusable copy of the function's body before creating a new
>         copy.  Keep track of the callee's SAVE_EXPRs that we evaluate
>         and forget their values afterwards. Push the function body we
>         used onto the freelist for later reuse.
>
> gcc/testsuite/ChangeLog:
>
>         PR c++/70452
>         * g++.dg/ext/constexpr-vla4.C: New test.
> ---
>  gcc/cp/constexpr.c                        | 55 ++++++++++++++++++++++++++++---
>  gcc/testsuite/g++.dg/ext/constexpr-vla4.C | 17 ++++++++++
>  2 files changed, 67 insertions(+), 5 deletions(-)
>  create mode 100644 gcc/testsuite/g++.dg/ext/constexpr-vla4.C
>
> diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
> index ea605dc..fc9b67c 100644
> --- a/gcc/cp/constexpr.c
> +++ b/gcc/cp/constexpr.c
> @@ -112,11 +112,24 @@ ensure_literal_type_for_constexpr_object (tree decl)
>    return decl;
>  }
>
> +/* The representation of a single node in the constexpr_fundef::bpr_freelist chain.  */
> +
> +struct GTY((chain_next ("%h.prev"))) bpr_entry
> +{
> +  tree body;
> +  tree parms;
> +  tree res;
> +  struct bpr_entry *prev;
> +};
> +
>  /* Representation of entries in the constexpr function definition table.  */
>
>  struct GTY((for_user)) constexpr_fundef {
>    tree decl;
>    tree body;
> +  /* A chain of unused copies of this function's body awaiting reuse for
> +     CALL_EXPR evaluation.  */
> +  struct bpr_entry *bpr_freelist;
>  };
>
>  struct constexpr_fundef_hasher : ggc_ptr_hash<constexpr_fundef>
> @@ -154,7 +167,7 @@ constexpr_fundef_hasher::hash (constexpr_fundef *fundef)
>  static constexpr_fundef *
>  retrieve_constexpr_fundef (tree fun)
>  {
> -  constexpr_fundef fundef = { NULL, NULL };
> +  constexpr_fundef fundef = { NULL, NULL, NULL };
>    if (constexpr_fundef_table == NULL)
>      return NULL;
>
> @@ -806,6 +819,7 @@ register_constexpr_fundef (tree fun, tree body)
>
>    entry.decl = fun;
>    entry.body = body;
> +  entry.bpr_freelist = NULL;
>    slot = constexpr_fundef_table->find_slot (&entry, INSERT);
>
>    gcc_assert (*slot == NULL);
> @@ -1377,10 +1391,21 @@ cxx_eval_call_expression (const constexpr_ctx *ctx, tree t,
>        if (!result || result == error_mark_node)
>         {
>           gcc_assert (DECL_SAVED_TREE (fun));
> -         tree parms, res;
> +         tree body, parms, res;
>
> -         /* Unshare the whole function body.  */
> -         tree body = copy_fn (fun, parms, res);
> +         /* Reuse or create a new unshared copy of this function's body.  */
> +         if (bpr_entry *bpr = new_call.fundef->bpr_freelist)
> +           {
> +             body = bpr->body;
> +             parms = bpr->parms;
> +             res = bpr->res;
> +             new_call.fundef->bpr_freelist = bpr->prev;
> +           }
> +         else
> +           {
> +             /* Unshare the whole function body.  */
> +             body = copy_fn (fun, parms, res);
> +           }
>
>           /* Associate the bindings with the remapped parms.  */
>           tree bound = new_call.bindings;
> @@ -1409,11 +1434,22 @@ cxx_eval_call_expression (const constexpr_ctx *ctx, tree t,
>           else
>             ctx->values->put (res, NULL_TREE);
>
> +         /* Track the SAVE_EXPRs of the callee that we evaluate so that
> +            we can later forget their values.  */
> +         constexpr_ctx ctx_with_save_exprs = *ctx;
> +         hash_set<tree> save_exprs;
> +         ctx_with_save_exprs.save_exprs = &save_exprs;

Didn't like the way this comment is worded so I changed it to

+         /* Track the callee's evaluated SAVE_EXPRs so that we can forget
+            their values after the call.  */