[3/6] Share code from fold_array_ctor_reference with fold.

This is in response to https://gcc.gnu.org/ml/gcc/2015-10/msg00097.html, where
Richi points out that CONSTRUCTOR elements are not necessarily ordered.

I wasn't sure of a good naming convention for the new get_ctor_element_at_index,
other suggestions welcome.

gcc/ChangeLog:

	* gimple-fold.c (fold_array_ctor_reference): Move searching code to:
	* fold-const.c (get_ctor_element_at_index): New.
	(fold): Remove binary-search through CONSTRUCTOR, call previous.

	* fold-const.h (get_ctor_element_at_index): New.
---
 gcc/fold-const.c  | 93 ++++++++++++++++++++++++++++++++++++++++---------------
 gcc/fold-const.h  |  1 +
 gcc/gimple-fold.c | 47 ++--------------------------
 3 files changed, 72 insertions(+), 69 deletions(-)

On Thu, Oct 29, 2015 at 8:18 PM, Alan Lawrence <alan.lawrence@arm.com> wrote:
> This is in response to https://gcc.gnu.org/ml/gcc/2015-10/msg00097.html, where
> Richi points out that CONSTRUCTOR elements are not necessarily ordered.
>
> I wasn't sure of a good naming convention for the new get_ctor_element_at_index,
> other suggestions welcome.

get_array_ctor_element_at_index

(ok it also handles vectors).

Ok with that change.

Richard.

> gcc/ChangeLog:
>
>         * gimple-fold.c (fold_array_ctor_reference): Move searching code to:
>         * fold-const.c (get_ctor_element_at_index): New.
>         (fold): Remove binary-search through CONSTRUCTOR, call previous.
>
>         * fold-const.h (get_ctor_element_at_index): New.
> ---
>  gcc/fold-const.c  | 93 ++++++++++++++++++++++++++++++++++++++++---------------
>  gcc/fold-const.h  |  1 +
>  gcc/gimple-fold.c | 47 ++--------------------------
>  3 files changed, 72 insertions(+), 69 deletions(-)
>
> diff --git a/gcc/fold-const.c b/gcc/fold-const.c
> index de45a2c..5d27b91 100644
> --- a/gcc/fold-const.c
> +++ b/gcc/fold-const.c
> @@ -12018,6 +12018,72 @@ fold_ternary_loc (location_t loc, enum tree_code code, tree type,
>      } /* switch (code) */
>  }
>
> +/* Gets the element ACCESS_INDEX from CTOR, which must be a CONSTRUCTOR.  */
> +
> +tree
> +get_ctor_element_at_index (tree ctor, offset_int access_index)
> +{
> +  tree index_type = NULL_TREE;
> +  offset_int low_bound = 0;
> +
> +  if (TREE_CODE (TREE_TYPE (ctor)) == ARRAY_TYPE)
> +  {
> +    tree domain_type = TYPE_DOMAIN (TREE_TYPE (ctor));
> +    if (domain_type && TYPE_MIN_VALUE (domain_type))
> +    {
> +      /* Static constructors for variably sized objects makes no sense.  */
> +      gcc_assert (TREE_CODE (TYPE_MIN_VALUE (domain_type)) == INTEGER_CST);
> +      index_type = TREE_TYPE (TYPE_MIN_VALUE (domain_type));
> +      low_bound = wi::to_offset (TYPE_MIN_VALUE (domain_type));
> +    }
> +  }
> +
> +  if (index_type)
> +    access_index = wi::ext (access_index, TYPE_PRECISION (index_type),
> +                           TYPE_SIGN (index_type));
> +
> +  offset_int index = low_bound - 1;
> +  if (index_type)
> +    index = wi::ext (index, TYPE_PRECISION (index_type),
> +                    TYPE_SIGN (index_type));
> +
> +  offset_int max_index;
> +  unsigned HOST_WIDE_INT cnt;
> +  tree cfield, cval;
> +
> +  FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
> +  {
> +    /* Array constructor might explicitely set index, or specify range
> +     * or leave index NULL meaning that it is next index after previous
> +     * one.  */
> +    if (cfield)
> +    {
> +      if (TREE_CODE (cfield) == INTEGER_CST)
> +       max_index = index = wi::to_offset (cfield);
> +      else
> +      {
> +       gcc_assert (TREE_CODE (cfield) == RANGE_EXPR);
> +       index = wi::to_offset (TREE_OPERAND (cfield, 0));
> +       max_index = wi::to_offset (TREE_OPERAND (cfield, 1));
> +      }
> +    }
> +    else
> +    {
> +      index += 1;
> +      if (index_type)
> +       index = wi::ext (index, TYPE_PRECISION (index_type),
> +                        TYPE_SIGN (index_type));
> +       max_index = index;
> +    }
> +
> +    /* Do we have match?  */
> +    if (wi::cmpu (access_index, index) >= 0
> +       && wi::cmpu (access_index, max_index) <= 0)
> +      return cval;
> +  }
> +  return NULL_TREE;
> +}
> +
>  /* Perform constant folding and related simplification of EXPR.
>     The related simplifications include x*1 => x, x*0 => 0, etc.,
>     and application of the associative law.
> @@ -12094,31 +12160,8 @@ fold (tree expr)
>             && TREE_CODE (op0) == CONSTRUCTOR
>             && ! type_contains_placeholder_p (TREE_TYPE (op0)))
>           {
> -           vec<constructor_elt, va_gc> *elts = CONSTRUCTOR_ELTS (op0);
> -           unsigned HOST_WIDE_INT end = vec_safe_length (elts);
> -           unsigned HOST_WIDE_INT begin = 0;
> -
> -           /* Find a matching index by means of a binary search.  */
> -           while (begin != end)
> -             {
> -               unsigned HOST_WIDE_INT middle = (begin + end) / 2;
> -               tree index = (*elts)[middle].index;
> -
> -               if (TREE_CODE (index) == INTEGER_CST
> -                   && tree_int_cst_lt (index, op1))
> -                 begin = middle + 1;
> -               else if (TREE_CODE (index) == INTEGER_CST
> -                        && tree_int_cst_lt (op1, index))
> -                 end = middle;
> -               else if (TREE_CODE (index) == RANGE_EXPR
> -                        && tree_int_cst_lt (TREE_OPERAND (index, 1), op1))
> -                 begin = middle + 1;
> -               else if (TREE_CODE (index) == RANGE_EXPR
> -                        && tree_int_cst_lt (op1, TREE_OPERAND (index, 0)))
> -                 end = middle;
> -               else
> -                 return (*elts)[middle].value;
> -             }
> +           if (tree val = get_ctor_element_at_index (op0, wi::to_offset (op1)))
> +             return val;
>           }
>
>         return t;
> diff --git a/gcc/fold-const.h b/gcc/fold-const.h
> index ee74dc8..1fa6ee0 100644
> --- a/gcc/fold-const.h
> +++ b/gcc/fold-const.h
> @@ -73,6 +73,7 @@ extern tree fold_build_call_array_loc (location_t, tree, tree, int, tree *);
>  #define fold_build_call_array_initializer(T1,T2,N,T4)\
>     fold_build_call_array_initializer_loc (UNKNOWN_LOCATION, T1, T2, N, T4)
>  extern tree fold_build_call_array_initializer_loc (location_t, tree, tree, int, tree *);
> +extern tree get_ctor_element_at_index (tree, offset_int);
>  extern bool fold_convertible_p (const_tree, const_tree);
>  #define fold_convert(T1,T2)\
>     fold_convert_loc (UNKNOWN_LOCATION, T1, T2)
> diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c
> index 85ff018..823d952 100644
> --- a/gcc/gimple-fold.c
> +++ b/gcc/gimple-fold.c
> @@ -5308,13 +5308,10 @@ fold_array_ctor_reference (tree type, tree ctor,
>                            unsigned HOST_WIDE_INT size,
>                            tree from_decl)
>  {
> -  unsigned HOST_WIDE_INT cnt;
> -  tree cfield, cval;
>    offset_int low_bound;
>    offset_int elt_size;
> -  offset_int index, max_index;
>    offset_int access_index;
> -  tree domain_type = NULL_TREE, index_type = NULL_TREE;
> +  tree domain_type = NULL_TREE;
>    HOST_WIDE_INT inner_offset;
>
>    /* Compute low bound and elt size.  */
> @@ -5324,7 +5321,6 @@ fold_array_ctor_reference (tree type, tree ctor,
>      {
>        /* Static constructors for variably sized objects makes no sense.  */
>        gcc_assert (TREE_CODE (TYPE_MIN_VALUE (domain_type)) == INTEGER_CST);
> -      index_type = TREE_TYPE (TYPE_MIN_VALUE (domain_type));
>        low_bound = wi::to_offset (TYPE_MIN_VALUE (domain_type));
>      }
>    else
> @@ -5346,9 +5342,6 @@ fold_array_ctor_reference (tree type, tree ctor,
>    access_index = wi::udiv_trunc (offset_int (offset / BITS_PER_UNIT),
>                                  elt_size);
>    access_index += low_bound;
> -  if (index_type)
> -    access_index = wi::ext (access_index, TYPE_PRECISION (index_type),
> -                           TYPE_SIGN (index_type));
>
>    /* And offset within the access.  */
>    inner_offset = offset % (elt_size.to_uhwi () * BITS_PER_UNIT);
> @@ -5357,43 +5350,9 @@ fold_array_ctor_reference (tree type, tree ctor,
>       care to fold accesses spanning multiple array indexes.  */
>    if (inner_offset + size > elt_size.to_uhwi () * BITS_PER_UNIT)
>      return NULL_TREE;
> +  if (tree val = get_ctor_element_at_index (ctor, access_index))
> +    return fold_ctor_reference (type, val, inner_offset, size, from_decl);
>
> -  index = low_bound - 1;
> -  if (index_type)
> -    index = wi::ext (index, TYPE_PRECISION (index_type),
> -                    TYPE_SIGN (index_type));
> -
> -  FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
> -    {
> -      /* Array constructor might explicitely set index, or specify range
> -        or leave index NULL meaning that it is next index after previous
> -        one.  */
> -      if (cfield)
> -       {
> -         if (TREE_CODE (cfield) == INTEGER_CST)
> -           max_index = index = wi::to_offset (cfield);
> -         else
> -           {
> -             gcc_assert (TREE_CODE (cfield) == RANGE_EXPR);
> -             index = wi::to_offset (TREE_OPERAND (cfield, 0));
> -             max_index = wi::to_offset (TREE_OPERAND (cfield, 1));
> -           }
> -       }
> -      else
> -       {
> -         index += 1;
> -         if (index_type)
> -           index = wi::ext (index, TYPE_PRECISION (index_type),
> -                            TYPE_SIGN (index_type));
> -         max_index = index;
> -       }
> -
> -      /* Do we have match?  */
> -      if (wi::cmpu (access_index, index) >= 0
> -         && wi::cmpu (access_index, max_index) <= 0)
> -       return fold_ctor_reference (type, cval, inner_offset, size,
> -                                   from_decl);
> -    }
>    /* When memory is not explicitely mentioned in constructor,
>       it is 0 (or out of range).  */
>    return build_zero_cst (type);
> --
> 1.9.1
>

On 10/29/2015 01:18 PM, Alan Lawrence wrote:
> This is in response to https://gcc.gnu.org/ml/gcc/2015-10/msg00097.html, where
> Richi points out that CONSTRUCTOR elements are not necessarily ordered.
>
> I wasn't sure of a good naming convention for the new get_ctor_element_at_index,
> other suggestions welcome.
>
> gcc/ChangeLog:
>
> 	* gimple-fold.c (fold_array_ctor_reference): Move searching code to:
> 	* fold-const.c (get_ctor_element_at_index): New.
> 	(fold): Remove binary-search through CONSTRUCTOR, call previous.
>
> 	* fold-const.h (get_ctor_element_at_index): New.
Code is fine.  Some formatting nits though.


> ---
>   gcc/fold-const.c  | 93 ++++++++++++++++++++++++++++++++++++++++---------------
>   gcc/fold-const.h  |  1 +
>   gcc/gimple-fold.c | 47 ++--------------------------
>   3 files changed, 72 insertions(+), 69 deletions(-)
>
> diff --git a/gcc/fold-const.c b/gcc/fold-const.c
> index de45a2c..5d27b91 100644
> --- a/gcc/fold-const.c
> +++ b/gcc/fold-const.c
> +
> +  FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
> +  {
> +    /* Array constructor might explicitely set index, or specify range
> +     * or leave index NULL meaning that it is next index after previous
> +     * one.  */
s/explicitely/explicitly/  And remove the '*' from the 2nd and 3rd lines 
of the comment.

It looks like get_ctor_element_at_index has numerous formatting 
problems.  In particular you didn't indent the braces across the board 
properly.  Also check for tabs vs spaces issues please.

Can you please fix the formatting and comments and repost for a final check?

Thanks,
Jeff