Re: Tree CONSTRUCTORs and Ada array indices

[Richard Biener <richard dot guenther at gmail dot com>]

On Wed, Oct 14, 2015 at 5:57 PM, Eric Botcazou <ebotcazou@adacore.com> wrote:
>> I'm having fun with arrays in Ada ;) and wondering if anyone can tell me
>> what's right here.
>
> No surprise, arrays are probably the base types for which there is the largest
> gap between Ada and the C family of languages, for which GCC was written.
> You can see in the E_Array_Subtype case of gnat_to_gnu_entity the hoops we
> have to jump through to make them work.
>
>> In GCC this gets represented as an ARRAY_TYPE, whose TYPE_DOMAIN is a 32-bit
>> signed integer type; the TYPE_MAX_VALUE of this is 1 (as a size_int), the
>> TYPE_MIN_VALUE of this is -1 as a size_int, i.e. 4294967295. I believe
>> using (unsigned 32-bit) size_int for min/max is correct (?) despite the
>> domain being a signed type.
>
> Historically it was required that TYPE_DOMAIN be a subtype of 'sizetype', see
> build_index_type.  The Ada compiler was originally using a signed 'sizetype'
> because of this (all the other compilers were using an unsigned one) but a
> couple of changes (POINTER_PLUS_EXPR and LTO) essentially forced a uniform
> 'sizetype' across languages and the Ada compiler wasn't the winner. ;-)
>
>> An array of this type is then initialized with a CONSTRUCTOR. The
>> CONSTRUCTOR has three elements, with INTEGER_CST indices, being in order
>> 2^32-1, 0, 1 (all of sizetype).
>>
>> I substitute the CONSTRUCTOR into an ARRAY_REF <blah>[4294967295]{lb:
>> 4294967295 sz: 2}, i.e. that picks the element with index (sizetype)2^32-1.
>>
>> fold() in fold-const.c then fails to fold, because it does binary search for
>> 2^32-1 through the constructor elements, and first checks against the
>> middle CONSTRUCTOR_ELT, which has index 0.
>
> IIRC I wrote this code (before the signedness change).
>
>> So, where's the bug here? Should all these indices have sizetype? Should
>> fold-const.c's binary search respect the TYPE_DOMAIN of the type of the
>> CONSTRUCTOR being searched? (Lots of build_int_cst to reinterpret the
>> CONSTRUCTOR_ELT indices, and/or the index being searched for, in said
>> TYPE_DOMAIN ?)
>
> According to Richard, we should now be able to set TYPE_DOMAIN to something
> else than a subtype of 'sizetype' but this is a mid-term goal and may require
> some substantial work.  The short-term solution is probably to do nothing,
> arrays with negative indices are not very common in real life even in Ada.

C/C++ empty arrays (int a[0]) now use a signed TYPE_DOMAIN with bounds [0, -1]
for example (that was my original motivation to make hopefully all of
the middle-end
work with ssizetype TYPE_DOMAINs at least).  The tree.c range-type build helpers
accept all integral types now (but most FEs use sizetype or ssizetype).

ISTR also doing some Ada adjustments but they may have been dumped for
"interesting" changes to stor-layout.c instead:

                /* ???  When it is obvious that the range is signed
                   represent it using ssizetype.  */
                if (TREE_CODE (lb) == INTEGER_CST
                    && TREE_CODE (ub) == INTEGER_CST
                    && TYPE_UNSIGNED (TREE_TYPE (lb))
                    && tree_int_cst_lt (ub, lb))
                  {
                    lb = wide_int_to_tree (ssizetype,
                                           offset_int::from (lb, SIGNED));
                    ub = wide_int_to_tree (ssizetype,
                                           offset_int::from (ub, SIGNED));
                  }
                length
                  = fold_convert (sizetype,
                                  size_binop (PLUS_EXPR,
                                              build_int_cst (TREE_TYPE (lb), 1),
                                              size_binop (MINUS_EXPR, ub, lb)));
              }

            /* ??? We have no way to distinguish a null-sized array from an
               array spanning the whole sizetype range, so we arbitrarily
               decide that [0, -1] is the only valid representation.  */
            if (integer_zerop (length)
                && TREE_OVERFLOW (length)
                && integer_zerop (lb))
              length = size_zero_node;

this probably tries to deal with the situation you are running into.

Richard.

> --
> Eric Botcazou