c++: Handle CONSTRUCTORs without indexes in find_array_ctor_elt [PR93549]

Hi!

My change
* typeck2.c (store_init_value): Don't call cp_fully_fold_init on
initializers of automatic non-constexpr variables in constexpr
functions.
-  value = cp_fully_fold_init (value);
+  /* Don't fold initializers of automatic variables in constexpr functions,
+     that might fold away something that needs to be diagnosed at constexpr
+     evaluation time.  */
+  if (!current_function_decl
+      || !DECL_DECLARED_CONSTEXPR_P (current_function_decl)
+      || TREE_STATIC (decl))
+    value = cp_fully_fold_init (value);
from the constexpr new change apparently broke the following testcase.
When handling COND_EXPR, we build_vector_from_val, however as the argument we
pass to it is not an INTEGER_CST/REAL_CST, but that wrapped in a
NON_LVALUE_EXPR location wrapper, we end up with a CONSTRUCTOR and as it is
middle-end that builds it, it doesn't bother with indexes.  The
cp_fully_fold_init call used to fold it into VECTOR_CST in the past, but as
we intentionally don't invoke it anymore as it might fold away something
that needs to be diagnosed during constexpr evaluation, we end up evaluating
ARRAY_REF into the index-less CONSTRUCTOR.  The following patch fixes the
ICE by teaching find_array_ctor_elt to handle CONSTRUCTORs without indexes
(that itself could be still very efficient) and CONSTRUCTORs with some
indexes present and others missing (the rules are that if the index on the
first element is missing, then it is the array's lowest index (in C/C++ 0)
and if other indexes are missing, they are the index of the previous element
+ 1).

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

Slightly OT, for large arrays it might be efficient to leave indexes out of
the CONSTRUCTORs too, but as the patch shows, we can't then access the
elements using binary search.  Could we (for GCC11+) use either some flag on
the CONSTRUCTOR to denote CONSTRUCTORs with no indexes at all, or some new
tree as index on the first element that would be similar to RANGE_EXPR, but
would say this element has index xyz and the following n elements have
linearly increasing indexes omitted?  If we have such an assurance, we could
do direct access to access the array elts in such CONSTRUCTORs and be even
more efficient than binary search.

2020-02-04  Jakub Jelinek  <jakub@redhat.com>

	PR c++/93549
	* constexpr.c (find_array_ctor_elt): Deal with some or all indexes in
	CONSTRUCTOR missing.

	* g++.dg/ext/constexpr-pr93549.C: New test.


	Jakub

On 2/4/20 4:20 AM, Jakub Jelinek wrote:
> Hi!
> 
> My change
> * typeck2.c (store_init_value): Don't call cp_fully_fold_init on
> initializers of automatic non-constexpr variables in constexpr
> functions.
> -  value = cp_fully_fold_init (value);
> +  /* Don't fold initializers of automatic variables in constexpr functions,
> +     that might fold away something that needs to be diagnosed at constexpr
> +     evaluation time.  */
> +  if (!current_function_decl
> +      || !DECL_DECLARED_CONSTEXPR_P (current_function_decl)
> +      || TREE_STATIC (decl))
> +    value = cp_fully_fold_init (value);
> from the constexpr new change apparently broke the following testcase.
> When handling COND_EXPR, we build_vector_from_val, however as the argument we
> pass to it is not an INTEGER_CST/REAL_CST, but that wrapped in a
> NON_LVALUE_EXPR location wrapper, we end up with a CONSTRUCTOR and as it is
> middle-end that builds it, it doesn't bother with indexes.  The
> cp_fully_fold_init call used to fold it into VECTOR_CST in the past, but as
> we intentionally don't invoke it anymore as it might fold away something
> that needs to be diagnosed during constexpr evaluation, we end up evaluating
> ARRAY_REF into the index-less CONSTRUCTOR.  The following patch fixes the
> ICE by teaching find_array_ctor_elt to handle CONSTRUCTORs without indexes
> (that itself could be still very efficient) and CONSTRUCTORs with some
> indexes present and others missing (the rules are that if the index on the
> first element is missing, then it is the array's lowest index (in C/C++ 0)
> and if other indexes are missing, they are the index of the previous element
> + 1).

Is it currently possible to get a CONSTRUCTOR with non-init-list type 
that has some indexes present and others missing?  Other than from the 
new code in your patch that sets some indexes?

> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
> 
> Slightly OT, for large arrays it might be efficient to leave indexes out of
> the CONSTRUCTORs too, but as the patch shows, we can't then access the
> elements using binary search.

> Could we (for GCC11+) use either some flag on
> the CONSTRUCTOR to denote CONSTRUCTORs with no indexes at all, or some new
> tree as index on the first element that would be similar to RANGE_EXPR, but
> would say this element has index xyz and the following n elements have
> linearly increasing indexes omitted?  If we have such an assurance, we could
> do direct access to access the array elts in such CONSTRUCTORs and be even
> more efficient than binary search.

Is it unreasonable to assume that if the first element has no index, 
none of the elements do?

> 2020-02-04  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR c++/93549
> 	* constexpr.c (find_array_ctor_elt): Deal with some or all indexes in
> 	CONSTRUCTOR missing.
> 
> 	* g++.dg/ext/constexpr-pr93549.C: New test.
> 
> --- gcc/cp/constexpr.c.jj	2020-01-26 00:20:26.532367552 +0100
> +++ gcc/cp/constexpr.c	2020-02-03 17:14:21.520780109 +0100
> @@ -3023,7 +3023,8 @@ find_array_ctor_elt (tree ary, tree dind
>     if (end > 0)
>       {
>         tree cindex = (*elts)[end - 1].index;
> -      if (TREE_CODE (cindex) == INTEGER_CST
> +      if (cindex
> +	  && TREE_CODE (cindex) == INTEGER_CST
>   	  && compare_tree_int (cindex, end - 1) == 0)
>   	{
>   	  if (i < end)
> @@ -3037,8 +3038,32 @@ find_array_ctor_elt (tree ary, tree dind
>     while (begin != end)
>       {
>         unsigned HOST_WIDE_INT middle = (begin + end) / 2;
> -      constructor_elt &elt = (*elts)[middle];
> -      tree idx = elt.index;
> +      constructor_elt *elt = &(*elts)[middle];
> +      tree idx = elt->index;
> +
> +      if (idx == NULL_TREE)
> +	{
> +	  /* If some or all indexes are missing, we can't use binary search.  */
> +	  unsigned HOST_WIDE_INT j
> +	    = (begin > 0 ? tree_to_uhwi ((*elts)[begin - 1].index) + 1 : 0);
> +	  for (middle = begin; middle < end; middle++)
> +	    if ((*elts)[middle].index)
> +	      {
> +		elt = &(*elts)[middle];
> +		idx = elt->index;
> +		break;
> +	      }
> +	    else if (i == j + (middle - begin))
> +	      {
> +		(*elts)[middle].index = dindex;

Why set this index?

> +		return middle;
> +	      }
> +	  if (middle == end)
> +	    {
> +	      begin = end;
> +	      continue;
> +	    }
> +	}
>   
>         int cmp = array_index_cmp (dindex, idx);
>         if (cmp < 0)
> @@ -3053,7 +3078,7 @@ find_array_ctor_elt (tree ary, tree dind
>   	      constructor_elt e;
>   	      tree lo = TREE_OPERAND (idx, 0);
>   	      tree hi = TREE_OPERAND (idx, 1);
> -	      tree value = elt.value;
> +	      tree value = elt->value;
>   	      dindex = fold_convert (sizetype, dindex);
>   	      if (tree_int_cst_lt (lo, dindex))
>   		{
> @@ -3062,7 +3087,7 @@ find_array_ctor_elt (tree ary, tree dind
>   						 size_one_node);
>   		  if (tree_int_cst_equal (lo, new_hi))
>   		    /* Only one element left, no longer a range.  */
> -		    elt.index = lo;
> +		    elt->index = lo;
>   		  else
>   		    TREE_OPERAND (idx, 1) = new_hi;
>   		  /* Append the element we want to insert.  */
> @@ -3073,7 +3098,7 @@ find_array_ctor_elt (tree ary, tree dind
>   		}
>   	      else
>   		/* No lower elts, the range elt is now ours.  */
> -		elt.index = dindex;
> +		elt->index = dindex;
>   
>   	      if (tree_int_cst_lt (dindex, hi))
>   		{
> --- gcc/testsuite/g++.dg/ext/constexpr-pr93549.C.jj	2020-02-03 17:19:30.083234827 +0100
> +++ gcc/testsuite/g++.dg/ext/constexpr-pr93549.C	2020-02-03 17:18:30.177117265 +0100
> @@ -0,0 +1,26 @@
> +// PR c++/93549
> +// { dg-do compile { target c++17 } }
> +// { dg-options "-O2 -Wno-psabi -w" }
> +
> +struct simd {
> +  using shortx8 [[gnu::vector_size(16)]] = short;
> +  shortx8 data;
> +  constexpr simd (short x) : data{x, x, x, x, x, x, x, x} {}
> +  constexpr friend unsigned operator== (simd lhs, simd rhs)
> +  {
> +    shortx8 tmp = lhs.data == rhs.data;
> +    using ushort = unsigned short;
> +    auto bools = tmp ? ushort(1) : ushort(0);
> +    unsigned bits = 0;
> +    for (int i = 0; i < 8; ++i)
> +      bits |= bools[i] << i;
> +    return bits;
> +  }
> +};
> +
> +auto
> +foo ()
> +{
> +  constexpr auto tmp = simd(1) == simd(2);
> +  return tmp;
> +}
> 
> 	Jakub
>

On Wed, Feb 05, 2020 at 01:31:30PM -0500, Jason Merrill wrote:
> > from the constexpr new change apparently broke the following testcase.
> > When handling COND_EXPR, we build_vector_from_val, however as the argument we
> > pass to it is not an INTEGER_CST/REAL_CST, but that wrapped in a
> > NON_LVALUE_EXPR location wrapper, we end up with a CONSTRUCTOR and as it is
> > middle-end that builds it, it doesn't bother with indexes.  The
> > cp_fully_fold_init call used to fold it into VECTOR_CST in the past, but as
> > we intentionally don't invoke it anymore as it might fold away something
> > that needs to be diagnosed during constexpr evaluation, we end up evaluating
> > ARRAY_REF into the index-less CONSTRUCTOR.  The following patch fixes the
> > ICE by teaching find_array_ctor_elt to handle CONSTRUCTORs without indexes
> > (that itself could be still very efficient) and CONSTRUCTORs with some
> > indexes present and others missing (the rules are that if the index on the
> > first element is missing, then it is the array's lowest index (in C/C++ 0)
> > and if other indexes are missing, they are the index of the previous element
> > + 1).
> 
> Is it currently possible to get a CONSTRUCTOR with non-init-list type that
> has some indexes present and others missing?  Other than from the new code
> in your patch that sets some indexes?

I don't know, can try to add some instrumentation and do bootstrap/regtest
with it.  The handling of the CONSTRUCTORs with missing or present or mixed
indexes is what I found in various middle-end routines.
The only thing I see in our verifiers is that in GIMPLE function bodies,
we don't allow non-VECTOR_TYPE CONSTRUCTORs with any elements, and for
VECTOR_TYPE CONSTRUCTORs we require that indexes are NULL for elements with
VECTOR_TYPE and for others require that it is either NULL or INTEGER_CST
matching the position (so effectively for those direct access is still
possible).
The question might not be just what we do emit right now, but also what we'd
like to emit in the future, because as has been noted several times, for
large initializers those explicit indexes consume huge amounts of memory.
In C with designated initializers, I can see us not emitting indexes from
the start because we'd want to avoid the memory overhead for normal
sequential initializers, but then much later we can find a designated
initializer that wants to skip over some elements and thus add an index at
that point (or range designator for which we want RANGE_EXPR); shall we add
indexes to all elements at that point?
In C++, I think we don't allow non-useless array designated initializers, so
there is no way to skip elements using that or go backwards, but still,
don't we emit RANGE_EXPRs if we see the same initializer for many elements?
I guess right now we emit indexes for all elements for those, but if we
choose to optimize?

> Is it unreasonable to assume that if the first element has no index, none of
> the elements do?

Not sure, see above.  Depends on what we want to guarantee.

> > +	    else if (i == j + (middle - begin))
> > +	      {
> > +		(*elts)[middle].index = dindex;
> 
> Why set this index?

Because the caller asserts or relies that it has one.
      constructor_elt *cep = NULL;
      if (code == ARRAY_TYPE)
        {
          HOST_WIDE_INT i
            = find_array_ctor_elt (*valp, index, /*insert*/true);
          gcc_assert (i >= 0);
          cep = CONSTRUCTOR_ELT (*valp, i);
          gcc_assert (TREE_CODE (cep->index) != RANGE_EXPR);

Now, ATM we are aware of just small CONSTRUCTORs that can appear this way
(VECTOR_TYPE and so generally not too many elements in real-world
testcases), so if you prefer, the function when seeing NULL index could just
add indexes to all elements and retry and defer deciding if and how we
optimize large constructors for later.

	Jakub

On Thu, 6 Feb 2020, Jakub Jelinek wrote:

> On Wed, Feb 05, 2020 at 01:31:30PM -0500, Jason Merrill wrote:
> > > from the constexpr new change apparently broke the following testcase.
> > > When handling COND_EXPR, we build_vector_from_val, however as the argument we
> > > pass to it is not an INTEGER_CST/REAL_CST, but that wrapped in a
> > > NON_LVALUE_EXPR location wrapper, we end up with a CONSTRUCTOR and as it is
> > > middle-end that builds it, it doesn't bother with indexes.  The
> > > cp_fully_fold_init call used to fold it into VECTOR_CST in the past, but as
> > > we intentionally don't invoke it anymore as it might fold away something
> > > that needs to be diagnosed during constexpr evaluation, we end up evaluating
> > > ARRAY_REF into the index-less CONSTRUCTOR.  The following patch fixes the
> > > ICE by teaching find_array_ctor_elt to handle CONSTRUCTORs without indexes
> > > (that itself could be still very efficient) and CONSTRUCTORs with some
> > > indexes present and others missing (the rules are that if the index on the
> > > first element is missing, then it is the array's lowest index (in C/C++ 0)
> > > and if other indexes are missing, they are the index of the previous element
> > > + 1).
> > 
> > Is it currently possible to get a CONSTRUCTOR with non-init-list type that
> > has some indexes present and others missing?  Other than from the new code
> > in your patch that sets some indexes?
> 
> I don't know, can try to add some instrumentation and do bootstrap/regtest
> with it.  The handling of the CONSTRUCTORs with missing or present or mixed
> indexes is what I found in various middle-end routines.
> The only thing I see in our verifiers is that in GIMPLE function bodies,
> we don't allow non-VECTOR_TYPE CONSTRUCTORs with any elements, and for
> VECTOR_TYPE CONSTRUCTORs we require that indexes are NULL for elements with
> VECTOR_TYPE and for others require that it is either NULL or INTEGER_CST
> matching the position (so effectively for those direct access is still
> possible).
> The question might not be just what we do emit right now, but also what we'd
> like to emit in the future, because as has been noted several times, for
> large initializers those explicit indexes consume huge amounts of memory.
> In C with designated initializers, I can see us not emitting indexes from
> the start because we'd want to avoid the memory overhead for normal
> sequential initializers, but then much later we can find a designated
> initializer that wants to skip over some elements and thus add an index at
> that point (or range designator for which we want RANGE_EXPR); shall we add
> indexes to all elements at that point?
> In C++, I think we don't allow non-useless array designated initializers, so
> there is no way to skip elements using that or go backwards, but still,
> don't we emit RANGE_EXPRs if we see the same initializer for many elements?
> I guess right now we emit indexes for all elements for those, but if we
> choose to optimize?

I've played with eliding them (on the C frontend) some time ago and
the issue with designated initializers is not themselves but that
we need to "sort" the CTOR and at that point we need indexes for all
elements (or have some other way of dealing with it).

Also for sparse CTORs the middle-end needs indices for binary search.

I wonder if we could replace INTEGER_CSTs with (index<<1)|1 in
constructor_elt.index or so ... (or sth less hackish)

I bet there's a way around the sorting issue of course.  Like
the suggested late add.

> > Is it unreasonable to assume that if the first element has no index, none of
> > the elements do?
> 
> Not sure, see above.  Depends on what we want to guarantee.

In the middle-end we don't want to rely on this unless we have 
checking that we honor it.  For pure frontend code feel free to
set your own constraints ;)

> > > +	    else if (i == j + (middle - begin))
> > > +	      {
> > > +		(*elts)[middle].index = dindex;
> > 
> > Why set this index?
> 
> Because the caller asserts or relies that it has one.
>       constructor_elt *cep = NULL;
>       if (code == ARRAY_TYPE)
>         {
>           HOST_WIDE_INT i
>             = find_array_ctor_elt (*valp, index, /*insert*/true);
>           gcc_assert (i >= 0);
>           cep = CONSTRUCTOR_ELT (*valp, i);
>           gcc_assert (TREE_CODE (cep->index) != RANGE_EXPR);
> 
> Now, ATM we are aware of just small CONSTRUCTORs that can appear this way
> (VECTOR_TYPE and so generally not too many elements in real-world
> testcases), so if you prefer, the function when seeing NULL index could just
> add indexes to all elements and retry and defer deciding if and how we
> optimize large constructors for later.
>
> 	Jakub
> 
>

On Thu, Feb 6, 2020 at 7:02 AM Jakub Jelinek <jakub@redhat.com> wrote:

> On Wed, Feb 05, 2020 at 01:31:30PM -0500, Jason Merrill wrote:
> > > from the constexpr new change apparently broke the following testcase.
> > > When handling COND_EXPR, we build_vector_from_val, however as the
> argument we
> > > pass to it is not an INTEGER_CST/REAL_CST, but that wrapped in a
> > > NON_LVALUE_EXPR location wrapper, we end up with a CONSTRUCTOR and as
> it is
> > > middle-end that builds it, it doesn't bother with indexes.  The
> > > cp_fully_fold_init call used to fold it into VECTOR_CST in the past,
> but as
> > > we intentionally don't invoke it anymore as it might fold away
> something
> > > that needs to be diagnosed during constexpr evaluation, we end up
> evaluating
> > > ARRAY_REF into the index-less CONSTRUCTOR.  The following patch fixes
> the
> > > ICE by teaching find_array_ctor_elt to handle CONSTRUCTORs without
> indexes
> > > (that itself could be still very efficient) and CONSTRUCTORs with some
> > > indexes present and others missing (the rules are that if the index on
> the
> > > first element is missing, then it is the array's lowest index (in
> C/C++ 0)
> > > and if other indexes are missing, they are the index of the previous
> element
> > > + 1).
> >
> > Is it currently possible to get a CONSTRUCTOR with non-init-list type
> that
> > has some indexes present and others missing?  Other than from the new
> code
> > in your patch that sets some indexes?
>
> I don't know, can try to add some instrumentation and do bootstrap/regtest
> with it.  The handling of the CONSTRUCTORs with missing or present or mixed
> indexes is what I found in various middle-end routines.
> The only thing I see in our verifiers is that in GIMPLE function bodies,
> we don't allow non-VECTOR_TYPE CONSTRUCTORs with any elements, and for
> VECTOR_TYPE CONSTRUCTORs we require that indexes are NULL for elements with
> VECTOR_TYPE and for others require that it is either NULL or INTEGER_CST
> matching the position (so effectively for those direct access is still
> possible).
>

Where are these verifiers?  I'm not finding them.


> The question might not be just what we do emit right now, but also what
> we'd
> like to emit in the future, because as has been noted several times, for
> large initializers those explicit indexes consume huge amounts of memory.
> In C with designated initializers, I can see us not emitting indexes from
> the start because we'd want to avoid the memory overhead for normal
> sequential initializers, but then much later we can find a designated
> initializer that wants to skip over some elements and thus add an index at
> that point (or range designator for which we want RANGE_EXPR); shall we add
> indexes to all elements at that point?
>

That sounds right to me.  Until we have the linear range start marker you
suggested above.


> In C++, I think we don't allow non-useless array designated initializers,
> so
> there is no way to skip elements using that or go backwards, but still,
> don't we emit RANGE_EXPRs if we see the same initializer for many elements?
>

Yes, though only for omitted initializers where {}-initialization is
different from zero-initialization; we don't currently combine explicit
initializers.


> I guess right now we emit indexes for all elements for those, but if we
> choose to optimize?
>
> > Is it unreasonable to assume that if the first element has no index,
> none of
> > the elements do?
>
> Not sure, see above.  Depends on what we want to guarantee.
>

If we go back and fill in indexes when we see something more complicated,
we could enforce this in the verifiers.


> > > +       else if (i == j + (middle - begin))
> > > +         {
> > > +           (*elts)[middle].index = dindex;
> >
> > Why set this index?
>
> Because the caller asserts or relies that it has one.
>       constructor_elt *cep = NULL;
>       if (code == ARRAY_TYPE)
>         {
>           HOST_WIDE_INT i
>             = find_array_ctor_elt (*valp, index, /*insert*/true);
>           gcc_assert (i >= 0);
>           cep = CONSTRUCTOR_ELT (*valp, i);
>           gcc_assert (TREE_CODE (cep->index) != RANGE_EXPR);
>

Let's change this assert to allow null index.


>
> Now, ATM we are aware of just small CONSTRUCTORs that can appear this way
> (VECTOR_TYPE and so generally not too many elements in real-world
> testcases), so if you prefer, the function when seeing NULL index could
> just
> add indexes to all elements and retry and defer deciding if and how we
> optimize large constructors for later.
>
>         Jakub
>
>

On Thu, Feb 06, 2020 at 10:38:25AM -0500, Jason Merrill wrote:
> > I don't know, can try to add some instrumentation and do bootstrap/regtest
> > with it.  The handling of the CONSTRUCTORs with missing or present or mixed
> > indexes is what I found in various middle-end routines.
> > The only thing I see in our verifiers is that in GIMPLE function bodies,
> > we don't allow non-VECTOR_TYPE CONSTRUCTORs with any elements, and for
> > VECTOR_TYPE CONSTRUCTORs we require that indexes are NULL for elements with
> > VECTOR_TYPE and for others require that it is either NULL or INTEGER_CST
> > matching the position (so effectively for those direct access is still
> > possible).
> >
> 
> Where are these verifiers?  I'm not finding them.

tree-cfg.c (verify_gimple_assign_single).
Though, we don't really have verifiers for initializers of global variables,
guess it would need to be called somewhere from varpool_node::assemble_decl
or so (or other varpool method or multiple of them).

	Jakub