[PATCH] c++: cxx_eval_vec_init after zero initialization [PR96282]

[Jason Merrill]

On 8/3/20 8:53 AM, Patrick Palka wrote:
> On Mon, 3 Aug 2020, Patrick Palka wrote:
> 
>> In the first testcase below, expand_aggr_init_1 sets up t's default
>> constructor such that the ctor first zero-initializes the entire base b,
>> followed by calling b's default constructor, the latter of which just
>> default-initializes the array member b::m via a VEC_INIT_EXPR.
>>
>> So upon constexpr evaluation of this latter VEC_INIT_EXPR, ctx->ctor is
>> nonempty due to the prior zero-initialization, and we proceed in
>> cxx_eval_vec_init to append new constructor_elts to the end of ctx->ctor
>> without first checking if a matching constructor_elt already exists.
>> This leads to ctx->ctor having two matching constructor_elts for each
>> index.
>>
>> This patch partially fixes this issue by making the RANGE_EXPR
>> optimization in cxx_eval_vec_init truncate ctx->ctor before adding the
>> single RANGE_EXPR constructor_elt.  This isn't a complete fix because
>> the RANGE_EXPR optimization applies only when the constant initializer
>> is relocatable, so whenever it's not relocatable we can still build up
>> an invalid CONSTRUCTOR, e.g. if in the first testcase we add an NSDMI
>> such as 'e *p = this;' to struct e, then the ICE still occurs even with
>> this patch.
> 
> A complete but more risky one-line fix would be to always truncate
> ctx->ctor beforehand, not just when the RANGE_EXPR optimization applies.
> If it's true that the initializer of a VEC_INIT_EXPR can't observe the
> previous elements of the target array, then it should be safe to always
> truncate I think?

What if default-initialization of the array element type doesn't fully 
initialize the elements, e.g. if 'e' had another member without a 
default initializer?  Does truncation first mean we lose the 
zero-initialization of such a member?

We could probably still do the truncation, but clear the 
CONSTRUCTOR_NO_CLEARING flag on the element initializer.

> Another complete fix would be to replace the uses of CONSTRUCTOR_APPEND_ELT
> with get_or_insert_ctor_field, which does the right thing when a
> matching constructor_elt already exists.  But get_or_insert_ctor_field
> was introduced only in GCC 10, .
> 
> I'm not sure which fix we should go with in light of this being an
> 8/9/10/11 regression..
> 
>>
>> A side benefit of the approach taken by this patch is that constexpr
>> evaluation of a simple VEC_INIT_EXPR for a high-dimensional array no
>> longer scales exponentially with the number of dimensions.  This is
>> because after the RANGE_EXPR optimization, the CONSTRUCTOR for each
>> array dimension now consists of a single constructor_elt (with index
>> 0...max-1) instead of two constructor_elts (with indexes 0 and 1...max-1
>> respectively).  This is verified by the second testcase below.
>>
>> Bootstrapped and regtested on x86_64-pc-linux-gnu.  Does this look OK
>> for trunk and perhaps for backports?
>>
>> gcc/cp/ChangeLog:
>>
>> 	PR c++/96282
>> 	* constexpr.c (cxx_eval_vec_init_1): Move the i == 0 test to the
>> 	if statement that guards the RANGE_EXPR optimization. Consider the
>> 	RANGE_EXPR optimization before we append the first element.
>> 	Truncate ctx->ctor when performing the RANGE_EXPR optimization.
>> 	Make the built RANGE_EXPR start at index 0 instead of 1.  Don't
>> 	call unshare_constructor.
>>
>> gcc/testsuite/ChangeLog:
>>
>> 	PR c++/96282
>> 	* g++.dg/cpp0x/constexpr-array26.C: New test.
>> 	* g++.dg/cpp0x/constexpr-array27.C: New test.
>> ---
>>   gcc/cp/constexpr.c                            | 36 ++++++++++---------
>>   .../g++.dg/cpp0x/constexpr-array26.C          | 13 +++++++
>>   .../g++.dg/cpp0x/constexpr-array27.C          | 18 ++++++++++
>>   3 files changed, 51 insertions(+), 16 deletions(-)
>>   create mode 100644 gcc/testsuite/g++.dg/cpp0x/constexpr-array26.C
>>   create mode 100644 gcc/testsuite/g++.dg/cpp0x/constexpr-array27.C
>>
>> diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
>> index b1c1d249c6e..3808a0713ba 100644
>> --- a/gcc/cp/constexpr.c
>> +++ b/gcc/cp/constexpr.c
>> @@ -4189,7 +4189,7 @@ cxx_eval_vec_init_1 (const constexpr_ctx *ctx, tree atype, tree init,
>>   	  if (value_init || init == NULL_TREE)
>>   	    {
>>   	      eltinit = NULL_TREE;
>> -	      reuse = i == 0;
>> +	      reuse = true;
>>   	    }
>>   	  else
>>   	    eltinit = cp_build_array_ref (input_location, init, idx, complain);
>> @@ -4206,7 +4206,7 @@ cxx_eval_vec_init_1 (const constexpr_ctx *ctx, tree atype, tree init,
>>   	    return ctx->ctor;
>>   	  eltinit = cxx_eval_constant_expression (&new_ctx, init, lval,
>>   						  non_constant_p, overflow_p);
>> -	  reuse = i == 0;
>> +	  reuse = true;
>>   	}
>>         else
>>   	{
>> @@ -4222,33 +4222,37 @@ cxx_eval_vec_init_1 (const constexpr_ctx *ctx, tree atype, tree init,
>>   	}
>>         if (*non_constant_p && !ctx->quiet)
>>   	break;
>> -      if (new_ctx.ctor != ctx->ctor)
>> -	{
>> -	  /* We appended this element above; update the value.  */
>> -	  gcc_assert ((*p)->last().index == idx);
>> -	  (*p)->last().value = eltinit;
>> -	}
>> -      else
>> -	CONSTRUCTOR_APPEND_ELT (*p, idx, eltinit);
>> +
>>         /* Reuse the result of cxx_eval_constant_expression call
>>   	 from the first iteration to all others if it is a constant
>>   	 initializer that doesn't require relocations.  */
>> -      if (reuse
>> -	  && max > 1
>> +      if (i == 0
>> +	  && reuse
>>   	  && (eltinit == NULL_TREE
>>   	      || (initializer_constant_valid_p (eltinit, TREE_TYPE (eltinit))
>>   		  == null_pointer_node)))
>>   	{
>>   	  if (new_ctx.ctor != ctx->ctor)
>>   	    eltinit = new_ctx.ctor;
>> -	  tree range = build2 (RANGE_EXPR, size_type_node,
>> -			       build_int_cst (size_type_node, 1),
>> -			       build_int_cst (size_type_node, max - 1));
>> -	  CONSTRUCTOR_APPEND_ELT (*p, range, unshare_constructor (eltinit));
>> +	  vec_safe_truncate (*p, 0);
>> +	  if (max > 1)
>> +	    idx = build2 (RANGE_EXPR, size_type_node,
>> +			  build_int_cst (size_type_node, 0),
>> +			  build_int_cst (size_type_node, max - 1));
>> +	  CONSTRUCTOR_APPEND_ELT (*p, idx, eltinit);
>>   	  break;
>>   	}
>>         else if (i == 0)
>>   	vec_safe_reserve (*p, max);
>> +
>> +      if (new_ctx.ctor != ctx->ctor)
>> +	{
>> +	  /* We appended this element above; update the value.  */
>> +	  gcc_assert ((*p)->last().index == idx);
>> +	  (*p)->last().value = eltinit;
>> +	}
>> +      else
>> +	CONSTRUCTOR_APPEND_ELT (*p, idx, eltinit);
>>       }
>>   
>>     if (!*non_constant_p)
>> diff --git a/gcc/testsuite/g++.dg/cpp0x/constexpr-array26.C b/gcc/testsuite/g++.dg/cpp0x/constexpr-array26.C
>> new file mode 100644
>> index 00000000000..274f55a88bf
>> --- /dev/null
>> +++ b/gcc/testsuite/g++.dg/cpp0x/constexpr-array26.C
>> @@ -0,0 +1,13 @@
>> +// PR c++/96282
>> +// { dg-do compile { target c++11 } }
>> +
>> +struct e { bool v = true; };
>> +
>> +template<int N>
>> +struct b { e m[N]; };
>> +
>> +template<int N>
>> +struct t : b<N> { constexpr t() : b<N>() {} };
>> +
>> +constexpr t<1> h1;
>> +constexpr t<42> h2;
>> diff --git a/gcc/testsuite/g++.dg/cpp0x/constexpr-array27.C b/gcc/testsuite/g++.dg/cpp0x/constexpr-array27.C
>> new file mode 100644
>> index 00000000000..a5ce3f7be08
>> --- /dev/null
>> +++ b/gcc/testsuite/g++.dg/cpp0x/constexpr-array27.C
>> @@ -0,0 +1,18 @@
>> +// Verify that default initialization an array of aggregates within an aggregate
>> +// does not scale exponentially with the number of dimensions.
>> +
>> +// { dg-do compile { target c++11 } }
>> +// Pass -fsyntax-only to stress only the performance of the frontend.
>> +// { dg-additional-options "-fsyntax-only" }
>> +
>> +struct A
>> +{
>> +  int a = 42;
>> +};
>> +
>> +struct B
>> +{
>> +  A b[2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2];
>> +};
>> +
>> +constexpr B c;
>> -- 
>> 2.28.0.89.g85b4e0a6dc
>>
>>
>