Re: [PATCH] Avoid needless unsharing during constexpr evaluation (PR c++/70452)

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

On Wed, Apr 6, 2016 at 1:17 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On April 6, 2016 6:51:40 PM GMT+02:00, Patrick Palka <patrick@parcs.ath.cx> wrote:
>>During constexpr evaluation we unconditionally call unshare_expr in a
>>bunch of places to ensure that CONSTRUCTORs (and their
>>CONSTRUCTOR_ELTS)
>>don't get shared.  But as far as I can tell, we don't have any reason
>>to
>>call unshare_expr on non-CONSTRUCTORs, and a CONSTRUCTOR will never be
>>an operand of a non-CONSTRUCTOR tree.  Assuming these two things are
>>true, then I think we can safely restrict the calls to unshare_expr to
>>only CONSTRUCTOR trees. Doing so saves 50MB of peak memory usage in the
>>test case in the PR (bringing memory usage down to 4.9 levels).
>>
>>This patch takes this idea a bit further and implements a custom
>>unshare_constructor procedure that recursively unshares just
>>CONSTRUCTORs and their CONSTRUCTOR elements.  This is in contrast to
>>unshare_expr which unshares even non-CONSTRUCTOR elements of a
>>CONSTRUCTOR.  unshare_constructor also has an assert which verifies
>>that
>>there really is no CONSTRUCTOR subexpression inside a non-CONSTRUCTOR
>>tree.  So far I haven't been able to get this assert to trigger which
>>makes me reasonably confident about this optimization.
>
> At least the middle end uses CONSTRUCTOR to build vectors from components which can then of course be operands of expressions.

I see... I was assuming that the expressions passed to unshare_expr
would be more or less normalized but of course if the expression
involves a non-constant operand then not much normalization can be
done. So the patch ICEs on the following test case because we don't
normalize <retval> = g (X { }) to <retval> = 5 since g is not
constexpr.  So we end up calling unshare_constructor on this CALL_EXPR
whose argument is a CONSTRUCTOR.

struct X { };

constexpr int
foo (int (*f) (X))
{
  return f (X { });
}

int
g (X)
{
  return 5;
}

int a = foo (g);

 So the added assert and probably this patch is wrong.  Hmm...

>
> Richard.
>
>>Does this look OK to commit after bootstrap + regtesting?
>>
>>gcc/cp/ChangeLog:
>>
>>       PR c++/70452
>>       * constexpr.c (not_a_constructor): New function.
>>       (unshare_constructor): New function.
>>       (cxx_eval_call_expression): Use unshare_constructor instead of
>>       unshare_expr.
>>       (find_array_ctor_elt): Likewise.
>>       (cxx_eval_vec_init_1): Likewise.
>>       (cxx_eval_store_expression): Likewise.
>>       (cxx_eval_constant_expression): Likewise.
>>---
>>gcc/cp/constexpr.c | 55
>>++++++++++++++++++++++++++++++++++++++++++++++--------
>> 1 file changed, 47 insertions(+), 8 deletions(-)
>>
>>diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
>>index 1c2701b..5d33a11 100644
>>--- a/gcc/cp/constexpr.c
>>+++ b/gcc/cp/constexpr.c
>>@@ -1151,6 +1151,45 @@ adjust_temp_type (tree type, tree temp)
>>   return cp_fold_convert (type, temp);
>> }
>>
>>+/* Callback for walk_tree used by unshare_constructor.  */
>>+
>>+static tree
>>+not_a_constructor (tree *tp, int *walk_subtrees, void *)
>>+{
>>+  if (TYPE_P (*tp))
>>+    *walk_subtrees = 0;
>>+  gcc_assert (TREE_CODE (*tp) != CONSTRUCTOR);
>>+  return NULL_TREE;
>>+}
>>+
>>+/* If T is a CONSTRUCTOR, return an unshared copy of T.  Otherwise
>>+   return T.  */
>>+
>>+static tree
>>+unshare_constructor (tree t)
>>+{
>>+  if (TREE_CODE (t) == CONSTRUCTOR)
>>+    {
>>+      tree r;
>>+
>>+      r = copy_node (t);
>>+      CONSTRUCTOR_ELTS (r) = vec_safe_copy (CONSTRUCTOR_ELTS (t));
>>+
>>+      /* Unshare any of its elements that also happen to be
>>CONSTRUCTORs.  */
>>+      for (unsigned idx = 0;
>>+         idx < vec_safe_length (CONSTRUCTOR_ELTS (r)); idx++)
>>+      CONSTRUCTOR_ELT (r, idx)->value
>>+        = unshare_constructor (CONSTRUCTOR_ELT (r, idx)->value);
>>+
>>+      return r;
>>+    }
>>+
>>+  /* If T is not itself a CONSTRUCTOR then we don't expect it to
>>contain
>>+     any CONSTRUCTOR subexpressions.  */
>>+  walk_tree_without_duplicates (&t, not_a_constructor, NULL);
>>+  return t;
>>+}
>>+
>> /* Subroutine of cxx_eval_call_expression.
>>    We are processing a call expression (either CALL_EXPR or
>>    AGGR_INIT_EXPR) in the context of CTX.  Evaluate
>>@@ -1454,7 +1493,7 @@ cxx_eval_call_expression (const constexpr_ctx
>>*ctx, tree t,
>>             tree arg = TREE_VALUE (bound);
>>             gcc_assert (DECL_NAME (remapped) == DECL_NAME (oparm));
>>             /* Don't share a CONSTRUCTOR that might be changed.  */
>>-            arg = unshare_expr (arg);
>>+            arg = unshare_constructor (arg);
>>             ctx->values->put (remapped, arg);
>>             bound = TREE_CHAIN (bound);
>>             remapped = DECL_CHAIN (remapped);
>>@@ -1534,7 +1573,7 @@ cxx_eval_call_expression (const constexpr_ctx
>>*ctx, tree t,
>>     }
>>
>>   pop_cx_call_context ();
>>-  return unshare_expr (result);
>>+  return unshare_constructor (result);
>> }
>>
>>/* FIXME speed this up, it's taking 16% of compile time on sieve
>>testcase.  */
>>@@ -1880,7 +1919,7 @@ find_array_ctor_elt (tree ary, tree dindex, bool
>>insert = false)
>>                 /* Append the element we want to insert.  */
>>                 ++middle;
>>                 e.index = dindex;
>>-                e.value = unshare_expr (elt.value);
>>+                e.value = unshare_constructor (elt.value);
>>                 vec_safe_insert (CONSTRUCTOR_ELTS (ary), middle, e);
>>               }
>>             else
>>@@ -1896,7 +1935,7 @@ find_array_ctor_elt (tree ary, tree dindex, bool
>>insert = false)
>>                   e.index = hi;
>>                 else
>>                   e.index = build2 (RANGE_EXPR, sizetype, new_lo, hi);
>>-                e.value = unshare_expr (elt.value);
>>+                e.value = unshare_constructor (elt.value);
>>                 vec_safe_insert (CONSTRUCTOR_ELTS (ary), middle+1, e);
>>               }
>>           }
>>@@ -2565,7 +2604,7 @@ cxx_eval_vec_init_1 (const constexpr_ctx *ctx,
>>tree atype, tree init,
>>         for (i = 1; i < max; ++i)
>>           {
>>             idx = build_int_cst (size_type_node, i);
>>-            CONSTRUCTOR_APPEND_ELT (*p, idx, unshare_expr (eltinit));
>>+            CONSTRUCTOR_APPEND_ELT (*p, idx, unshare_constructor
>>(eltinit));
>>           }
>>         break;
>>       }
>>@@ -3113,7 +3152,7 @@ cxx_eval_store_expression (const constexpr_ctx
>>*ctx, tree t,
>>   init = cxx_eval_constant_expression (&new_ctx, init, false,
>>                                      non_constant_p, overflow_p);
>>   /* Don't share a CONSTRUCTOR that might be changed later.  */
>>-  init = unshare_expr (init);
>>+  init = unshare_constructor (init);
>>   if (target == object)
>>     /* The hash table might have moved since the get earlier.  */
>>     valp = ctx->values->get (object);
>>@@ -3565,7 +3604,7 @@ cxx_eval_constant_expression (const constexpr_ctx
>>*ctx, tree t,
>>                                                false,
>>                                                non_constant_p, overflow_p);
>>           /* Don't share a CONSTRUCTOR that might be changed.  */
>>-          init = unshare_expr (init);
>>+          init = unshare_constructor (init);
>>           ctx->values->put (r, init);
>>         }
>>       else if (ctx == &new_ctx)
>>@@ -3610,7 +3649,7 @@ cxx_eval_constant_expression (const constexpr_ctx
>>*ctx, tree t,
>>       if (lval)
>>       {
>>         tree slot = TARGET_EXPR_SLOT (t);
>>-        r = unshare_expr (r);
>>+        r = unshare_constructor (r);
>>         ctx->values->put (slot, r);
>>         return slot;
>>       }
>
>