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

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

[Patrick Palka]

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.

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;
 	}
-- 
2.8.1.68.gbcddfe0

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

[Richard Biener]

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.

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;
> 	}

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

[Patrick Palka]

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;
>>       }
>
>

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

[Patrick Palka]

On Wed, 6 Apr 2016, Patrick Palka wrote:

> 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...

Here is a safer and simpler approach that just walks the expression
being unshared to try to find a CONSTRUCTOR node.  If it finds one, then
we unshare the whole expression.  Otherwise we return the original
expression.  It should be completely safe to avoid unsharing an
expression if it contains no CONSTRUCTOR nodes.

-- >8 --

gcc/cp/ChangeLog:

	PR c++/70452
	* constexpr.c (find_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 | 40 ++++++++++++++++++++++++++++++++--------
 1 file changed, 32 insertions(+), 8 deletions(-)

diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
index 1c2701b..5bccdec 100644
--- a/gcc/cp/constexpr.c
+++ b/gcc/cp/constexpr.c
@@ -1151,6 +1151,30 @@ adjust_temp_type (tree type, tree temp)
   return cp_fold_convert (type, temp);
 }
 
+/* Callback for walk_tree used by unshare_constructor.  */
+
+static tree
+find_constructor (tree *tp, int *walk_subtrees, void *)
+{
+  if (TYPE_P (*tp))
+    *walk_subtrees = 0;
+  if (TREE_CODE (*tp) == CONSTRUCTOR)
+    return *tp;
+  return NULL_TREE;
+}
+
+/* If T is a CONSTRUCTOR or an expression that has a CONSTRUCTOR node as a
+   subexpression, return an unshared copy of T.  Otherwise return T.  */
+
+static tree
+unshare_constructor (tree t)
+{
+  tree ctor = walk_tree (&t, find_constructor, NULL, NULL);
+  if (ctor != NULL_TREE)
+    return unshare_expr (t);
+  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 +1478,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 +1558,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 +1904,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 +1920,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 +2589,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 +3137,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 +3589,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 +3634,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;
 	}
-- 
2.8.1.68.gbcddfe0

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

[Jason Merrill]

OK.

Jason

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

[Markus Trippelsdorf]

On 2016.04.06 at 18:25 -0400, Patrick Palka wrote:
> On Wed, 6 Apr 2016, Patrick Palka wrote:
> Here is a safer and simpler approach that just walks the expression
> being unshared to try to find a CONSTRUCTOR node.  If it finds one, then
> we unshare the whole expression.  Otherwise we return the original
> expression.  It should be completely safe to avoid unsharing an
> expression if it contains no CONSTRUCTOR nodes.
> 
> gcc/cp/ChangeLog:
> 
> 	PR c++/70452
> 	* constexpr.c (find_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.

This patch causes: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=70590

-- 
Markus