[PATCH] c++: Improve RANGE_EXPR optimization in cxx_eval_vec_init

Jason Merrill jason@redhat.com
Tue Aug 11 18:57:09 GMT 2020


On 8/10/20 9:21 AM, Patrick Palka wrote:
> On Fri, 7 Aug 2020, Jason Merrill wrote:
> 
>> On 8/6/20 1:50 PM, Patrick Palka wrote:
>>> This patch eliminates an exponential dependence in cxx_eval_vec_init on
>>> the array dimension of a VEC_INIT_EXPR when the RANGE_EXPR optimization
>>> applies.  This is achieved by using a single constructor_elt (with index
>>> RANGE_EXPR 0...max-1) per dimension instead of two constructor_elts
>>> (with index 0 and RANGE_EXPR 1...max-1 respectively).  In doing so, we
>>> can also get rid of the call to unshare_constructor since the element
>>> initializer now gets used in exactly one spot.
>>>
>>> The patch also removes the 'eltinit = new_ctx.ctor' assignment within the
>>> RANGE_EXPR optimization since eltinit should already always be equal to
>>> new_ctx.ctor here (modulo encountering an error when computing eltinit).
>>> This was verified by running the testsuite against an appropriate assert.
>>
>> Maybe keep that assert?
> 
> FWIW, the assert was
> 
>    gcc_assert (*non_constant_p || eltinit == new_ctx->ctor);
> 
> and apparently it survives the testsuite when added to either the
> RANGE_EXPR or non-RANGE_EXPR code paths in cxx_eval_vec_init.
> 
> I then tried adding an analogous assert to cxx_eval_bare_aggregate, but
> this assert triggers for lots of our testcases, in particular when (but
> not only when) an elt initializer is already a reduced constant
> CONSTRUCTOR (since then cxx_eval_constant_expression just returns this
> already-reduced CONSTRUCTOR without updating ctx->ctor).
> 
> I'm not sure why the assert should necessarily hold in cxx_eval_vec_init
> but not in cxx_eval_bare_aggregate.  I guess we never see a
> VEC_INIT_EXPR whose elt initializer is a reduced constant CONSTRUCTOR or
> similar?

That sounds like a plausible reason.

>>
>>> Finally, this patch reverses the sense of the ctx->quiet test that
>>> controls whether to short-circuit evaluation upon seeing an error.  This
>>> should speed up speculative evaluation of non-constant VEC_INIT_EXPRs
>>> (since ctx->quiet is true then).  I'm not sure why we were testing
>>> !ctx->quiet originally; it's inconsistent with how we short-circuit in
>>> other spots.
>>
>> Good question.  That code seems to go back to the initial implementation of
>> constexpr.
>>
>>    I contrived the testcase array60.C below which verifies
>>> that we now short-circuit quickly.
>>>
>>> Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK to
>>> commit?
>>>
>>> gcc/cp/ChangeLog:
>>>
>>> 	* constexpr.c (cxx_eval_vec_init_1): Move the i == 0 test to the
>>> 	if statement that guards the RANGE_EXPR optimization.  Invert
>>> 	the ctx->quiet test. Apply the RANGE_EXPR optimization before we
>>> 	append the first element initializer.  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:
>>>
>>> 	* g++.dg/cpp0x/constexpr-array28.C: New test.
>>> 	* g++.dg/init/array60.C: New test.
>>> ---
>>>    gcc/cp/constexpr.c                            | 34 ++++++++++---------
>>>    .../g++.dg/cpp0x/constexpr-array28.C          | 14 ++++++++
>>>    gcc/testsuite/g++.dg/init/array60.C           | 13 +++++++
>>>    3 files changed, 45 insertions(+), 16 deletions(-)
>>>    create mode 100644 gcc/testsuite/g++.dg/cpp0x/constexpr-array28.C
>>>    create mode 100644 gcc/testsuite/g++.dg/init/array60.C
>>>
>>> diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
>>> index ab747a58fa0..e67ce5da355 100644
>>> --- a/gcc/cp/constexpr.c
>>> +++ b/gcc/cp/constexpr.c
>>> @@ -4205,7 +4205,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);
>>> @@ -4222,7 +4222,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;

The patch seems to replace checking i == 0 here with checking it in the 
condition below, which seems equivalent.  Why?

>>>    	}
>>>          else
>>>    	{
>>> @@ -4236,35 +4236,37 @@ cxx_eval_vec_init_1 (const constexpr_ctx *ctx, tree
>>> atype, tree init,
>>>    	  eltinit = cxx_eval_constant_expression (&new_ctx, eltinit, lval,
>>>    						  non_constant_p, overflow_p);
>>>    	}
>>> -      if (*non_constant_p && !ctx->quiet)
>>> +      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
>>> +      if (i == 0
>>> +	  && reuse
>>>    	  && max > 1
>>>    	  && (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, 0),
>>>    			       build_int_cst (size_type_node, max - 1));
>>> -	  CONSTRUCTOR_APPEND_ELT (*p, range, unshare_constructor (eltinit));
>>> +	  vec_safe_truncate (*p, 0);
>>> +	  CONSTRUCTOR_APPEND_ELT (*p, range, 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;
>>
>> So if eltinit already == new_ctx.ctor, this doesn't change anything?
> 
> Hmm, good point.  I should take back saying that eltinit must already
> equal new_ctx.ctor here, because I'm not convinced that/why it's true
> (besides the experimental evidence) :)
> 
> It still seems surprising that we prefer the value of new_ctx.ctor over
> the return value of cxx_eval_constant_expression in the RANGE_EXPR code
> path after evaluating a sub-agregate initializer, but not in the
> non-RANGE_EXPR path and also not in cxx_eval_bare_aggregate.  But I
> guess if it ain't broke, don't fix it, so maybe the patch should just
> leave alone the 'eltinit = new_ctx.ctor' assignment?

It would be good for this and cxx_eval_bare_aggregate to work more 
similarly.  As you point out, b_a doesn't rely on new_ctx->ctor at all, 
which seems important for the cases you mention where adding the assert 
there failed.  So I think removing the assignment is an improvement. 
Jakub, you don't happen to remember why you added it, do you?

>>> +	}
>>> +      else
>>> +	CONSTRUCTOR_APPEND_ELT (*p, idx, eltinit);
>>>        }
>>>        if (!*non_constant_p)
>>> diff --git a/gcc/testsuite/g++.dg/cpp0x/constexpr-array28.C
>>> b/gcc/testsuite/g++.dg/cpp0x/constexpr-array28.C
>>> new file mode 100644
>>> index 00000000000..f844926e32b
>>> --- /dev/null
>>> +++ b/gcc/testsuite/g++.dg/cpp0x/constexpr-array28.C
>>> @@ -0,0 +1,14 @@
>>> +// { dg-do compile { target c++11 } }
>>> +
>>> +struct A { int i = 42; };
>>> +
>>> +struct B
>>> +{
>>> +  A
>>> a[2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2];
>>> +};
>>> +
>>> +void f() {
>>> +  // Verify default initialization here does not scale exponentially
>>> +  // with the number of array dimensions.
>>> +  constexpr B b;
>>> +}
>>> diff --git a/gcc/testsuite/g++.dg/init/array60.C
>>> b/gcc/testsuite/g++.dg/init/array60.C
>>> new file mode 100644
>>> index 00000000000..22bd750f8e6
>>> --- /dev/null
>>> +++ b/gcc/testsuite/g++.dg/init/array60.C
>>> @@ -0,0 +1,13 @@
>>> +struct A { int i; };
>>> +
>>> +struct B
>>> +{
>>> +  virtual void f();
>>> +  A a[10000000];
>>> +};
>>> +
>>> +extern B b;
>>> +
>>> +// Verify that speculative constexpr evaluation of this non-constant
>>> +// initializer does not scale with the size of the array member 'a'.
>>> +B b2 (b);
>>>
>>
>>
> 



More information about the Gcc-patches mailing list