[00/10,RFC] Splitting the C and C++ concept of "complete type"

Message ID 87d0sbjn97.fsf@arm.com
Headers show
Series
  • Splitting the C and C++ concept of "complete type"
Related show

Message

Richard Sandiford Oct. 15, 2018, 2:30 p.m.
The C standard says:

    At various points within a translation unit an object type may be
    "incomplete" (lacking sufficient information to determine the size of
    objects of that type) or "complete" (having sufficient information).

For AArch64 SVE, we'd like to split this into two concepts:

  * has the type been fully defined?
  * would fully-defining the type determine its size?

This is because we'd like to be able to represent SVE vectors as C and C++
types.  Since SVE is a "vector-length agnostic" architecture, the size
of the vectors is determined by the runtime environment rather than the
programmer or compiler.  In that sense, defining an SVE vector type does
not determine its size.  It's nevertheless possible to use SVE vector types
in meaningful ways, such as having automatic vector variables and passing
vectors between functions.

The main questions in the RFC are:

  1) is splitting the definition like this OK in principle?
  2) are the specific rules described below OK?
  3) coding-wise, how should the split be represented in GCC?

Terminology
-----------

Going back to the second bullet above:

  * would fully-defining the type determine its size?

the rest of the RFC calls a type "sized" if fully defining it would
determine its size.  The type is "sizeless" otherwise.

Contents
--------

The RFC is organised as follows.  I've erred on the side of including
detail rather than leaving it out, but each section is meant to be
self-contained and skippable:

  - An earlier RFC
  - Quick overview of SVE
  - Why we need SVE types in C and C++
  - How we ended up with this definition
  - The SVE types in more detail
  - Outline of the type system changes
  - Sizeless structures (and testing on non-SVE targets)
  - Other variable-length vector architectures
  - Edits to the C standard
    - Base changes
    - Updates for consistency
    - Sizeless structures
  - Edits to the C++ standard
  - GCC implementation questions

I'll follow up with patches that implement the split.



An earlier RFC
==============

For the record (in case this sounds familiar) I sent an RFC about the
sizeless type extension a while ago:

    https://gcc.gnu.org/ml/gcc/2017-08/msg00012.html

The rules haven't changed since then, but this version includes more
information and includes support for sizeless structures.


Quick overview of SVE
=====================

SVE is a vector extension to AArch64.  A detailed description is
available here:

    https://static.docs.arm.com/ddi0584/a/DDI0584A_a_SVE_supp_armv8A.pdf

but the only feature that really matters for this RFC is that SVE has no
fixed or preferred vector length.  Implementations can instead choose
from a range of possible vector lengths, with 128 bits being the minimum
and 2048 bits being the maximum.  Priveleged software can further
constrain the vector length within the range offered by the implementation;
e.g. linux currently provides per-thread control of the vector length.


Why we need SVE types in C and C++
==================================

SVE was designed to be an easy target for autovectorising normal scalar
code.  There are also various language extensions that support explicit
data parallelism or that make explicit vector chunking easier to do in
an architecture-neutral way (e.g. C++ P0214).  This means that many users
won't need to do anything SVE-specific.

Even so, there's always going to be a place for writing SVE-specific
optimisations, with full access to the underlying ISA.  As for other
vector architectures, we'd like users to be able to write such routines
in C and C++ rather than force them to go all the way to assembly.

We'd also like C and C++ functions to be able to take SVE vector
parameters and return SVE vector results, which is particularly useful
when implementing things like vector math routines.  In this case in
particular, the types need to map directly to something that fits in
an SVE register, so that passing and returning vectors has minimal
overhead.


How we ended up with this definition
====================================

Requirements
------------

We need the SVE vector types to define and use SVE intrinsic functions
and to write SVE vector library routines.  The key requirements when
defining the types were:

  * They must be available in both C and C++ (because we want to be able
    add SVE optimisations to C-only codebases).

  * They must fit in an SVE vector register (so there can be no on-the-side
    information).

  * It must be possible to define automatic variables with these types.

  * It must be possible to pass and return objects of these types
    (since that's what intrinsics and vector library routines need to do).

  * It must be possible to use the types in _Generic associations
    (so that _Generic can be used to provide tgmath.h-style overloads).

  * It must be possible to use pointers or references to the types
    (for passing or returning by pointer or reference, and because not
    allowing references would be semantically difficult in C++).

Ideally, there'd also be a way of grouping SVE vectors together into tuples,
since the ISA has instructions like LD2 that return multiple vectors.
It would be good if users could also define their own tuple types, on top
of the ones needed by the intrinsics, although that's more "nice to have".

Possible approaches
-------------------

The main complication is that the size of an SVE vector is not a
compile-time constant.  It seems that any approach to handling this
would fall into one of three categories:

  (1) Limit the types in such a way that there is no concept of size.

  (2) Define the size of the types to be variable.

  (3) Define the size of the types to be constant, either with the
      constant being large enough for all possible vector lengths or
      with the types pointing to separate memory (as for C++ classes
      like std::string).

Why (2) seemed like a bad idea
------------------------------

(2) seemed initially appealing since C already has the concept of
variable-length arrays.  However, variable-length built-in types
would work in a significantly different way.  Arrays often decay to
pointers (which of course are fixed-length types), whereas vector
types never would.  Unlike arrays, it should be possible to pass
variable-length vectors to functions, return them from functions,
and assign them by value.

One particular difficulty is that the semantics of variable-length arrays
rely on having a point at which the array size is evaluated.  It would
be difficult to extend this approach to declarations of functions that
pass or return variable-length types.

As well as the extension itself being relatively complex (especially
for C++), it might be difficult to define it in a way that interacts
naturally with other (unseen) extensions, even those that are aware of
variable-length arrays.  Also, AIUI, variable-length arrays were added
to an early draft of C++14, but were later removed as too controversial
and didn't make it into the final standard.  C++17 still requires sizeof
to be constant and C11 makes variable-length arrays optional.

(2) therefore felt like a complicated dead-end.

Why (3) seemed like a bad idea
------------------------------

(3) can be divided into two:

(3a) The vector types have a constant size and are large enough for all
     possible vector lengths.

    The main problem with this is that the maximum size of an SVE
    vector (2048 bits) is much larger than the minimum size (128 bits).
    Using a fixed size of 2048 bits would be extremely inefficient for
    smaller vector lengths, and of course the whole point of using
    vectors is to make things *more* efficient.

    Also, we would need to define the types such that only the bytes
    associated with the actual vector length are significant.  This would
    make it possible to pass or return the types in registers and treat
    them as register values when copying.  This perhaps has some similarity
    with overaligned structures such as:

	struct s { _Alignas(16) int i; };

    except that the amount of padding would only be known at runtime.

    There's also a significant conceptual problem: encoding a fixed size
    goes against a guiding principle of SVE, in which there is no preferred
    vector length.  There's nothing particularly magical about the current
    limit of 2048 bits and it would be better to avoid an ABI break if the
    maximum ever did increase in future.

(3b) The vector types have a constant size and refer to separate storage
     (as for std::string etc.)

    This would be difficult to do without C++-style constructor, destructor,
    copy and move semantics, so wouldn't work well in C.  And in C++ it would
    be less efficient than the proposed approach, since presumably an Allocator
    would be needed to allocate the separate storage.  It would also require
    a complicated ABI mapping to ensure that the vectors can still be passed
    and returned in registers.

Chosen approach
---------------

We therefore took approach (1) and classified C and C++ types as "sized"
(having a measurable size when fully-defined) and "sizeless" (never
having a measurable size).  Sizeless types have no defined size,
alignment or layout at the language level, with those things becoming
purely an ABI-level detail.

We then treated all sizeless types as permanently incomplete.
On its own, this would put them in a similar situation to "void"
(although they wouldn't be exactly the same, since there are some
specific rules for "void" that don't apply to incomplete types in
general).  We then relaxed specific rules until the types were actually
useful.

Things in favour of (1)
-----------------------

The reasons above were mostly negative, arriving at (1) by elimination.
A more positive justification of this approach is that it seems
to meet the requirements in the most efficient way possible.  The
vectors can use their natural (native) representation, and the type
system prevents uses that would make that representation problematic.

Also, the approach of starting with very restricted types and then
specifically allowing certain things should be more future-proof
and interact better with other language extensions.  By default,
any language extension would treat the new types like other incomplete
types and choose conservatively-correct behaviour.  It would then be
possible to relax the language extension if this default behaviour
turns out to be too restrictive.

(That said, treating the types as permanently incomplete still won't
avoid all clashes with other extensions.  For example, we need to
allow objects of automatic storage duration to have certain forms of
incomplete type, whereas an extension might implicitly assume that all
such objects must already have complete type.  The approach should still
avoid the worst effects though.)


The SVE types in more detail
============================

Arm has published an SVE "ACLE" that specifies the SVE types and intrinsic
functions in detail.  For reference this is available without registration
at:

    https://static.docs.arm.com/100987/0000/acle_sve_100987_0000_00_en.pdf

but I'll try to keep this self-contained.

The ACLE defines a vector type sv<base>_t for each supported element type
<base>_t, so that the complete set is:

    svint8_t      svint16_t     svint32_t     svint64_t
    svuint8_t     svuint16_t    svuint32_t    svuint64_t
                  svfloat16_t   svfloat32_t   svfloat64_t

The types in each column have the same number of lanes and have twice
as many lanes as those in the column to the right.  Every vector has
the same number of bytes in total, with the number of bytes being
determined at runtime.

The ACLE also defines a single predicate type:

    svbool_t

that has the same number of lanes as svint8_t and svuint8_t.

All these types are opaque builtin types and are only expected to
be used with the associated ACLE intrinsics.  There are intrinsics for
creating vectors from scalars, loading from scalars, storing to scalars,
reinterpreting one type as another, etc.

The idea is that the vector types would only be used for short-term
register-sized working data.  Longer-term data would typically be stored
out to arrays.

For example, the vector function underlying:

    #pragma omp declare simd
    double sin(double);

would be:

    svfloat64_t mangled_sin(svfloat64_t, svbool_t);

(The svbool_t is because SVE functions should be predicated by default,
to avoid the need for a scalar epilogue loop.)

The ACLE also defines x2, x3 and x4 tuple types for each vector type;
for example, svint8x3_t is a tuple of 3 svint8_ts.  The tuples are
structure-like types with fields v0, v1, v2 and v3, up to the number
required.


Outline of the type system changes
==================================

Going back to the summary at the start of the RFC, C classifies types as
"complete" (the size of objects can be calculated) or "incomplete" (the
size of objects can't be calculated).  There's very little you can do
with a type until it becomes complete.

The approach we took was to treat all the SVE types as permanently
incomplete.  We then went through the standard relaxing specific
rules until the types were actually useful.

The first step was to classify types as:

  * "indefinite" (lacking sufficient information to create an object of
    that type) or "definite" (having sufficient information)

  * "sized" (will have a known size when definite) or "sizeless" (will
    never have a known size)

  * "incomplete" (lacking sufficient information to determine the size of
    objects of that type) or "complete" (having sufficient information)

where the wording for the final bullet is unchanged from the standard.
Thus a "definite type" is one that has been fully-defined rather than
simply declared, and "complete" is now equivalent to "sized and definite".
All standard types are "sized" (even "void", although it's always
indefinite and incomplete).

We then needed to make some rules use the distinction between "indefinite"
and "definite" rather than "incomplete" and "complete".  The specific
things we wanted to allow were:

  * defining automatic variables with sizeless definite type
  * defining functions whose parameters have sizeless definite type
  * defining functions that return a sizeless definite type
  * using sizeless definite types in _Generic associations
  * dereferencing pointers to sizeless definite types

Specific things we wanted to remain invalid -- by inheriting the rules from
incomplete types -- were:

  * creating or accessing arrays that have sizeless element types
  * doing pointer arithmetic on pointers to sizeless types
  * using sizeof and _Alignof with a sizeless type (or object of sizeless type)
  * defining (sized) unions or structures with sizeless members

It also seemed worth adding an extra restriction:

  * variables with sizeless type must not have static or thread-local
    storage duration

In practice it's impossible to define such variables with incomplete type,
but having an explicit rule means that things like:

    extern svint8_t foo;  // An SVE vector of int8_t elements.

are outright invalid rather than simply useless (because no other
translation unit could ever define foo).  Similarly, without an
explicit rule:

    svint8_t foo;         // An SVE vector of int8_t elements.

would be a valid tentative definition at the point it occurs and only
become invalid at the end of the translation unit, because svint8_t is
never completed.

This restriction isn't critical but it gives better diagnostics.


Sizeless structures (and testing on non-SVE targets)
====================================================

We're planning to build all SVE intrinsic types directly into GCC
(patches already written).  SVE therefore doesn't strictly need a syntax
for creating new sizeless types in C and C++.  However, having a way of
creating new structure-like "sizeless" types would be useful for three
reasons:

  - Functions could return arbitrary data by value.  The SVE ABI allows
    a function to return up to 8 vectors and 4 predicates in registers,
    which is far more flexible than the intrinsic types.

  - We could use these sizeless structure types to test the functionality
    on all targets.

  - A lot of the C++ frontend is concerned with classes, and having
    a way of creating sizeless classes would help make the C++ changes
    more consistent.

The patches therefore add a new "__sizeless_struct" keyword to denote
structures that are sizeless rather than sized.  Unlike normal
structures, these structures can have members of sizeless type in
addition to members of sized type.  On the other hand, they have all
the same limitations as other sizeless types (described in earlier
sections).

E.g., a sizeless structure definition might look like:

    __sizeless_struct data {
      double *array;
      svuint64_t indices;  // An SVE vector of uint64_t elements.
      svbool_t active;     // An SVE predicate.
    };

Adding a new keyword seemed better than using an attribute because it
means that the sized vs. sizeless distinction is fixed by the declaration.
E.g.:

    struct data;                     // Is it sized or sizeless?
    extern struct data global_data;  // OK if sized, not if sizeless.
    struct __attribute__((sizeless)) data {
      double *array;
      svuint64_t indices;            // An SVE vector of uint64_t elements.
      svbool_t active;               // An SVE predicate.
    };

would lead to the declaration of "global_data" sneaking through
despite being invalid when "data" is sizeless.

The tests in the patches all use these __sizeless_structs; they contain
nothing SVE- or AArch64-specific.


Other variable-length vector architectures
==========================================

The proposed RISC-V vector extension also has variable-length vectors.
When this language change was discussed on the clang developers' list,
Bruce Hoult (from SiFive, but speaking personally) replied with:

    http://lists.llvm.org/pipermail/cfe-dev/2018-May/057943.html

That message covers some of the background about the vector extension.
On the language changes, Bruce said:

    > However, even though the length is variable, the concept of a

    > "register-sized" C and C++ vector type makes just as much sense for SVE

    > as it does for other vector architectures.  Vector library functions

    > take such register-sized vectors as input and return them as results.

    > Intrinsic functions are also just as useful as they are for other vector

    > architectures, and they too take register-sized vectors as input and

    > return them as results.


    Intrinsic functions are absolutely required, and are I think the main
    reason for such a low-level register-sized vector type to exist.

[ Bruce went on to say:

    I'm not sure whether user-written functions operating on register-sized
    vectors are useful enough to support. User-written functions would normally
    take and return a higher-level vector type, and would implement the desired
    functionality in terms of calls to other user-written functions (operating
    on the high level vector as a whole) and/or explicit loops iterating
    through the high level vector type using intrinsic functions on the
    register-sized vector type proposed here.

But this use case is very important for SVE, since it will allow us
to implement vector math routines in a way that works with the OpenMP
"declare simd" construct.  There was also talk on gcc@ recently about
supporting this style of interface for RISC-V. ]

[...]

    > All these types are opaque builtin types and are only intended to be

    > used with the associated ACLE intrinsics.  There are intrinsics for

    > creating vectors from scalars, loading from scalars, storing to scalars,

    > reinterpreting one type as another, etc.

    >

    > The idea is that the vector types would only be used for short-term

    > register-sized working data.  Longer-term data would typically be stored

    > out to arrays.


    I agree with this.

[...]

    > The approach we took was to treat all the SVE types as permanently

    > incomplete.


    This seems reasonable.

So it looks like this extension would be useful for at least one
architecture besides SVE.


Edits to the C standard
=======================

This section specifies the behaviour for sizeless types as an edit to N1570.
There are three stages:

  - base changes, which add enough support for built-in sizeless
    vector types

  - updates for consistency, which change some of the wording without
    changing the meaning

  - support for sizeless structures

In each case, -strikethrough- indicates deleted text and *bold*
includes additional text.


Base changes
------------

These changes are enough to support sizeless built-in vector types.

    6.2.5 Types
    -----------

    1. The meaning of a value stored in an object or returned by a
    function is determined by the type of the expression used to access
    it. … Types are partitioned into object types (types that
    describe objects) and function types (types that describe
    functions).  -At various points within a translation unit an object
    type may be incomplete (lacking sufficient information to determine
    the size of objects of that type) or complete (having sufficient
    information).37)- *Object types are further partitioned into sized and
    sizeless; all basic and derived types defined in this standard are
    sized, but an implementation may provide additional sizeless types.*

    1A. *At various points within a translation unit an object type may
    be indefinite (lacking sufficient information to construct an object
    of that type) or definite (having sufficient information).37) An
    object type is said to be complete if it is both sized and definite;
    all other object types are said to be incomplete.  Complete types
    have sufficient information to determine the size of an object of
    that type while incomplete types do not.*

    1B. *Arrays, structures, unions and enumerated types are always
    sized, so for them the term incomplete is equivalent to (and used
    interchangeably with) the term indefinite.*

    …

    19. The void type comprises an empty set of values; it is -an
    incomplete- *a sized indefinite* object type that cannot be completed
    *(made definite)*.

    …

    37) A type may be -incomplete- *indefinite* or -complete- *definite*
    throughout an entire translation unit, or it may change states at
    different points within a translation unit.

    …

    6.3.2.1 Lvalues, arrays, and function designators
    -------------------------------------------------

    1.  An lvalue is an expression (with an object type other than void)
    that potentially designates an object;64) … A modifiable lvalue is
    an lvalue that does not have array type, does not have an
    -incomplete- *indefinite* type, does not have a const-qualified
    type, …

    2.  Except when it is the operand of the sizeof operator, the
    _Alignof operator, the unary & operator, the ++ operator, the --
    operator, or the left operand of the . operator or an assignment
    operator, an lvalue that does not have array type is converted to
    the value stored in the designated object (and is no longer an
    lvalue); this is called lvalue conversion. … If the lvalue has an
    -incomplete- *indefinite* type and does not have array type, the
    behavior is undefined. …

    …

    6.5.1.1 Generic selection
    -------------------------

    …

    Constraints

    2. A generic selection shall have no more than one default generic
    association. The type name in a generic association shall specify a
    -complete- *definite* object type other than a variably modified
    type. …

    …

    6.5.2.2 Function calls
    ----------------------

    Constraints

    1. The expression that denotes the called function92) shall have
    type pointer to function returning void or returning a -complete-
    *definite* object type other than an array type.

    …

    Semantics

    …

    4. An argument may be an expression of any -complete- *definite* object
    type. …

    …

    6.5.2.5 Compound literals
    -------------------------

    Constraints

    1. The type name shall specify a -complete- *definite* object type or an
    array of unknown size, but not a variable length array type.

    …

    6.7 Declarations
    ----------------

    Constraints

    …

    4A. *If an identifier for an object does not have automatic storage
    duration, its type must be sized rather than sizeless.*

    Semantics

    …

    7. If an identifier for an object is declared with no linkage, the
    type for the object shall be -complete- *definite* by the end of its
    declarator, or by the end of its init-declarator if it has an
    initializer; in the case of function parameters (including in
    prototypes), it is the adjusted type (see 6.7.6.3) that is required
    to be -complete- *definite*.

    …
     
    6.7.6.3 Function declarators (including prototypes) 
    ---------------------------------------------------

    Constraints

    …

    4. After adjustment, the parameters in a parameter type list in a
    function declarator that is part of a definition of that function
    shall not have -incomplete- *indefinite* type.

    …

    6.7.9 Initialization
    --------------------

    Constraints

    …

    3. The type of the entity to be initialized shall be an array of
    unknown size or a -complete- *definite* object type that is not a
    variable length array type.

    …

    6.9.1 Function definitions
    --------------------------

    Constraints

    …

    3. The return type of a function shall be void or a -complete-
    *definite* object type other than array type.

    …

    Semantics

    …

    7. The declarator in a function definition specifies the name of the
    function being defined and the identifiers of its parameters. …
    [T]he type of each parameter is adjusted as described in
    6.7.6.3 for a parameter type list; the resulting type shall be a
    -complete- *definite* object type.

    …

    J.2 Undefined behavior
    ----------------------

        …
      * A non-array lvalue with -an incomplete- *an indefinite* type is used
        in a context that requires the value of the designated object
        (6.3.2.1).
        …
      * An identifier for an object is declared with no linkage and the
        type of the object is -incomplete- *indefinite* after its
        declarator, or after its init-declarator if it has an
        initializer (6.7).
        …
      * An adjusted parameter type in a function definition is not a
        -complete- *definite* object type (6.9.1).
        …

Updates for consistency
-----------------------

These changes are a prerequisite for sizeless structures.  They have no
effect otherwise, but might be preferred anyway because they make the
terminology more consistent.  They apply on top of the previous edits.

    6.2.5 Types
    -----------

    …

    22. An array type of unknown size is an -incomplete- *indefinite*
    type. It is -completed- *made definite*, for an identifier of that type,
    by specifying the size in a later declaration (with internal or
    external linkage). A structure or union type of unknown content (as
    described in 6.7.2.3) is an -incomplete- *indefinite* type. It is
    -completed- *made definite*, for all declarations of that type, by
    declaring the same structure or union tag with its defining content
    later in the same scope.

    …

    6.2.7 Compatible type and composite type
    ----------------------------------------

    1. Two types have compatible type if their types are the same. …
    Moreover, two structure, union, or enumerated types declared in
    separate translation units are compatible if their tags and members
    satisfy the following requirements: If one is declared with a tag,
    the other shall be declared with the same tag. If both are
    -completed- *made definite* anywhere within their respective
    translation units, then the following additional requirements apply: …

    …

    6.7.2.1 Structure and union specifiers
    --------------------------------------

    …

    Semantics

    …

    8. The presence of a struct-declaration-list in a
    struct-or-union-specifier declares a new type, within a translation
    unit. The struct-declaration-list is a sequence of declarations for
    the members of the structure or union.  If the struct-declaration-list
    does not contain any named members, either directly or via an anonymous
    structure or anonymous union, the behavior is undefined.  The type is
    -incomplete- *indefinite* until immediately after the } that terminates
    the list, and -complete- *definite* thereafter.

    …

    6.7.2.2 Enumeration specifiers
    ------------------------------

    …

    Semantics

    …

    4. … The enumerated type is -incomplete- *indefinite* until
    immediately after the } that terminates the list of enumerator
    declarations, and -complete- *definite* thereafter.

    …

    6.7.2.3 Tags
    ------------

    …

    Semantics

    4. All declarations of structure, union, or enumerated types that
    have the same scope and use the same tag declare the same
    type. Irrespective of whether there is a tag or what other
    declarations of the type are in the same translation unit, the type
    is -incomplete- *indefinite* 129) until immediately after the closing
    brace of the list defining the content, and -complete- *definite*
    thereafter.

    …

    8. If a type specifier of the form

    struct-or-union identifier

    occurs other than as part of one of the above forms, and no other
    declaration of the identifier as a tag is visible, then it declares
    an -incomplete- *indefinite* structure or union type, and declares the
    identifier as the tag of that type.131)

    …

    129) An -incomplete- *indefinite* type may only by used when -the
    size of an object- *the ability to create an object* of that type
    is not needed.  It is not needed, for example, when a typedef name
    is declared to be a specifier for a structure or union, or when a
    pointer to or a function returning a structure or union is being
    declared. (See -incomplete- *indefinite* types in 6.2.5.) The
    specification has to be -complete- *definite* before such a function
    is called or defined.

    6.7.6.3 Function declarators (including prototypes) 
    ---------------------------------------------------

    …

    Semantics

    …

    12.  If the function declarator is not part of a definition of that
    function, parameters may have -incomplete- *indefinite* type and may use
    the [*] notation in their sequences of declarator specifiers to
    specify variable length array types.

    …

    J.2 Undefined behavior
    ----------------------

        …
      * When the -complete- *definite* type is needed, an -incomplete-
        *indefinite* structure or union type is not completed in the same
        scope by another declaration of the tag that defines the content
        (6.7.2.3).
        …

Sizeless structures
-------------------

These additional changes to N1570 add the concept of a sizeless structure.
Again they apply on top of the edits above:

    6.2.3 Name spaces of identifiers
    --------------------------------

    1. If more than one declaration of a particular identifier is
    visible at any point in a translation unit, the syntactic context
    disambiguates uses that refer to different entities. Thus, there
    are separate name spaces for various categories of identifiers, as
    follows:

	…

      * the tags of *sized* structures, *sizeless structures,* unions, and
	enumerations (disambiguated by following any32) of the keywords
	struct, *__sizeless_struct,* union, or enum);

	…

    6.2.5 Types
    -----------

    1. … Types are partitioned into object types (types that describe
    objects) and function types (types that describe functions).
    Object types are further partitioned into sized and sizeless;
    -all basic and derived types defined in this standard are
    sized, but an implementation may provide additional sizeless types.-
    *the only sizeless types defined by this standard are __sizeless_structs,
    but an implementation may provide additional sizeless types.*

    …

    1B. Arrays, -structures,- unions and enumerated types are always
    sized, so for them the term incomplete is equivalent to (and used
    interchangeably with) the term indefinite.

    …

    20. Any number of derived types can be constructed from the object
    and function types, as follows: …

      * A *sized* structure type describes a sequentially allocated
        nonempty set of sized member objects (and, in certain
        circumstances, an incomplete array), each of which has an
        optionally specified name and possibly distinct type.

      * *A sizeless structure type describes a set of non-overlapping
        member objects whose types may be sizeless and whose relative
        positions are unspecified.  It is also unspecified whether the
        structure occupies a single contiguous piece of storage or
        whether it requires several disjoint pieces.*

    …

    *20A. The term structure type refers collectively to sized structure
    types and sizeless structure types.*

    …

    6.4.1 Keywords
    --------------

    Syntax

    1. *(Add __sizeless_struct to the list and update the copy in A.1.2)*

    …

    6.5.8 Relational operators
    --------------------------

    …

    Semantics

    …

    5. When two pointers are compared, the result depends on the
    relative locations in the address space of the objects pointed to.
    … If the objects pointed to are members of the same aggregate object,
    pointers to *sized* structure members declared later compare greater
    than pointers to members declared earlier in the structure, and
    pointers to array elements with larger subscript values compare
    greater than pointers to elements of the same array with lower
    subscript values. …

    …

    6.7.2.1 Structure and union specifiers
    --------------------------------------

    Syntax

    struct-or-union-specifier:
        struct-or-union identifieropt { struct-declaration-list }
        struct-or-union identifier

    struct-or-union:
        struct
        *__sizeless_struct*
        union

    …

    3. A *sized* structure or union shall not contain a member with
    incomplete or function type …, except that the last member of a
    structure with more than one named member may have incomplete array
    type; such a structure (and any union containing, possibly
    recursively, a member that is such a structure) shall not be a
    member of a structure or an element of an array.  *Simlarly, a
    sizeless structure shall not contain a member with indefinite or
    function type; the exception for incomplete array types does not
    apply.*

    …

    Semantics

    6. As discussed in 6.2.5, a *sized* structure is a type consisting
    of a sequence of members, whose storage is allocated in an ordered
    sequence; *a sizeless structure is a type consisting of
    non-overlapping members whose relative position is unspecified,*
    and a union is a type consisting of a sequence of members whose
    storage overlap.

    7. Structure and union specifiers have the same form. The keywords
    struct, *__sizeless_struct* and union indicate that the type being
    specified is, respectively, a *sized* structure type, *a sizeless
    structure type,* or a union type.

    …[8 is as above]…

    9. A member of a structure or union may have any complete object
    type other than a variably modified type.123)  *A member of a sizeless
    structure may also have a sizeless definite type.*  In addition, a
    member *of a structure or union* may be declared to consist of a
    specified number of bits (including a sign bit, if any). Such a
    member is called a bit-field;124) its width is preceded by a colon.

    …

    15. Within a *sized* structure object, the non-bit-field members and
    the units in which bit-fields reside have addresses that increase in
    the order in which they are declared. A pointer to a *sized* structure
    object, suitably converted, points to its initial member (or if that
    member is a bit-field, then to the unit in which it resides), and
    vice versa. There may be unnamed padding within a *sized* structure
    object, but not at its beginning.

    15A. *The representation of a sizeless structure object is
    unspecified.  It is possible to form pointers to the structure
    itself and to its individual members, but the relationship between
    their addresses is unspecified.  The structure may occupy a single
    piece of contiguous storage or it may occupy several disjoint
    pieces.*

    …

    18 As a special case, the last element of a *sized* structure with
    more than one named member may have an incomplete array type; this
    is called a flexible array member. …

    …

    6.7.2.3 Tags
    ------------

    Constraints

    …

    2. Where two declarations that use the same tag declare the same
    type, they shall both use the same choice of struct, *__sizeless_struct,*
    union, or enum.

    …


Edits to the C++ standard
=========================

We have a similar set of changes to the C++ standard, but this RFC is
long enough already, so I've not included them here.  I also didn't find
them to be particularly useful when writing the C++ patches, since most
of the changes were obvious given a few basic rules.  Those rules are:

  - type traits can be used with sizeless types (unlike incomplete types)

  - sizeless structures cannot have base classes or be used as base classes

  - sizeless structures cannot have virtual members

  - pointers to member variables are invalid for sizeless structures
    (although taking the address of a member of a specific sizeless object
    is fine, as for C)

  - sizeless types are not literal types

  - sizeless types cannot be created by operator new (as for incomplete types)

  - sizeless types cannot be deleted (so, unlike for incomplete types,
    this is an error rather than a warning)

  - sizeless types cannot be thrown or caught (as for incomplete types)

  - sizeless types cannot be used with typeid() (as for incomplete types)


GCC implementation questions
============================

The GCC patches are pretty simple in principle.  The language changes
involve going through the standard replacing "complete" with "definite"
and most of the GCC patches go through the frontend code making the
same kind of change.

New type flag for sizeless types
--------------------------------

The patches add a new flag TYPE_SIZELESS_P to represent the negative of:

  * would fully-defining the type determine its size?

from the summary above.  Negative names are usually a bad thing,
but the natural default is for the flag to be off.

There are currently 17 bits free in tree_type_common, so the patches
steal one of those.  Is that OK?

The effect on COMPLETE_TYPE_P
-----------------------------

The current definition of COMPLETE_TYPE_P is:

    /* Nonzero if this type is a complete type.  */
    #define COMPLETE_TYPE_P(NODE) (TYPE_SIZE (NODE) != NULL_TREE)

Although the SVE types don't have a measurable size at the language
level, they still have a TYPE_SIZE and TYPE_SIZE_UNIT, with the sizes
using placeholders for the runtime vector size.  So after the split
described in the summary, TYPE_SIZE (NODE) != NULL_TREE means
"the type is fully defined" rather than "the type is complete".
With TYPE_SIZELESS_P, the definition of "complete type" would be:

    #define COMPLETE_TYPE_P(NODE) \
      (TYPE_SIZE (NODE) != NULL_TREE && !TYPE_SIZELESS_P (NODE))

i.e. the type is fully-defined, and fully-defining it determines
its size at the language level.

Uses of COMPLETE_TYPE_P outside the frontends
---------------------------------------------

The main complication is that the concept of "complete type" is exposed
outside the frontends, with COMPLETE_TYPE_P being defined in tree.h.

I tried to audit all uses outside the frontends and it looks like
they're all testing whether "the type is fully defined" and don't
care about the distinction between sized and sizeless.  This means
that the current definition (rather than the new definition)
should be correct in all cases.

In some cases the tests are simple null checks, like:

     /* Try to approach equal type sizes.  */
     if (!COMPLETE_TYPE_P (type_a)
         || !COMPLETE_TYPE_P (type_b)
         || !tree_fits_uhwi_p (TYPE_SIZE_UNIT (type_a))
         || !tree_fits_uhwi_p (TYPE_SIZE_UNIT (type_b)))
       break;

IMO it's more obvious to test TYPE_SIZE_UNIT directly for null here.
Having a wrapper doesn't add much.

In places like:

  if (!COMPLETE_TYPE_P (t))
    layout_type (t);

and:

  if (COMPLETE_TYPE_P (t) && TYPE_CANONICAL (t)
      && TYPE_MODE (t) != TYPE_MODE (TYPE_CANONICAL (t)))
    ...

it's testing whether the type has been laid out already.

So the patches do two things:

  * Expand the definition of the current COMPLETE_TYPE_P macro outside
    the frontends if the macro is simply protecting against a null
    dereference.

  * Make COMPLETE_TYPE_P local to the frontends and rename all uses
    outside the frontends.

As far as the second point goes, I wasn't sure what new name to use
outside the front ends.  Possibilities include:

  - DEFINITE_TYPE_P
  - USABLE_TYPE_P
  - VALID_VAR_TYPE_P
  - TYPE_LAID_OUT_P
  - TYPE_DEFINED_P
  - TYPE_FULLY_DEFINED_P
  - TYPE_READY_P
  ...other suggestions welcome...

I went for DEFINITE_TYPE_P because that's what the SVE specification
uses, but something more neutral like TYPE_DEFINED_P might be better.

Frontend changes
----------------

The frontend patches change COMPLETE_TYPE_P to DEFINITE_TYPE_P where
necessary.  I've tried where possible to accompany each individual
change with a test.

This worked fairly naturally (IMO) for C, and most of the changes could
be tied directly to the language edits above.

For C++ it was more difficult (not surprisingly).  There are a lot of
tests for COMPLETE_TYPE_P that are obviously testing whether a class
has been fully defined, and are more concerned with name lookup than
TYPE_SIZE.  The same goes for COMPLETE_OR_OPEN_TYPE_P and whether the
definition has been started.  So while the C changes were relatively
small and self-contained, the C++ changes replace many more uses of
COMPLETE_TYPE_P than they keep.  This makes me wonder whether it's a
good idea to keep COMPLETE_TYPE_P at all, or whether it would be better
to replace the remaining uses with something more explicit like:

  TYPE_SIZE_KNOWN_P
  TYPE_SIZE_DEFINED_P
  TYPE_SIZE_MEASURABLE_P
  TYPE_SIZE_COMPLETE_P
  ...suggestions again welcome...

Thanks,
Richard

Comments

Joseph Myers Oct. 15, 2018, 3 p.m. | #1
On Mon, 15 Oct 2018, Richard Sandiford wrote:

> The patches therefore add a new "__sizeless_struct" keyword to denote

> structures that are sizeless rather than sized.  Unlike normal

> structures, these structures can have members of sizeless type in

> addition to members of sized type.  On the other hand, they have all

> the same limitations as other sizeless types (described in earlier

> sections).


I don't see anything here disallowing offsetof on such structures.

> Edits to the C standard

> =======================

> 

> This section specifies the behaviour for sizeless types as an edit to N1570.


That's a very old standard version.

I'm not in Pittsburgh this week, but I don't see anything to do with these 
ideas on the agenda.  I haven't seen any contributions from Arm to the 
ongoing discussions on the WG14 reflector that include issues relating to 
possibly runtime sized types (vectors, bignums, types representing 
information about another type, for example), unless they're using 
not-obviously-Arm email addresses.  Is Arm going to be engaging in those 
discussions and working with people interested in these areas to produce 
proposals that take account of the different ideas people have for use of 
non-VLA types that may not have a compile-time-constant size (some of 
which may not end up in the C standard, of course)?  (It might of course 
require multiple papers, e.g. starting with fixed-width vector types which 
as a widely-implemented feature are something it might be natural to 
consider for C2x.)

-- 
Joseph S. Myers
joseph@codesourcery.com
Uecker, Martin Oct. 15, 2018, 6:40 p.m. | #2
Hi Richard,

as Joseph pointed out, there are some related discussions
on the WG14 reflector. How a about moving the discussion
there?

I find your approach very interesting and that it already
comes with an implementation is of course very useful

But I don't really understand the reasons why this is not based
on (2). These types are not "sizeless" at all, their size
just isn't known at compile time. So to me this seems to me
a misnomer.

In fact, to me these types *do* in fact seem very similar
to VLAs as VLAs are also complete types which also do no
have a known size at compile time.

That arrays decay to pointers doesn't mean that we
couldn't have similar vectors types which don't decay.
This is hardly a fundamental problem.

I also don't understand the problem about the array
size. If I understand this correctly, the size is somehow
known at run-time and implicitly passed along with the
values. So these new types do not need to have a
size expression (as in your proposal). 

Assignment, the possibility to return the type from
functions, and something like __sizeless_structs would
make sense for VLAs too.

So creating a new category "variable-length types" for 
both VLAs and variably-length vector types seems do make
much more sense to me. As I see it, this would be mainly
a change in terminology and not so much of the underlying
approach.


Best,
Martin

Am Montag, den 15.10.2018, 15:30 +0100 schrieb Richard Sandiford:
> The C standard says:

> 

>     At various points within a translation unit an object type may be

>     "incomplete" (lacking sufficient information to determine the size of

>     objects of that type) or "complete" (having sufficient information).

> 

> For AArch64 SVE, we'd like to split this into two concepts:

> 

>   * has the type been fully defined?

>   * would fully-defining the type determine its size?

> 

> This is because we'd like to be able to represent SVE vectors as C and C++

> types.  Since SVE is a "vector-length agnostic" architecture, the size

> of the vectors is determined by the runtime environment rather than the

> programmer or compiler.  In that sense, defining an SVE vector type does

> not determine its size.  It's nevertheless possible to use SVE vector types

> in meaningful ways, such as having automatic vector variables and passing

> vectors between functions.

> 

> The main questions in the RFC are:

> 

>   1) is splitting the definition like this OK in principle?

>   2) are the specific rules described below OK?

>   3) coding-wise, how should the split be represented in GCC?

> 

> Terminology

> -----------

> 

> Going back to the second bullet above:

> 

>   * would fully-defining the type determine its size?

> 

> the rest of the RFC calls a type "sized" if fully defining it would

> determine its size.  The type is "sizeless" otherwise.

> 

> Contents

> --------

> 

> The RFC is organised as follows.  I've erred on the side of including

> detail rather than leaving it out, but each section is meant to be

> self-contained and skippable:

> 

>   - An earlier RFC

>   - Quick overview of SVE

>   - Why we need SVE types in C and C++

>   - How we ended up with this definition

>   - The SVE types in more detail

>   - Outline of the type system changes

>   - Sizeless structures (and testing on non-SVE targets)

>   - Other variable-length vector architectures

>   - Edits to the C standard

>     - Base changes

>     - Updates for consistency

>     - Sizeless structures

>   - Edits to the C++ standard

>   - GCC implementation questions

> 

> I'll follow up with patches that implement the split.

> 

> 

> 

> An earlier RFC

> ==============

> 

> For the record (in case this sounds familiar) I sent an RFC about the

> sizeless type extension a while ago:

> 

>     https://gcc.gnu.org/ml/gcc/2017-08/msg00012.html

> 

> The rules haven't changed since then, but this version includes more

> information and includes support for sizeless structures.

> 

> 

> Quick overview of SVE

> =====================

> 

> SVE is a vector extension to AArch64.  A detailed description is

> available here:

> 

>     https://static.docs.arm.com/ddi0584/a/DDI0584A_a_SVE_supp_armv8A.pdf

> 

> but the only feature that really matters for this RFC is that SVE has no

> fixed or preferred vector length.  Implementations can instead choose

> from a range of possible vector lengths, with 128 bits being the minimum

> and 2048 bits being the maximum.  Priveleged software can further

> constrain the vector length within the range offered by the implementation;

> e.g. linux currently provides per-thread control of the vector length.

> 

> 

> Why we need SVE types in C and C++

> ==================================

> 

> SVE was designed to be an easy target for autovectorising normal scalar

> code.  There are also various language extensions that support explicit

> data parallelism or that make explicit vector chunking easier to do in

> an architecture-neutral way (e.g. C++ P0214).  This means that many users

> won't need to do anything SVE-specific.

> 

> Even so, there's always going to be a place for writing SVE-specific

> optimisations, with full access to the underlying ISA.  As for other

> vector architectures, we'd like users to be able to write such routines

> in C and C++ rather than force them to go all the way to assembly.

> 

> We'd also like C and C++ functions to be able to take SVE vector

> parameters and return SVE vector results, which is particularly useful

> when implementing things like vector math routines.  In this case in

> particular, the types need to map directly to something that fits in

> an SVE register, so that passing and returning vectors has minimal

> overhead.

> 

> 

> How we ended up with this definition

> ====================================

> 

> Requirements

> ------------

> 

> We need the SVE vector types to define and use SVE intrinsic functions

> and to write SVE vector library routines.  The key requirements when

> defining the types were:

> 

>   * They must be available in both C and C++ (because we want to be able

>     add SVE optimisations to C-only codebases).

> 

>   * They must fit in an SVE vector register (so there can be no on-the-side

>     information).

> 

>   * It must be possible to define automatic variables with these types.

> 

>   * It must be possible to pass and return objects of these types

>     (since that's what intrinsics and vector library routines need to do).

> 

>   * It must be possible to use the types in _Generic associations

>     (so that _Generic can be used to provide tgmath.h-style overloads).

> 

>   * It must be possible to use pointers or references to the types

>     (for passing or returning by pointer or reference, and because not

>     allowing references would be semantically difficult in C++).

> 

> Ideally, there'd also be a way of grouping SVE vectors together into tuples,

> since the ISA has instructions like LD2 that return multiple vectors.

> It would be good if users could also define their own tuple types, on top

> of the ones needed by the intrinsics, although that's more "nice to have".

> 

> Possible approaches

> -------------------

> 

> The main complication is that the size of an SVE vector is not a

> compile-time constant.  It seems that any approach to handling this

> would fall into one of three categories:

> 

>   (1) Limit the types in such a way that there is no concept of size.

> 

>   (2) Define the size of the types to be variable.

> 

>   (3) Define the size of the types to be constant, either with the

>       constant being large enough for all possible vector lengths or

>       with the types pointing to separate memory (as for C++ classes

>       like std::string).

> 

> Why (2) seemed like a bad idea

> ------------------------------

> 

> (2) seemed initially appealing since C already has the concept of

> variable-length arrays.  However, variable-length built-in types

> would work in a significantly different way.  Arrays often decay to

> pointers (which of course are fixed-length types), whereas vector

> types never would.  Unlike arrays, it should be possible to pass

> variable-length vectors to functions, return them from functions,

> and assign them by value.

> 

> One particular difficulty is that the semantics of variable-length arrays

> rely on having a point at which the array size is evaluated.  It would

> be difficult to extend this approach to declarations of functions that

> pass or return variable-length types.

> 

> As well as the extension itself being relatively complex (especially

> for C++), it might be difficult to define it in a way that interacts

> naturally with other (unseen) extensions, even those that are aware of

> variable-length arrays.  Also, AIUI, variable-length arrays were added

> to an early draft of C++14, but were later removed as too controversial

> and didn't make it into the final standard.  C++17 still requires sizeof

> to be constant and C11 makes variable-length arrays optional.

> 

> (2) therefore felt like a complicated dead-end.

> 

> Why (3) seemed like a bad idea

> ------------------------------

> 

> (3) can be divided into two:

> 

> (3a) The vector types have a constant size and are large enough for all

>      possible vector lengths.

> 

>     The main problem with this is that the maximum size of an SVE

>     vector (2048 bits) is much larger than the minimum size (128 bits).

>     Using a fixed size of 2048 bits would be extremely inefficient for

>     smaller vector lengths, and of course the whole point of using

>     vectors is to make things *more* efficient.

> 

>     Also, we would need to define the types such that only the bytes

>     associated with the actual vector length are significant.  This would

>     make it possible to pass or return the types in registers and treat

>     them as register values when copying.  This perhaps has some similarity

>     with overaligned structures such as:

> 

> 	struct s { _Alignas(16) int i; };

> 

>     except that the amount of padding would only be known at runtime.

> 

>     There's also a significant conceptual problem: encoding a fixed size

>     goes against a guiding principle of SVE, in which there is no preferred

>     vector length.  There's nothing particularly magical about the current

>     limit of 2048 bits and it would be better to avoid an ABI break if the

>     maximum ever did increase in future.

> 

> (3b) The vector types have a constant size and refer to separate storage

>      (as for std::string etc.)

> 

>     This would be difficult to do without C++-style constructor, destructor,

>     copy and move semantics, so wouldn't work well in C.  And in C++ it would

>     be less efficient than the proposed approach, since presumably an Allocator

>     would be needed to allocate the separate storage.  It would also require

>     a complicated ABI mapping to ensure that the vectors can still be passed

>     and returned in registers.

> 

> Chosen approach

> ---------------

> 

> We therefore took approach (1) and classified C and C++ types as "sized"

> (having a measurable size when fully-defined) and "sizeless" (never

> having a measurable size).  Sizeless types have no defined size,

> alignment or layout at the language level, with those things becoming

> purely an ABI-level detail.

> 

> We then treated all sizeless types as permanently incomplete.

> On its own, this would put them in a similar situation to "void"

> (although they wouldn't be exactly the same, since there are some

> specific rules for "void" that don't apply to incomplete types in

> general).  We then relaxed specific rules until the types were actually

> useful.

> 

> Things in favour of (1)

> -----------------------

> 

> The reasons above were mostly negative, arriving at (1) by elimination.

> A more positive justification of this approach is that it seems

> to meet the requirements in the most efficient way possible.  The

> vectors can use their natural (native) representation, and the type

> system prevents uses that would make that representation problematic.

> 

> Also, the approach of starting with very restricted types and then

> specifically allowing certain things should be more future-proof

> and interact better with other language extensions.  By default,

> any language extension would treat the new types like other incomplete

> types and choose conservatively-correct behaviour.  It would then be

> possible to relax the language extension if this default behaviour

> turns out to be too restrictive.

> 

> (That said, treating the types as permanently incomplete still won't

> avoid all clashes with other extensions.  For example, we need to

> allow objects of automatic storage duration to have certain forms of

> incomplete type, whereas an extension might implicitly assume that all

> such objects must already have complete type.  The approach should still

> avoid the worst effects though.)

> 

> 

> The SVE types in more detail

> ============================

> 

> Arm has published an SVE "ACLE" that specifies the SVE types and intrinsic

> functions in detail.  For reference this is available without registration

> at:

> 

>     https://static.docs.arm.com/100987/0000/acle_sve_100987_0000_00_en.pdf

> 

> but I'll try to keep this self-contained.

> 

> The ACLE defines a vector type sv<base>_t for each supported element type

> <base>_t, so that the complete set is:

> 

>     svint8_t      svint16_t     svint32_t     svint64_t

>     svuint8_t     svuint16_t    svuint32_t    svuint64_t

>                   svfloat16_t   svfloat32_t   svfloat64_t

> 

> The types in each column have the same number of lanes and have twice

> as many lanes as those in the column to the right.  Every vector has

> the same number of bytes in total, with the number of bytes being

> determined at runtime.

> 

> The ACLE also defines a single predicate type:

> 

>     svbool_t

> 

> that has the same number of lanes as svint8_t and svuint8_t.

> 

> All these types are opaque builtin types and are only expected to

> be used with the associated ACLE intrinsics.  There are intrinsics for

> creating vectors from scalars, loading from scalars, storing to scalars,

> reinterpreting one type as another, etc.

> 

> The idea is that the vector types would only be used for short-term

> register-sized working data.  Longer-term data would typically be stored

> out to arrays.

> 

> For example, the vector function underlying:

> 

>     #pragma omp declare simd

>     double sin(double);

> 

> would be:

> 

>     svfloat64_t mangled_sin(svfloat64_t, svbool_t);

> 

> (The svbool_t is because SVE functions should be predicated by default,

> to avoid the need for a scalar epilogue loop.)

> 

> The ACLE also defines x2, x3 and x4 tuple types for each vector type;

> for example, svint8x3_t is a tuple of 3 svint8_ts.  The tuples are

> structure-like types with fields v0, v1, v2 and v3, up to the number

> required.

> 

> 

> Outline of the type system changes

> ==================================

> 

> Going back to the summary at the start of the RFC, C classifies types as

> "complete" (the size of objects can be calculated) or "incomplete" (the

> size of objects can't be calculated).  There's very little you can do

> with a type until it becomes complete.

> 

> The approach we took was to treat all the SVE types as permanently

> incomplete.  We then went through the standard relaxing specific

> rules until the types were actually useful.

> 

> The first step was to classify types as:

> 

>   * "indefinite" (lacking sufficient information to create an object of

>     that type) or "definite" (having sufficient information)

> 

>   * "sized" (will have a known size when definite) or "sizeless" (will

>     never have a known size)

> 

>   * "incomplete" (lacking sufficient information to determine the size of

>     objects of that type) or "complete" (having sufficient information)

> 

> where the wording for the final bullet is unchanged from the standard.

> Thus a "definite type" is one that has been fully-defined rather than

> simply declared, and "complete" is now equivalent to "sized and definite".

> All standard types are "sized" (even "void", although it's always

> indefinite and incomplete).

> 

> We then needed to make some rules use the distinction between "indefinite"

> and "definite" rather than "incomplete" and "complete".  The specific

> things we wanted to allow were:

> 

>   * defining automatic variables with sizeless definite type

>   * defining functions whose parameters have sizeless definite type

>   * defining functions that return a sizeless definite type

>   * using sizeless definite types in _Generic associations

>   * dereferencing pointers to sizeless definite types

> 

> Specific things we wanted to remain invalid -- by inheriting the rules from

> incomplete types -- were:

> 

>   * creating or accessing arrays that have sizeless element types

>   * doing pointer arithmetic on pointers to sizeless types

>   * using sizeof and _Alignof with a sizeless type (or object of sizeless type)

>   * defining (sized) unions or structures with sizeless members

> 

> It also seemed worth adding an extra restriction:

> 

>   * variables with sizeless type must not have static or thread-local

>     storage duration

> 

> In practice it's impossible to define such variables with incomplete type,

> but having an explicit rule means that things like:

> 

>     extern svint8_t foo;  // An SVE vector of int8_t elements.

> 

> are outright invalid rather than simply useless (because no other

> translation unit could ever define foo).  Similarly, without an

> explicit rule:

> 

>     svint8_t foo;         // An SVE vector of int8_t elements.

> 

> would be a valid tentative definition at the point it occurs and only

> become invalid at the end of the translation unit, because svint8_t is

> never completed.

> 

> This restriction isn't critical but it gives better diagnostics.

> 

> 

> Sizeless structures (and testing on non-SVE targets)

> ====================================================

> 

> We're planning to build all SVE intrinsic types directly into GCC

> (patches already written).  SVE therefore doesn't strictly need a syntax

> for creating new sizeless types in C and C++.  However, having a way of

> creating new structure-like "sizeless" types would be useful for three

> reasons:

> 

>   - Functions could return arbitrary data by value.  The SVE ABI allows

>     a function to return up to 8 vectors and 4 predicates in registers,

>     which is far more flexible than the intrinsic types.

> 

>   - We could use these sizeless structure types to test the functionality

>     on all targets.

> 

>   - A lot of the C++ frontend is concerned with classes, and having

>     a way of creating sizeless classes would help make the C++ changes

>     more consistent.

> 

> The patches therefore add a new "__sizeless_struct" keyword to denote

> structures that are sizeless rather than sized.  Unlike normal

> structures, these structures can have members of sizeless type in

> addition to members of sized type.  On the other hand, they have all

> the same limitations as other sizeless types (described in earlier

> sections).

> 

> E.g., a sizeless structure definition might look like:

> 

>     __sizeless_struct data {

>       double *array;

>       svuint64_t indices;  // An SVE vector of uint64_t elements.

>       svbool_t active;     // An SVE predicate.

>     };

> 

> Adding a new keyword seemed better than using an attribute because it

> means that the sized vs. sizeless distinction is fixed by the declaration.

> E.g.:

> 

>     struct data;                     // Is it sized or sizeless?

>     extern struct data global_data;  // OK if sized, not if sizeless.

>     struct __attribute__((sizeless)) data {

>       double *array;

>       svuint64_t indices;            // An SVE vector of uint64_t elements.

>       svbool_t active;               // An SVE predicate.

>     };

> 

> would lead to the declaration of "global_data" sneaking through

> despite being invalid when "data" is sizeless.

> 

> The tests in the patches all use these __sizeless_structs; they contain

> nothing SVE- or AArch64-specific.

> 

> 

> Other variable-length vector architectures

> ==========================================

> 

> The proposed RISC-V vector extension also has variable-length vectors.

> When this language change was discussed on the clang developers' list,

> Bruce Hoult (from SiFive, but speaking personally) replied with:

> 

>     http://lists.llvm.org/pipermail/cfe-dev/2018-May/057943.html

> 

> That message covers some of the background about the vector extension.

> On the language changes, Bruce said:

> 

>     > However, even though the length is variable, the concept of a

>     > "register-sized" C and C++ vector type makes just as much sense for SVE

>     > as it does for other vector architectures.  Vector library functions

>     > take such register-sized vectors as input and return them as results.

>     > Intrinsic functions are also just as useful as they are for other vector

>     > architectures, and they too take register-sized vectors as input and

>     > return them as results.

> 

>     Intrinsic functions are absolutely required, and are I think the main

>     reason for such a low-level register-sized vector type to exist.

> 

> [ Bruce went on to say:

> 

>     I'm not sure whether user-written functions operating on register-sized

>     vectors are useful enough to support. User-written functions would normally

>     take and return a higher-level vector type, and would implement the desired

>     functionality in terms of calls to other user-written functions (operating

>     on the high level vector as a whole) and/or explicit loops iterating

>     through the high level vector type using intrinsic functions on the

>     register-sized vector type proposed here.

> 

> But this use case is very important for SVE, since it will allow us

> to implement vector math routines in a way that works with the OpenMP

> "declare simd" construct.  There was also talk on gcc@ recently about

> supporting this style of interface for RISC-V. ]

> 

> [...]

> 

>     > All these types are opaque builtin types and are only intended to be

>     > used with the associated ACLE intrinsics.  There are intrinsics for

>     > creating vectors from scalars, loading from scalars, storing to scalars,

>     > reinterpreting one type as another, etc.

>     >

>     > The idea is that the vector types would only be used for short-term

>     > register-sized working data.  Longer-term data would typically be stored

>     > out to arrays.

> 

>     I agree with this.

> 

> [...]

> 

>     > The approach we took was to treat all the SVE types as permanently

>     > incomplete.

> 

>     This seems reasonable.

> 

> So it looks like this extension would be useful for at least one

> architecture besides SVE.

> 

> 

> Edits to the C standard

> =======================

> 

> This section specifies the behaviour for sizeless types as an edit to N1570.

> There are three stages:

> 

>   - base changes, which add enough support for built-in sizeless

>     vector types

> 

>   - updates for consistency, which change some of the wording without

>     changing the meaning

> 

>   - support for sizeless structures

> 

> In each case, -strikethrough- indicates deleted text and *bold*

> includes additional text.

> 

> 

> Base changes

> ------------

> 

> These changes are enough to support sizeless built-in vector types.

> 

>     6.2.5 Types

>     -----------

> 

>     1. The meaning of a value stored in an object or returned by a

>     function is determined by the type of the expression used to access

>     it. … Types are partitioned into object types (types that

>     describe objects) and function types (types that describe

>     functions).  -At various points within a translation unit an object

>     type may be incomplete (lacking sufficient information to determine

>     the size of objects of that type) or complete (having sufficient

>     information).37)- *Object types are further partitioned into sized and

>     sizeless; all basic and derived types defined in this standard are

>     sized, but an implementation may provide additional sizeless types.*

> 

>     1A. *At various points within a translation unit an object type may

>     be indefinite (lacking sufficient information to construct an object

>     of that type) or definite (having sufficient information).37) An

>     object type is said to be complete if it is both sized and definite;

>     all other object types are said to be incomplete.  Complete types

>     have sufficient information to determine the size of an object of

>     that type while incomplete types do not.*

> 

>     1B. *Arrays, structures, unions and enumerated types are always

>     sized, so for them the term incomplete is equivalent to (and used

>     interchangeably with) the term indefinite.*

> 

>     …

> 

>     19. The void type comprises an empty set of values; it is -an

>     incomplete- *a sized indefinite* object type that cannot be completed

>     *(made definite)*.

> 

>     …

> 

>     37) A type may be -incomplete- *indefinite* or -complete- *definite*

>     throughout an entire translation unit, or it may change states at

>     different points within a translation unit.

> 

>     …

> 

>     6.3.2.1 Lvalues, arrays, and function designators

>     -------------------------------------------------

> 

>     1.  An lvalue is an expression (with an object type other than void)

>     that potentially designates an object;64) … A modifiable lvalue is

>     an lvalue that does not have array type, does not have an

>     -incomplete- *indefinite* type, does not have a const-qualified

>     type, …

> 

>     2.  Except when it is the operand of the sizeof operator, the

>     _Alignof operator, the unary & operator, the ++ operator, the --

>     operator, or the left operand of the . operator or an assignment

>     operator, an lvalue that does not have array type is converted to

>     the value stored in the designated object (and is no longer an

>     lvalue); this is called lvalue conversion. … If the lvalue has an

>     -incomplete- *indefinite* type and does not have array type, the

>     behavior is undefined. …

> 

>     …

> 

>     6.5.1.1 Generic selection

>     -------------------------

> 

>     …

> 

>     Constraints

> 

>     2. A generic selection shall have no more than one default generic

>     association. The type name in a generic association shall specify a

>     -complete- *definite* object type other than a variably modified

>     type. …

> 

>     …

> 

>     6.5.2.2 Function calls

>     ----------------------

> 

>     Constraints

> 

>     1. The expression that denotes the called function92) shall have

>     type pointer to function returning void or returning a -complete-

>     *definite* object type other than an array type.

> 

>     …

> 

>     Semantics

> 

>     …

> 

>     4. An argument may be an expression of any -complete- *definite* object

>     type. …

> 

>     …

> 

>     6.5.2.5 Compound literals

>     -------------------------

> 

>     Constraints

> 

>     1. The type name shall specify a -complete- *definite* object type or an

>     array of unknown size, but not a variable length array type.

> 

>     …

> 

>     6.7 Declarations

>     ----------------

> 

>     Constraints

> 

>     …

> 

>     4A. *If an identifier for an object does not have automatic storage

>     duration, its type must be sized rather than sizeless.*

> 

>     Semantics

> 

>     …

> 

>     7. If an identifier for an object is declared with no linkage, the

>     type for the object shall be -complete- *definite* by the end of its

>     declarator, or by the end of its init-declarator if it has an

>     initializer; in the case of function parameters (including in

>     prototypes), it is the adjusted type (see 6.7.6.3) that is required

>     to be -complete- *definite*.

> 

>     …

>      

>     6.7.6.3 Function declarators (including prototypes) 

>     ---------------------------------------------------

> 

>     Constraints

> 

>     …

> 

>     4. After adjustment, the parameters in a parameter type list in a

>     function declarator that is part of a definition of that function

>     shall not have -incomplete- *indefinite* type.

> 

>     …

> 

>     6.7.9 Initialization

>     --------------------

> 

>     Constraints

> 

>     …

> 

>     3. The type of the entity to be initialized shall be an array of

>     unknown size or a -complete- *definite* object type that is not a

>     variable length array type.

> 

>     …

> 

>     6.9.1 Function definitions

>     --------------------------

> 

>     Constraints

> 

>     …

> 

>     3. The return type of a function shall be void or a -complete-

>     *definite* object type other than array type.

> 

>     …

> 

>     Semantics

> 

>     …

> 

>     7. The declarator in a function definition specifies the name of the

>     function being defined and the identifiers of its parameters. …

>     [T]he type of each parameter is adjusted as described in

>     6.7.6.3 for a parameter type list; the resulting type shall be a

>     -complete- *definite* object type.

> 

>     …

> 

>     J.2 Undefined behavior

>     ----------------------

> 

>         …

>       * A non-array lvalue with -an incomplete- *an indefinite* type is used

>         in a context that requires the value of the designated object

>         (6.3.2.1).

>         …

>       * An identifier for an object is declared with no linkage and the

>         type of the object is -incomplete- *indefinite* after its

>         declarator, or after its init-declarator if it has an

>         initializer (6.7).

>         …

>       * An adjusted parameter type in a function definition is not a

>         -complete- *definite* object type (6.9.1).

>         …

> 

> Updates for consistency

> -----------------------

> 

> These changes are a prerequisite for sizeless structures.  They have no

> effect otherwise, but might be preferred anyway because they make the

> terminology more consistent.  They apply on top of the previous edits.

> 

>     6.2.5 Types

>     -----------

> 

>     …

> 

>     22. An array type of unknown size is an -incomplete- *indefinite*

>     type. It is -completed- *made definite*, for an identifier of that type,

>     by specifying the size in a later declaration (with internal or

>     external linkage). A structure or union type of unknown content (as

>     described in 6.7.2.3) is an -incomplete- *indefinite* type. It is

>     -completed- *made definite*, for all declarations of that type, by

>     declaring the same structure or union tag with its defining content

>     later in the same scope.

> 

>     …

> 

>     6.2.7 Compatible type and composite type

>     ----------------------------------------

> 

>     1. Two types have compatible type if their types are the same. …

>     Moreover, two structure, union, or enumerated types declared in

>     separate translation units are compatible if their tags and members

>     satisfy the following requirements: If one is declared with a tag,

>     the other shall be declared with the same tag. If both are

>     -completed- *made definite* anywhere within their respective

>     translation units, then the following additional requirements apply: …

> 

>     …

> 

>     6.7.2.1 Structure and union specifiers

>     --------------------------------------

> 

>     …

> 

>     Semantics

> 

>     …

> 

>     8. The presence of a struct-declaration-list in a

>     struct-or-union-specifier declares a new type, within a translation

>     unit. The struct-declaration-list is a sequence of declarations for

>     the members of the structure or union.  If the struct-declaration-list

>     does not contain any named members, either directly or via an anonymous

>     structure or anonymous union, the behavior is undefined.  The type is

>     -incomplete- *indefinite* until immediately after the } that terminates

>     the list, and -complete- *definite* thereafter.

> 

>     …

> 

>     6.7.2.2 Enumeration specifiers

>     ------------------------------

> 

>     …

> 

>     Semantics

> 

>     …

> 

>     4. … The enumerated type is -incomplete- *indefinite* until

>     immediately after the } that terminates the list of enumerator

>     declarations, and -complete- *definite* thereafter.

> 

>     …

> 

>     6.7.2.3 Tags

>     ------------

> 

>     …

> 

>     Semantics

> 

>     4. All declarations of structure, union, or enumerated types that

>     have the same scope and use the same tag declare the same

>     type. Irrespective of whether there is a tag or what other

>     declarations of the type are in the same translation unit, the type

>     is -incomplete- *indefinite* 129) until immediately after the closing

>     brace of the list defining the content, and -complete- *definite*

>     thereafter.

> 

>     …

> 

>     8. If a type specifier of the form

> 

>     struct-or-union identifier

> 

>     occurs other than as part of one of the above forms, and no other

>     declaration of the identifier as a tag is visible, then it declares

>     an -incomplete- *indefinite* structure or union type, and declares the

>     identifier as the tag of that type.131)

> 

>     …

> 

>     129) An -incomplete- *indefinite* type may only by used when -the

>     size of an object- *the ability to create an object* of that type

>     is not needed.  It is not needed, for example, when a typedef name

>     is declared to be a specifier for a structure or union, or when a

>     pointer to or a function returning a structure or union is being

>     declared. (See -incomplete- *indefinite* types in 6.2.5.) The

>     specification has to be -complete- *definite* before such a function

>     is called or defined.

> 

>     6.7.6.3 Function declarators (including prototypes) 

>     ---------------------------------------------------

> 

>     …

> 

>     Semantics

> 

>     …

> 

>     12.  If the function declarator is not part of a definition of that

>     function, parameters may have -incomplete- *indefinite* type and may use

>     the [*] notation in their sequences of declarator specifiers to

>     specify variable length array types.

> 

>     …

> 

>     J.2 Undefined behavior

>     ----------------------

> 

>         …

>       * When the -complete- *definite* type is needed, an -incomplete-

>         *indefinite* structure or union type is not completed in the same

>         scope by another declaration of the tag that defines the content

>         (6.7.2.3).

>         …

> 

> Sizeless structures

> -------------------

> 

> These additional changes to N1570 add the concept of a sizeless structure.

> Again they apply on top of the edits above:

> 

>     6.2.3 Name spaces of identifiers

>     --------------------------------

> 

>     1. If more than one declaration of a particular identifier is

>     visible at any point in a translation unit, the syntactic context

>     disambiguates uses that refer to different entities. Thus, there

>     are separate name spaces for various categories of identifiers, as

>     follows:

> 

> 	…

> 

>       * the tags of *sized* structures, *sizeless structures,* unions, and

> 	enumerations (disambiguated by following any32) of the keywords

> 	struct, *__sizeless_struct,* union, or enum);

> 

> 	…

> 

>     6.2.5 Types

>     -----------

> 

>     1. … Types are partitioned into object types (types that describe

>     objects) and function types (types that describe functions).

>     Object types are further partitioned into sized and sizeless;

>     -all basic and derived types defined in this standard are

>     sized, but an implementation may provide additional sizeless types.-

>     *the only sizeless types defined by this standard are __sizeless_structs,

>     but an implementation may provide additional sizeless types.*

> 

>     …

> 

>     1B. Arrays, -structures,- unions and enumerated types are always

>     sized, so for them the term incomplete is equivalent to (and used

>     interchangeably with) the term indefinite.

> 

>     …

> 

>     20. Any number of derived types can be constructed from the object

>     and function types, as follows: …

> 

>       * A *sized* structure type describes a sequentially allocated

>         nonempty set of sized member objects (and, in certain

>         circumstances, an incomplete array), each of which has an

>         optionally specified name and possibly distinct type.

> 

>       * *A sizeless structure type describes a set of non-overlapping

>         member objects whose types may be sizeless and whose relative

>         positions are unspecified.  It is also unspecified whether the

>         structure occupies a single contiguous piece of storage or

>         whether it requires several disjoint pieces.*

> 

>     …

> 

>     *20A. The term structure type refers collectively to sized structure

>     types and sizeless structure types.*

> 

>     …

> 

>     6.4.1 Keywords

>     --------------

> 

>     Syntax

> 

>     1. *(Add __sizeless_struct to the list and update the copy in A.1.2)*

> 

>     …

> 

>     6.5.8 Relational operators

>     --------------------------

> 

>     …

> 

>     Semantics

> 

>     …

> 

>     5. When two pointers are compared, the result depends on the

>     relative locations in the address space of the objects pointed to.

>     … If the objects pointed to are members of the same aggregate object,

>     pointers to *sized* structure members declared later compare greater

>     than pointers to members declared earlier in the structure, and

>     pointers to array elements with larger subscript values compare

>     greater than pointers to elements of the same array with lower

>     subscript values. …

> 

>     …

> 

>     6.7.2.1 Structure and union specifiers

>     --------------------------------------

> 

>     Syntax

> 

>     struct-or-union-specifier:

>         struct-or-union identifieropt { struct-declaration-list }

>         struct-or-union identifier

> 

>     struct-or-union:

>         struct

>         *__sizeless_struct*

>         union

> 

>     …

> 

>     3. A *sized* structure or union shall not contain a member with

>     incomplete or function type …, except that the last member of a

>     structure with more than one named member may have incomplete array

>     type; such a structure (and any union containing, possibly

>     recursively, a member that is such a structure) shall not be a

>     member of a structure or an element of an array.  *Simlarly, a

>     sizeless structure shall not contain a member with indefinite or

>     function type; the exception for incomplete array types does not

>     apply.*

> 

>     …

> 

>     Semantics

> 

>     6. As discussed in 6.2.5, a *sized* structure is a type consisting

>     of a sequence of members, whose storage is allocated in an ordered

>     sequence; *a sizeless structure is a type consisting of

>     non-overlapping members whose relative position is unspecified,*

>     and a union is a type consisting of a sequence of members whose

>     storage overlap.

> 

>     7. Structure and union specifiers have the same form. The keywords

>     struct, *__sizeless_struct* and union indicate that the type being

>     specified is, respectively, a *sized* structure type, *a sizeless

>     structure type,* or a union type.

> 

>     …[8 is as above]…

> 

>     9. A member of a structure or union may have any complete object

>     type other than a variably modified type.123)  *A member of a sizeless

>     structure may also have a sizeless definite type.*  In addition, a

>     member *of a structure or union* may be declared to consist of a

>     specified number of bits (including a sign bit, if any). Such a

>     member is called a bit-field;124) its width is preceded by a colon.

> 

>     …

> 

>     15. Within a *sized* structure object, the non-bit-field members and

>     the units in which bit-fields reside have addresses that increase in

>     the order in which they are declared. A pointer to a *sized* structure

>     object, suitably converted, points to its initial member (or if that

>     member is a bit-field, then to the unit in which it resides), and

>     vice versa. There may be unnamed padding within a *sized* structure

>     object, but not at its beginning.

> 

>     15A. *The representation of a sizeless structure object is

>     unspecified.  It is possible to form pointers to the structure

>     itself and to its individual members, but the relationship between

>     their addresses is unspecified.  The structure may occupy a single

>     piece of contiguous storage or it may occupy several disjoint

>     pieces.*

> 

>     …

> 

>     18 As a special case, the last element of a *sized* structure with

>     more than one named member may have an incomplete array type; this

>     is called a flexible array member. …

> 

>     …

> 

>     6.7.2.3 Tags

>     ------------

> 

>     Constraints

> 

>     …

> 

>     2. Where two declarations that use the same tag declare the same

>     type, they shall both use the same choice of struct, *__sizeless_struct,*

>     union, or enum.

> 

>     …

> 

> 

> Edits to the C++ standard

> =========================

> 

> We have a similar set of changes to the C++ standard, but this RFC is

> long enough already, so I've not included them here.  I also didn't find

> them to be particularly useful when writing the C++ patches, since most

> of the changes were obvious given a few basic rules.  Those rules are:

> 

>   - type traits can be used with sizeless types (unlike incomplete types)

> 

>   - sizeless structures cannot have base classes or be used as base classes

> 

>   - sizeless structures cannot have virtual members

> 

>   - pointers to member variables are invalid for sizeless structures

>     (although taking the address of a member of a specific sizeless object

>     is fine, as for C)

> 

>   - sizeless types are not literal types

> 

>   - sizeless types cannot be created by operator new (as for incomplete types)

> 

>   - sizeless types cannot be deleted (so, unlike for incomplete types,

>     this is an error rather than a warning)

> 

>   - sizeless types cannot be thrown or caught (as for incomplete types)

> 

>   - sizeless types cannot be used with typeid() (as for incomplete types)

> 

> 

> GCC implementation questions

> ============================

> 

> The GCC patches are pretty simple in principle.  The language changes

> involve going through the standard replacing "complete" with "definite"

> and most of the GCC patches go through the frontend code making the

> same kind of change.

> 

> New type flag for sizeless types

> --------------------------------

> 

> The patches add a new flag TYPE_SIZELESS_P to represent the negative of:

> 

>   * would fully-defining the type determine its size?

> 

> from the summary above.  Negative names are usually a bad thing,

> but the natural default is for the flag to be off.

> 

> There are currently 17 bits free in tree_type_common, so the patches

> steal one of those.  Is that OK?

> 

> The effect on COMPLETE_TYPE_P

> -----------------------------

> 

> The current definition of COMPLETE_TYPE_P is:

> 

>     /* Nonzero if this type is a complete type.  */

>     #define COMPLETE_TYPE_P(NODE) (TYPE_SIZE (NODE) != NULL_TREE)

> 

> Although the SVE types don't have a measurable size at the language

> level, they still have a TYPE_SIZE and TYPE_SIZE_UNIT, with the sizes

> using placeholders for the runtime vector size.  So after the split

> described in the summary, TYPE_SIZE (NODE) != NULL_TREE means

> "the type is fully defined" rather than "the type is complete".

> With TYPE_SIZELESS_P, the definition of "complete type" would be:

> 

>     #define COMPLETE_TYPE_P(NODE) \

>       (TYPE_SIZE (NODE) != NULL_TREE && !TYPE_SIZELESS_P (NODE))

> 

> i.e. the type is fully-defined, and fully-defining it determines

> its size at the language level.

> 

> Uses of COMPLETE_TYPE_P outside the frontends

> ---------------------------------------------

> 

> The main complication is that the concept of "complete type" is exposed

> outside the frontends, with COMPLETE_TYPE_P being defined in tree.h.

> 

> I tried to audit all uses outside the frontends and it looks like

> they're all testing whether "the type is fully defined" and don't

> care about the distinction between sized and sizeless.  This means

> that the current definition (rather than the new definition)

> should be correct in all cases.

> 

> In some cases the tests are simple null checks, like:

> 

>      /* Try to approach equal type sizes.  */

>      if (!COMPLETE_TYPE_P (type_a)

>          || !COMPLETE_TYPE_P (type_b)

>          || !tree_fits_uhwi_p (TYPE_SIZE_UNIT (type_a))

>          || !tree_fits_uhwi_p (TYPE_SIZE_UNIT (type_b)))

>        break;

> 

> IMO it's more obvious to test TYPE_SIZE_UNIT directly for null here.

> Having a wrapper doesn't add much.

> 

> In places like:

> 

>   if (!COMPLETE_TYPE_P (t))

>     layout_type (t);

> 

> and:

> 

>   if (COMPLETE_TYPE_P (t) && TYPE_CANONICAL (t)

>       && TYPE_MODE (t) != TYPE_MODE (TYPE_CANONICAL (t)))

>     ...

> 

> it's testing whether the type has been laid out already.

> 

> So the patches do two things:

> 

>   * Expand the definition of the current COMPLETE_TYPE_P macro outside

>     the frontends if the macro is simply protecting against a null

>     dereference.

> 

>   * Make COMPLETE_TYPE_P local to the frontends and rename all uses

>     outside the frontends.

> 

> As far as the second point goes, I wasn't sure what new name to use

> outside the front ends.  Possibilities include:

> 

>   - DEFINITE_TYPE_P

>   - USABLE_TYPE_P

>   - VALID_VAR_TYPE_P

>   - TYPE_LAID_OUT_P

>   - TYPE_DEFINED_P

>   - TYPE_FULLY_DEFINED_P

>   - TYPE_READY_P

>   ...other suggestions welcome...

> 

> I went for DEFINITE_TYPE_P because that's what the SVE specification

> uses, but something more neutral like TYPE_DEFINED_P might be better.

> 

> Frontend changes

> ----------------

> 

> The frontend patches change COMPLETE_TYPE_P to DEFINITE_TYPE_P where

> necessary.  I've tried where possible to accompany each individual

> change with a test.

> 

> This worked fairly naturally (IMO) for C, and most of the changes could

> be tied directly to the language edits above.

> 

> For C++ it was more difficult (not surprisingly).  There are a lot of

> tests for COMPLETE_TYPE_P that are obviously testing whether a class

> has been fully defined, and are more concerned with name lookup than

> TYPE_SIZE.  The same goes for COMPLETE_OR_OPEN_TYPE_P and whether the

> definition has been started.  So while the C changes were relatively

> small and self-contained, the C++ changes replace many more uses of

> COMPLETE_TYPE_P than they keep.  This makes me wonder whether it's a

> good idea to keep COMPLETE_TYPE_P at all, or whether it would be better

> to replace the remaining uses with something more explicit like:

> 

>   TYPE_SIZE_KNOWN_P

>   TYPE_SIZE_DEFINED_P

>   TYPE_SIZE_MEASURABLE_P

>   TYPE_SIZE_COMPLETE_P

>   ...suggestions again welcome...

> 

> Thanks,

> Richard
Richard Biener Oct. 16, 2018, 7:52 a.m. | #3
On Mon, Oct 15, 2018 at 8:40 PM Uecker, Martin
<Martin.Uecker@med.uni-goettingen.de> wrote:
>

>

> Hi Richard,

>

> as Joseph pointed out, there are some related discussions

> on the WG14 reflector. How a about moving the discussion

> there?

>

> I find your approach very interesting and that it already

> comes with an implementation is of course very useful

>

> But I don't really understand the reasons why this is not based

> on (2). These types are not "sizeless" at all, their size

> just isn't known at compile time. So to me this seems to me

> a misnomer.

>

> In fact, to me these types *do* in fact seem very similar

> to VLAs as VLAs are also complete types which also do no

> have a known size at compile time.

>

> That arrays decay to pointers doesn't mean that we

> couldn't have similar vectors types which don't decay.

> This is hardly a fundamental problem.

>

> I also don't understand the problem about the array

> size. If I understand this correctly, the size is somehow

> known at run-time and implicitly passed along with the

> values. So these new types do not need to have a

> size expression (as in your proposal).

>

> Assignment, the possibility to return the type from

> functions, and something like __sizeless_structs would

> make sense for VLAs too.

>

> So creating a new category "variable-length types" for

> both VLAs and variably-length vector types seems do make

> much more sense to me. As I see it, this would be mainly

> a change in terminology and not so much of the underlying

> approach.


I agree - those types very much feel like VLAs.

I think there's also the existing vector extension of GCC to
factor in which introduces (non-VLA) vector types to the
language and allows arithmetic on them as well as
indexing and passing and returing them by values.
Variable-size vectors should play well in that context.

Richard.

>

> Best,

> Martin

>

> Am Montag, den 15.10.2018, 15:30 +0100 schrieb Richard Sandiford:

> > The C standard says:

> >

> >     At various points within a translation unit an object type may be

> >     "incomplete" (lacking sufficient information to determine the size of

> >     objects of that type) or "complete" (having sufficient information).

> >

> > For AArch64 SVE, we'd like to split this into two concepts:

> >

> >   * has the type been fully defined?

> >   * would fully-defining the type determine its size?

> >

> > This is because we'd like to be able to represent SVE vectors as C and C++

> > types.  Since SVE is a "vector-length agnostic" architecture, the size

> > of the vectors is determined by the runtime environment rather than the

> > programmer or compiler.  In that sense, defining an SVE vector type does

> > not determine its size.  It's nevertheless possible to use SVE vector types

> > in meaningful ways, such as having automatic vector variables and passing

> > vectors between functions.

> >

> > The main questions in the RFC are:

> >

> >   1) is splitting the definition like this OK in principle?

> >   2) are the specific rules described below OK?

> >   3) coding-wise, how should the split be represented in GCC?

> >

> > Terminology

> > -----------

> >

> > Going back to the second bullet above:

> >

> >   * would fully-defining the type determine its size?

> >

> > the rest of the RFC calls a type "sized" if fully defining it would

> > determine its size.  The type is "sizeless" otherwise.

> >

> > Contents

> > --------

> >

> > The RFC is organised as follows.  I've erred on the side of including

> > detail rather than leaving it out, but each section is meant to be

> > self-contained and skippable:

> >

> >   - An earlier RFC

> >   - Quick overview of SVE

> >   - Why we need SVE types in C and C++

> >   - How we ended up with this definition

> >   - The SVE types in more detail

> >   - Outline of the type system changes

> >   - Sizeless structures (and testing on non-SVE targets)

> >   - Other variable-length vector architectures

> >   - Edits to the C standard

> >     - Base changes

> >     - Updates for consistency

> >     - Sizeless structures

> >   - Edits to the C++ standard

> >   - GCC implementation questions

> >

> > I'll follow up with patches that implement the split.

> >

> >

> >

> > An earlier RFC

> > ==============

> >

> > For the record (in case this sounds familiar) I sent an RFC about the

> > sizeless type extension a while ago:

> >

> >     https://gcc.gnu.org/ml/gcc/2017-08/msg00012.html

> >

> > The rules haven't changed since then, but this version includes more

> > information and includes support for sizeless structures.

> >

> >

> > Quick overview of SVE

> > =====================

> >

> > SVE is a vector extension to AArch64.  A detailed description is

> > available here:

> >

> >     https://static.docs.arm.com/ddi0584/a/DDI0584A_a_SVE_supp_armv8A.pdf

> >

> > but the only feature that really matters for this RFC is that SVE has no

> > fixed or preferred vector length.  Implementations can instead choose

> > from a range of possible vector lengths, with 128 bits being the minimum

> > and 2048 bits being the maximum.  Priveleged software can further

> > constrain the vector length within the range offered by the implementation;

> > e.g. linux currently provides per-thread control of the vector length.

> >

> >

> > Why we need SVE types in C and C++

> > ==================================

> >

> > SVE was designed to be an easy target for autovectorising normal scalar

> > code.  There are also various language extensions that support explicit

> > data parallelism or that make explicit vector chunking easier to do in

> > an architecture-neutral way (e.g. C++ P0214).  This means that many users

> > won't need to do anything SVE-specific.

> >

> > Even so, there's always going to be a place for writing SVE-specific

> > optimisations, with full access to the underlying ISA.  As for other

> > vector architectures, we'd like users to be able to write such routines

> > in C and C++ rather than force them to go all the way to assembly.

> >

> > We'd also like C and C++ functions to be able to take SVE vector

> > parameters and return SVE vector results, which is particularly useful

> > when implementing things like vector math routines.  In this case in

> > particular, the types need to map directly to something that fits in

> > an SVE register, so that passing and returning vectors has minimal

> > overhead.

> >

> >

> > How we ended up with this definition

> > ====================================

> >

> > Requirements

> > ------------

> >

> > We need the SVE vector types to define and use SVE intrinsic functions

> > and to write SVE vector library routines.  The key requirements when

> > defining the types were:

> >

> >   * They must be available in both C and C++ (because we want to be able

> >     add SVE optimisations to C-only codebases).

> >

> >   * They must fit in an SVE vector register (so there can be no on-the-side

> >     information).

> >

> >   * It must be possible to define automatic variables with these types.

> >

> >   * It must be possible to pass and return objects of these types

> >     (since that's what intrinsics and vector library routines need to do).

> >

> >   * It must be possible to use the types in _Generic associations

> >     (so that _Generic can be used to provide tgmath.h-style overloads).

> >

> >   * It must be possible to use pointers or references to the types

> >     (for passing or returning by pointer or reference, and because not

> >     allowing references would be semantically difficult in C++).

> >

> > Ideally, there'd also be a way of grouping SVE vectors together into tuples,

> > since the ISA has instructions like LD2 that return multiple vectors.

> > It would be good if users could also define their own tuple types, on top

> > of the ones needed by the intrinsics, although that's more "nice to have".

> >

> > Possible approaches

> > -------------------

> >

> > The main complication is that the size of an SVE vector is not a

> > compile-time constant.  It seems that any approach to handling this

> > would fall into one of three categories:

> >

> >   (1) Limit the types in such a way that there is no concept of size.

> >

> >   (2) Define the size of the types to be variable.

> >

> >   (3) Define the size of the types to be constant, either with the

> >       constant being large enough for all possible vector lengths or

> >       with the types pointing to separate memory (as for C++ classes

> >       like std::string).

> >

> > Why (2) seemed like a bad idea

> > ------------------------------

> >

> > (2) seemed initially appealing since C already has the concept of

> > variable-length arrays.  However, variable-length built-in types

> > would work in a significantly different way.  Arrays often decay to

> > pointers (which of course are fixed-length types), whereas vector

> > types never would.  Unlike arrays, it should be possible to pass

> > variable-length vectors to functions, return them from functions,

> > and assign them by value.

> >

> > One particular difficulty is that the semantics of variable-length arrays

> > rely on having a point at which the array size is evaluated.  It would

> > be difficult to extend this approach to declarations of functions that

> > pass or return variable-length types.

> >

> > As well as the extension itself being relatively complex (especially

> > for C++), it might be difficult to define it in a way that interacts

> > naturally with other (unseen) extensions, even those that are aware of

> > variable-length arrays.  Also, AIUI, variable-length arrays were added

> > to an early draft of C++14, but were later removed as too controversial

> > and didn't make it into the final standard.  C++17 still requires sizeof

> > to be constant and C11 makes variable-length arrays optional.

> >

> > (2) therefore felt like a complicated dead-end.

> >

> > Why (3) seemed like a bad idea

> > ------------------------------

> >

> > (3) can be divided into two:

> >

> > (3a) The vector types have a constant size and are large enough for all

> >      possible vector lengths.

> >

> >     The main problem with this is that the maximum size of an SVE

> >     vector (2048 bits) is much larger than the minimum size (128 bits).

> >     Using a fixed size of 2048 bits would be extremely inefficient for

> >     smaller vector lengths, and of course the whole point of using

> >     vectors is to make things *more* efficient.

> >

> >     Also, we would need to define the types such that only the bytes

> >     associated with the actual vector length are significant.  This would

> >     make it possible to pass or return the types in registers and treat

> >     them as register values when copying.  This perhaps has some similarity

> >     with overaligned structures such as:

> >

> >       struct s { _Alignas(16) int i; };

> >

> >     except that the amount of padding would only be known at runtime.

> >

> >     There's also a significant conceptual problem: encoding a fixed size

> >     goes against a guiding principle of SVE, in which there is no preferred

> >     vector length.  There's nothing particularly magical about the current

> >     limit of 2048 bits and it would be better to avoid an ABI break if the

> >     maximum ever did increase in future.

> >

> > (3b) The vector types have a constant size and refer to separate storage

> >      (as for std::string etc.)

> >

> >     This would be difficult to do without C++-style constructor, destructor,

> >     copy and move semantics, so wouldn't work well in C.  And in C++ it would

> >     be less efficient than the proposed approach, since presumably an Allocator

> >     would be needed to allocate the separate storage.  It would also require

> >     a complicated ABI mapping to ensure that the vectors can still be passed

> >     and returned in registers.

> >

> > Chosen approach

> > ---------------

> >

> > We therefore took approach (1) and classified C and C++ types as "sized"

> > (having a measurable size when fully-defined) and "sizeless" (never

> > having a measurable size).  Sizeless types have no defined size,

> > alignment or layout at the language level, with those things becoming

> > purely an ABI-level detail.

> >

> > We then treated all sizeless types as permanently incomplete.

> > On its own, this would put them in a similar situation to "void"

> > (although they wouldn't be exactly the same, since there are some

> > specific rules for "void" that don't apply to incomplete types in

> > general).  We then relaxed specific rules until the types were actually

> > useful.

> >

> > Things in favour of (1)

> > -----------------------

> >

> > The reasons above were mostly negative, arriving at (1) by elimination.

> > A more positive justification of this approach is that it seems

> > to meet the requirements in the most efficient way possible.  The

> > vectors can use their natural (native) representation, and the type

> > system prevents uses that would make that representation problematic.

> >

> > Also, the approach of starting with very restricted types and then

> > specifically allowing certain things should be more future-proof

> > and interact better with other language extensions.  By default,

> > any language extension would treat the new types like other incomplete

> > types and choose conservatively-correct behaviour.  It would then be

> > possible to relax the language extension if this default behaviour

> > turns out to be too restrictive.

> >

> > (That said, treating the types as permanently incomplete still won't

> > avoid all clashes with other extensions.  For example, we need to

> > allow objects of automatic storage duration to have certain forms of

> > incomplete type, whereas an extension might implicitly assume that all

> > such objects must already have complete type.  The approach should still

> > avoid the worst effects though.)

> >

> >

> > The SVE types in more detail

> > ============================

> >

> > Arm has published an SVE "ACLE" that specifies the SVE types and intrinsic

> > functions in detail.  For reference this is available without registration

> > at:

> >

> >     https://static.docs.arm.com/100987/0000/acle_sve_100987_0000_00_en.pdf

> >

> > but I'll try to keep this self-contained.

> >

> > The ACLE defines a vector type sv<base>_t for each supported element type

> > <base>_t, so that the complete set is:

> >

> >     svint8_t      svint16_t     svint32_t     svint64_t

> >     svuint8_t     svuint16_t    svuint32_t    svuint64_t

> >                   svfloat16_t   svfloat32_t   svfloat64_t

> >

> > The types in each column have the same number of lanes and have twice

> > as many lanes as those in the column to the right.  Every vector has

> > the same number of bytes in total, with the number of bytes being

> > determined at runtime.

> >

> > The ACLE also defines a single predicate type:

> >

> >     svbool_t

> >

> > that has the same number of lanes as svint8_t and svuint8_t.

> >

> > All these types are opaque builtin types and are only expected to

> > be used with the associated ACLE intrinsics.  There are intrinsics for

> > creating vectors from scalars, loading from scalars, storing to scalars,

> > reinterpreting one type as another, etc.

> >

> > The idea is that the vector types would only be used for short-term

> > register-sized working data.  Longer-term data would typically be stored

> > out to arrays.

> >

> > For example, the vector function underlying:

> >

> >     #pragma omp declare simd

> >     double sin(double);

> >

> > would be:

> >

> >     svfloat64_t mangled_sin(svfloat64_t, svbool_t);

> >

> > (The svbool_t is because SVE functions should be predicated by default,

> > to avoid the need for a scalar epilogue loop.)

> >

> > The ACLE also defines x2, x3 and x4 tuple types for each vector type;

> > for example, svint8x3_t is a tuple of 3 svint8_ts.  The tuples are

> > structure-like types with fields v0, v1, v2 and v3, up to the number

> > required.

> >

> >

> > Outline of the type system changes

> > ==================================

> >

> > Going back to the summary at the start of the RFC, C classifies types as

> > "complete" (the size of objects can be calculated) or "incomplete" (the

> > size of objects can't be calculated).  There's very little you can do

> > with a type until it becomes complete.

> >

> > The approach we took was to treat all the SVE types as permanently

> > incomplete.  We then went through the standard relaxing specific

> > rules until the types were actually useful.

> >

> > The first step was to classify types as:

> >

> >   * "indefinite" (lacking sufficient information to create an object of

> >     that type) or "definite" (having sufficient information)

> >

> >   * "sized" (will have a known size when definite) or "sizeless" (will

> >     never have a known size)

> >

> >   * "incomplete" (lacking sufficient information to determine the size of

> >     objects of that type) or "complete" (having sufficient information)

> >

> > where the wording for the final bullet is unchanged from the standard.

> > Thus a "definite type" is one that has been fully-defined rather than

> > simply declared, and "complete" is now equivalent to "sized and definite".

> > All standard types are "sized" (even "void", although it's always

> > indefinite and incomplete).

> >

> > We then needed to make some rules use the distinction between "indefinite"

> > and "definite" rather than "incomplete" and "complete".  The specific

> > things we wanted to allow were:

> >

> >   * defining automatic variables with sizeless definite type

> >   * defining functions whose parameters have sizeless definite type

> >   * defining functions that return a sizeless definite type

> >   * using sizeless definite types in _Generic associations

> >   * dereferencing pointers to sizeless definite types

> >

> > Specific things we wanted to remain invalid -- by inheriting the rules from

> > incomplete types -- were:

> >

> >   * creating or accessing arrays that have sizeless element types

> >   * doing pointer arithmetic on pointers to sizeless types

> >   * using sizeof and _Alignof with a sizeless type (or object of sizeless type)

> >   * defining (sized) unions or structures with sizeless members

> >

> > It also seemed worth adding an extra restriction:

> >

> >   * variables with sizeless type must not have static or thread-local

> >     storage duration

> >

> > In practice it's impossible to define such variables with incomplete type,

> > but having an explicit rule means that things like:

> >

> >     extern svint8_t foo;  // An SVE vector of int8_t elements.

> >

> > are outright invalid rather than simply useless (because no other

> > translation unit could ever define foo).  Similarly, without an

> > explicit rule:

> >

> >     svint8_t foo;         // An SVE vector of int8_t elements.

> >

> > would be a valid tentative definition at the point it occurs and only

> > become invalid at the end of the translation unit, because svint8_t is

> > never completed.

> >

> > This restriction isn't critical but it gives better diagnostics.

> >

> >

> > Sizeless structures (and testing on non-SVE targets)

> > ====================================================

> >

> > We're planning to build all SVE intrinsic types directly into GCC

> > (patches already written).  SVE therefore doesn't strictly need a syntax

> > for creating new sizeless types in C and C++.  However, having a way of

> > creating new structure-like "sizeless" types would be useful for three

> > reasons:

> >

> >   - Functions could return arbitrary data by value.  The SVE ABI allows

> >     a function to return up to 8 vectors and 4 predicates in registers,

> >     which is far more flexible than the intrinsic types.

> >

> >   - We could use these sizeless structure types to test the functionality

> >     on all targets.

> >

> >   - A lot of the C++ frontend is concerned with classes, and having

> >     a way of creating sizeless classes would help make the C++ changes

> >     more consistent.

> >

> > The patches therefore add a new "__sizeless_struct" keyword to denote

> > structures that are sizeless rather than sized.  Unlike normal

> > structures, these structures can have members of sizeless type in

> > addition to members of sized type.  On the other hand, they have all

> > the same limitations as other sizeless types (described in earlier

> > sections).

> >

> > E.g., a sizeless structure definition might look like:

> >

> >     __sizeless_struct data {

> >       double *array;

> >       svuint64_t indices;  // An SVE vector of uint64_t elements.

> >       svbool_t active;     // An SVE predicate.

> >     };

> >

> > Adding a new keyword seemed better than using an attribute because it

> > means that the sized vs. sizeless distinction is fixed by the declaration.

> > E.g.:

> >

> >     struct data;                     // Is it sized or sizeless?

> >     extern struct data global_data;  // OK if sized, not if sizeless.

> >     struct __attribute__((sizeless)) data {

> >       double *array;

> >       svuint64_t indices;            // An SVE vector of uint64_t elements.

> >       svbool_t active;               // An SVE predicate.

> >     };

> >

> > would lead to the declaration of "global_data" sneaking through

> > despite being invalid when "data" is sizeless.

> >

> > The tests in the patches all use these __sizeless_structs; they contain

> > nothing SVE- or AArch64-specific.

> >

> >

> > Other variable-length vector architectures

> > ==========================================

> >

> > The proposed RISC-V vector extension also has variable-length vectors.

> > When this language change was discussed on the clang developers' list,

> > Bruce Hoult (from SiFive, but speaking personally) replied with:

> >

> >     http://lists.llvm.org/pipermail/cfe-dev/2018-May/057943.html

> >

> > That message covers some of the background about the vector extension.

> > On the language changes, Bruce said:

> >

> >     > However, even though the length is variable, the concept of a

> >     > "register-sized" C and C++ vector type makes just as much sense for SVE

> >     > as it does for other vector architectures.  Vector library functions

> >     > take such register-sized vectors as input and return them as results.

> >     > Intrinsic functions are also just as useful as they are for other vector

> >     > architectures, and they too take register-sized vectors as input and

> >     > return them as results.

> >

> >     Intrinsic functions are absolutely required, and are I think the main

> >     reason for such a low-level register-sized vector type to exist.

> >

> > [ Bruce went on to say:

> >

> >     I'm not sure whether user-written functions operating on register-sized

> >     vectors are useful enough to support. User-written functions would normally

> >     take and return a higher-level vector type, and would implement the desired

> >     functionality in terms of calls to other user-written functions (operating

> >     on the high level vector as a whole) and/or explicit loops iterating

> >     through the high level vector type using intrinsic functions on the

> >     register-sized vector type proposed here.

> >

> > But this use case is very important for SVE, since it will allow us

> > to implement vector math routines in a way that works with the OpenMP

> > "declare simd" construct.  There was also talk on gcc@ recently about

> > supporting this style of interface for RISC-V. ]

> >

> > [...]

> >

> >     > All these types are opaque builtin types and are only intended to be

> >     > used with the associated ACLE intrinsics.  There are intrinsics for

> >     > creating vectors from scalars, loading from scalars, storing to scalars,

> >     > reinterpreting one type as another, etc.

> >     >

> >     > The idea is that the vector types would only be used for short-term

> >     > register-sized working data.  Longer-term data would typically be stored

> >     > out to arrays.

> >

> >     I agree with this.

> >

> > [...]

> >

> >     > The approach we took was to treat all the SVE types as permanently

> >     > incomplete.

> >

> >     This seems reasonable.

> >

> > So it looks like this extension would be useful for at least one

> > architecture besides SVE.

> >

> >

> > Edits to the C standard

> > =======================

> >

> > This section specifies the behaviour for sizeless types as an edit to N1570.

> > There are three stages:

> >

> >   - base changes, which add enough support for built-in sizeless

> >     vector types

> >

> >   - updates for consistency, which change some of the wording without

> >     changing the meaning

> >

> >   - support for sizeless structures

> >

> > In each case, -strikethrough- indicates deleted text and *bold*

> > includes additional text.

> >

> >

> > Base changes

> > ------------

> >

> > These changes are enough to support sizeless built-in vector types.

> >

> >     6.2.5 Types

> >     -----------

> >

> >     1. The meaning of a value stored in an object or returned by a

> >     function is determined by the type of the expression used to access

> >     it. … Types are partitioned into object types (types that

> >     describe objects) and function types (types that describe

> >     functions).  -At various points within a translation unit an object

> >     type may be incomplete (lacking sufficient information to determine

> >     the size of objects of that type) or complete (having sufficient

> >     information).37)- *Object types are further partitioned into sized and

> >     sizeless; all basic and derived types defined in this standard are

> >     sized, but an implementation may provide additional sizeless types.*

> >

> >     1A. *At various points within a translation unit an object type may

> >     be indefinite (lacking sufficient information to construct an object

> >     of that type) or definite (having sufficient information).37) An

> >     object type is said to be complete if it is both sized and definite;

> >     all other object types are said to be incomplete.  Complete types

> >     have sufficient information to determine the size of an object of

> >     that type while incomplete types do not.*

> >

> >     1B. *Arrays, structures, unions and enumerated types are always

> >     sized, so for them the term incomplete is equivalent to (and used

> >     interchangeably with) the term indefinite.*

> >

> >     …

> >

> >     19. The void type comprises an empty set of values; it is -an

> >     incomplete- *a sized indefinite* object type that cannot be completed

> >     *(made definite)*.

> >

> >     …

> >

> >     37) A type may be -incomplete- *indefinite* or -complete- *definite*

> >     throughout an entire translation unit, or it may change states at

> >     different points within a translation unit.

> >

> >     …

> >

> >     6.3.2.1 Lvalues, arrays, and function designators

> >     -------------------------------------------------

> >

> >     1.  An lvalue is an expression (with an object type other than void)

> >     that potentially designates an object;64) … A modifiable lvalue is

> >     an lvalue that does not have array type, does not have an

> >     -incomplete- *indefinite* type, does not have a const-qualified

> >     type, …

> >

> >     2.  Except when it is the operand of the sizeof operator, the

> >     _Alignof operator, the unary & operator, the ++ operator, the --

> >     operator, or the left operand of the . operator or an assignment

> >     operator, an lvalue that does not have array type is converted to

> >     the value stored in the designated object (and is no longer an

> >     lvalue); this is called lvalue conversion. … If the lvalue has an

> >     -incomplete- *indefinite* type and does not have array type, the

> >     behavior is undefined. …

> >

> >     …

> >

> >     6.5.1.1 Generic selection

> >     -------------------------

> >

> >     …

> >

> >     Constraints

> >

> >     2. A generic selection shall have no more than one default generic

> >     association. The type name in a generic association shall specify a

> >     -complete- *definite* object type other than a variably modified

> >     type. …

> >

> >     …

> >

> >     6.5.2.2 Function calls

> >     ----------------------

> >

> >     Constraints

> >

> >     1. The expression that denotes the called function92) shall have

> >     type pointer to function returning void or returning a -complete-

> >     *definite* object type other than an array type.

> >

> >     …

> >

> >     Semantics

> >

> >     …

> >

> >     4. An argument may be an expression of any -complete- *definite* object

> >     type. …

> >

> >     …

> >

> >     6.5.2.5 Compound literals

> >     -------------------------

> >

> >     Constraints

> >

> >     1. The type name shall specify a -complete- *definite* object type or an

> >     array of unknown size, but not a variable length array type.

> >

> >     …

> >

> >     6.7 Declarations

> >     ----------------

> >

> >     Constraints

> >

> >     …

> >

> >     4A. *If an identifier for an object does not have automatic storage

> >     duration, its type must be sized rather than sizeless.*

> >

> >     Semantics

> >

> >     …

> >

> >     7. If an identifier for an object is declared with no linkage, the

> >     type for the object shall be -complete- *definite* by the end of its

> >     declarator, or by the end of its init-declarator if it has an

> >     initializer; in the case of function parameters (including in

> >     prototypes), it is the adjusted type (see 6.7.6.3) that is required

> >     to be -complete- *definite*.

> >

> >     …

> >

> >     6.7.6.3 Function declarators (including prototypes)

> >     ---------------------------------------------------

> >

> >     Constraints

> >

> >     …

> >

> >     4. After adjustment, the parameters in a parameter type list in a

> >     function declarator that is part of a definition of that function

> >     shall not have -incomplete- *indefinite* type.

> >

> >     …

> >

> >     6.7.9 Initialization

> >     --------------------

> >

> >     Constraints

> >

> >     …

> >

> >     3. The type of the entity to be initialized shall be an array of

> >     unknown size or a -complete- *definite* object type that is not a

> >     variable length array type.

> >

> >     …

> >

> >     6.9.1 Function definitions

> >     --------------------------

> >

> >     Constraints

> >

> >     …

> >

> >     3. The return type of a function shall be void or a -complete-

> >     *definite* object type other than array type.

> >

> >     …

> >

> >     Semantics

> >

> >     …

> >

> >     7. The declarator in a function definition specifies the name of the

> >     function being defined and the identifiers of its parameters. …

> >     [T]he type of each parameter is adjusted as described in

> >     6.7.6.3 for a parameter type list; the resulting type shall be a

> >     -complete- *definite* object type.

> >

> >     …

> >

> >     J.2 Undefined behavior

> >     ----------------------

> >

> >         …

> >       * A non-array lvalue with -an incomplete- *an indefinite* type is used

> >         in a context that requires the value of the designated object

> >         (6.3.2.1).

> >         …

> >       * An identifier for an object is declared with no linkage and the

> >         type of the object is -incomplete- *indefinite* after its

> >         declarator, or after its init-declarator if it has an

> >         initializer (6.7).

> >         …

> >       * An adjusted parameter type in a function definition is not a

> >         -complete- *definite* object type (6.9.1).

> >         …

> >

> > Updates for consistency

> > -----------------------

> >

> > These changes are a prerequisite for sizeless structures.  They have no

> > effect otherwise, but might be preferred anyway because they make the

> > terminology more consistent.  They apply on top of the previous edits.

> >

> >     6.2.5 Types

> >     -----------

> >

> >     …

> >

> >     22. An array type of unknown size is an -incomplete- *indefinite*

> >     type. It is -completed- *made definite*, for an identifier of that type,

> >     by specifying the size in a later declaration (with internal or

> >     external linkage). A structure or union type of unknown content (as

> >     described in 6.7.2.3) is an -incomplete- *indefinite* type. It is

> >     -completed- *made definite*, for all declarations of that type, by

> >     declaring the same structure or union tag with its defining content

> >     later in the same scope.

> >

> >     …

> >

> >     6.2.7 Compatible type and composite type

> >     ----------------------------------------

> >

> >     1. Two types have compatible type if their types are the same. …

> >     Moreover, two structure, union, or enumerated types declared in

> >     separate translation units are compatible if their tags and members

> >     satisfy the following requirements: If one is declared with a tag,

> >     the other shall be declared with the same tag. If both are

> >     -completed- *made definite* anywhere within their respective

> >     translation units, then the following additional requirements apply: …

> >

> >     …

> >

> >     6.7.2.1 Structure and union specifiers

> >     --------------------------------------

> >

> >     …

> >

> >     Semantics

> >

> >     …

> >

> >     8. The presence of a struct-declaration-list in a

> >     struct-or-union-specifier declares a new type, within a translation

> >     unit. The struct-declaration-list is a sequence of declarations for

> >     the members of the structure or union.  If the struct-declaration-list

> >     does not contain any named members, either directly or via an anonymous

> >     structure or anonymous union, the behavior is undefined.  The type is

> >     -incomplete- *indefinite* until immediately after the } that terminates

> >     the list, and -complete- *definite* thereafter.

> >

> >     …

> >

> >     6.7.2.2 Enumeration specifiers

> >     ------------------------------

> >

> >     …

> >

> >     Semantics

> >

> >     …

> >

> >     4. … The enumerated type is -incomplete- *indefinite* until

> >     immediately after the } that terminates the list of enumerator

> >     declarations, and -complete- *definite* thereafter.

> >

> >     …

> >

> >     6.7.2.3 Tags

> >     ------------

> >

> >     …

> >

> >     Semantics

> >

> >     4. All declarations of structure, union, or enumerated types that

> >     have the same scope and use the same tag declare the same

> >     type. Irrespective of whether there is a tag or what other

> >     declarations of the type are in the same translation unit, the type

> >     is -incomplete- *indefinite* 129) until immediately after the closing

> >     brace of the list defining the content, and -complete- *definite*

> >     thereafter.

> >

> >     …

> >

> >     8. If a type specifier of the form

> >

> >     struct-or-union identifier

> >

> >     occurs other than as part of one of the above forms, and no other

> >     declaration of the identifier as a tag is visible, then it declares

> >     an -incomplete- *indefinite* structure or union type, and declares the

> >     identifier as the tag of that type.131)

> >

> >     …

> >

> >     129) An -incomplete- *indefinite* type may only by used when -the

> >     size of an object- *the ability to create an object* of that type

> >     is not needed.  It is not needed, for example, when a typedef name

> >     is declared to be a specifier for a structure or union, or when a

> >     pointer to or a function returning a structure or union is being

> >     declared. (See -incomplete- *indefinite* types in 6.2.5.) The

> >     specification has to be -complete- *definite* before such a function

> >     is called or defined.

> >

> >     6.7.6.3 Function declarators (including prototypes)

> >     ---------------------------------------------------

> >

> >     …

> >

> >     Semantics

> >

> >     …

> >

> >     12.  If the function declarator is not part of a definition of that

> >     function, parameters may have -incomplete- *indefinite* type and may use

> >     the [*] notation in their sequences of declarator specifiers to

> >     specify variable length array types.

> >

> >     …

> >

> >     J.2 Undefined behavior

> >     ----------------------

> >

> >         …

> >       * When the -complete- *definite* type is needed, an -incomplete-

> >         *indefinite* structure or union type is not completed in the same

> >         scope by another declaration of the tag that defines the content

> >         (6.7.2.3).

> >         …

> >

> > Sizeless structures

> > -------------------

> >

> > These additional changes to N1570 add the concept of a sizeless structure.

> > Again they apply on top of the edits above:

> >

> >     6.2.3 Name spaces of identifiers

> >     --------------------------------

> >

> >     1. If more than one declaration of a particular identifier is

> >     visible at any point in a translation unit, the syntactic context

> >     disambiguates uses that refer to different entities. Thus, there

> >     are separate name spaces for various categories of identifiers, as

> >     follows:

> >

> >       …

> >

> >       * the tags of *sized* structures, *sizeless structures,* unions, and

> >       enumerations (disambiguated by following any32) of the keywords

> >       struct, *__sizeless_struct,* union, or enum);

> >

> >       …

> >

> >     6.2.5 Types

> >     -----------

> >

> >     1. … Types are partitioned into object types (types that describe

> >     objects) and function types (types that describe functions).

> >     Object types are further partitioned into sized and sizeless;

> >     -all basic and derived types defined in this standard are

> >     sized, but an implementation may provide additional sizeless types.-

> >     *the only sizeless types defined by this standard are __sizeless_structs,

> >     but an implementation may provide additional sizeless types.*

> >

> >     …

> >

> >     1B. Arrays, -structures,- unions and enumerated types are always

> >     sized, so for them the term incomplete is equivalent to (and used

> >     interchangeably with) the term indefinite.

> >

> >     …

> >

> >     20. Any number of derived types can be constructed from the object

> >     and function types, as follows: …

> >

> >       * A *sized* structure type describes a sequentially allocated

> >         nonempty set of sized member objects (and, in certain

> >         circumstances, an incomplete array), each of which has an

> >         optionally specified name and possibly distinct type.

> >

> >       * *A sizeless structure type describes a set of non-overlapping

> >         member objects whose types may be sizeless and whose relative

> >         positions are unspecified.  It is also unspecified whether the

> >         structure occupies a single contiguous piece of storage or

> >         whether it requires several disjoint pieces.*

> >

> >     …

> >

> >     *20A. The term structure type refers collectively to sized structure

> >     types and sizeless structure types.*

> >

> >     …

> >

> >     6.4.1 Keywords

> >     --------------

> >

> >     Syntax

> >

> >     1. *(Add __sizeless_struct to the list and update the copy in A.1.2)*

> >

> >     …

> >

> >     6.5.8 Relational operators

> >     --------------------------

> >

> >     …

> >

> >     Semantics

> >

> >     …

> >

> >     5. When two pointers are compared, the result depends on the

> >     relative locations in the address space of the objects pointed to.

> >     … If the objects pointed to are members of the same aggregate object,

> >     pointers to *sized* structure members declared later compare greater

> >     than pointers to members declared earlier in the structure, and

> >     pointers to array elements with larger subscript values compare

> >     greater than pointers to elements of the same array with lower

> >     subscript values. …

> >

> >     …

> >

> >     6.7.2.1 Structure and union specifiers

> >     --------------------------------------

> >

> >     Syntax

> >

> >     struct-or-union-specifier:

> >         struct-or-union identifieropt { struct-declaration-list }

> >         struct-or-union identifier

> >

> >     struct-or-union:

> >         struct

> >         *__sizeless_struct*

> >         union

> >

> >     …

> >

> >     3. A *sized* structure or union shall not contain a member with

> >     incomplete or function type …, except that the last member of a

> >     structure with more than one named member may have incomplete array

> >     type; such a structure (and any union containing, possibly

> >     recursively, a member that is such a structure) shall not be a

> >     member of a structure or an element of an array.  *Simlarly, a

> >     sizeless structure shall not contain a member with indefinite or

> >     function type; the exception for incomplete array types does not

> >     apply.*

> >

> >     …

> >

> >     Semantics

> >

> >     6. As discussed in 6.2.5, a *sized* structure is a type consisting

> >     of a sequence of members, whose storage is allocated in an ordered

> >     sequence; *a sizeless structure is a type consisting of

> >     non-overlapping members whose relative position is unspecified,*

> >     and a union is a type consisting of a sequence of members whose

> >     storage overlap.

> >

> >     7. Structure and union specifiers have the same form. The keywords

> >     struct, *__sizeless_struct* and union indicate that the type being

> >     specified is, respectively, a *sized* structure type, *a sizeless

> >     structure type,* or a union type.

> >

> >     …[8 is as above]…

> >

> >     9. A member of a structure or union may have any complete object

> >     type other than a variably modified type.123)  *A member of a sizeless

> >     structure may also have a sizeless definite type.*  In addition, a

> >     member *of a structure or union* may be declared to consist of a

> >     specified number of bits (including a sign bit, if any). Such a

> >     member is called a bit-field;124) its width is preceded by a colon.

> >

> >     …

> >

> >     15. Within a *sized* structure object, the non-bit-field members and

> >     the units in which bit-fields reside have addresses that increase in

> >     the order in which they are declared. A pointer to a *sized* structure

> >     object, suitably converted, points to its initial member (or if that

> >     member is a bit-field, then to the unit in which it resides), and

> >     vice versa. There may be unnamed padding within a *sized* structure

> >     object, but not at its beginning.

> >

> >     15A. *The representation of a sizeless structure object is

> >     unspecified.  It is possible to form pointers to the structure

> >     itself and to its individual members, but the relationship between

> >     their addresses is unspecified.  The structure may occupy a single

> >     piece of contiguous storage or it may occupy several disjoint

> >     pieces.*

> >

> >     …

> >

> >     18 As a special case, the last element of a *sized* structure with

> >     more than one named member may have an incomplete array type; this

> >     is called a flexible array member. …

> >

> >     …

> >

> >     6.7.2.3 Tags

> >     ------------

> >

> >     Constraints

> >

> >     …

> >

> >     2. Where two declarations that use the same tag declare the same

> >     type, they shall both use the same choice of struct, *__sizeless_struct,*

> >     union, or enum.

> >

> >     …

> >

> >

> > Edits to the C++ standard

> > =========================

> >

> > We have a similar set of changes to the C++ standard, but this RFC is

> > long enough already, so I've not included them here.  I also didn't find

> > them to be particularly useful when writing the C++ patches, since most

> > of the changes were obvious given a few basic rules.  Those rules are:

> >

> >   - type traits can be used with sizeless types (unlike incomplete types)

> >

> >   - sizeless structures cannot have base classes or be used as base classes

> >

> >   - sizeless structures cannot have virtual members

> >

> >   - pointers to member variables are invalid for sizeless structures

> >     (although taking the address of a member of a specific sizeless object

> >     is fine, as for C)

> >

> >   - sizeless types are not literal types

> >

> >   - sizeless types cannot be created by operator new (as for incomplete types)

> >

> >   - sizeless types cannot be deleted (so, unlike for incomplete types,

> >     this is an error rather than a warning)

> >

> >   - sizeless types cannot be thrown or caught (as for incomplete types)

> >

> >   - sizeless types cannot be used with typeid() (as for incomplete types)

> >

> >

> > GCC implementation questions

> > ============================

> >

> > The GCC patches are pretty simple in principle.  The language changes

> > involve going through the standard replacing "complete" with "definite"

> > and most of the GCC patches go through the frontend code making the

> > same kind of change.

> >

> > New type flag for sizeless types

> > --------------------------------

> >

> > The patches add a new flag TYPE_SIZELESS_P to represent the negative of:

> >

> >   * would fully-defining the type determine its size?

> >

> > from the summary above.  Negative names are usually a bad thing,

> > but the natural default is for the flag to be off.

> >

> > There are currently 17 bits free in tree_type_common, so the patches

> > steal one of those.  Is that OK?

> >

> > The effect on COMPLETE_TYPE_P

> > -----------------------------

> >

> > The current definition of COMPLETE_TYPE_P is:

> >

> >     /* Nonzero if this type is a complete type.  */

> >     #define COMPLETE_TYPE_P(NODE) (TYPE_SIZE (NODE) != NULL_TREE)

> >

> > Although the SVE types don't have a measurable size at the language

> > level, they still have a TYPE_SIZE and TYPE_SIZE_UNIT, with the sizes

> > using placeholders for the runtime vector size.  So after the split

> > described in the summary, TYPE_SIZE (NODE) != NULL_TREE means

> > "the type is fully defined" rather than "the type is complete".

> > With TYPE_SIZELESS_P, the definition of "complete type" would be:

> >

> >     #define COMPLETE_TYPE_P(NODE) \

> >       (TYPE_SIZE (NODE) != NULL_TREE && !TYPE_SIZELESS_P (NODE))

> >

> > i.e. the type is fully-defined, and fully-defining it determines

> > its size at the language level.

> >

> > Uses of COMPLETE_TYPE_P outside the frontends

> > ---------------------------------------------

> >

> > The main complication is that the concept of "complete type" is exposed

> > outside the frontends, with COMPLETE_TYPE_P being defined in tree.h.

> >

> > I tried to audit all uses outside the frontends and it looks like

> > they're all testing whether "the type is fully defined" and don't

> > care about the distinction between sized and sizeless.  This means

> > that the current definition (rather than the new definition)

> > should be correct in all cases.

> >

> > In some cases the tests are simple null checks, like:

> >

> >      /* Try to approach equal type sizes.  */

> >      if (!COMPLETE_TYPE_P (type_a)

> >          || !COMPLETE_TYPE_P (type_b)

> >          || !tree_fits_uhwi_p (TYPE_SIZE_UNIT (type_a))

> >          || !tree_fits_uhwi_p (TYPE_SIZE_UNIT (type_b)))

> >        break;

> >

> > IMO it's more obvious to test TYPE_SIZE_UNIT directly for null here.

> > Having a wrapper doesn't add much.

> >

> > In places like:

> >

> >   if (!COMPLETE_TYPE_P (t))

> >     layout_type (t);

> >

> > and:

> >

> >   if (COMPLETE_TYPE_P (t) && TYPE_CANONICAL (t)

> >       && TYPE_MODE (t) != TYPE_MODE (TYPE_CANONICAL (t)))

> >     ...

> >

> > it's testing whether the type has been laid out already.

> >

> > So the patches do two things:

> >

> >   * Expand the definition of the current COMPLETE_TYPE_P macro outside

> >     the frontends if the macro is simply protecting against a null

> >     dereference.

> >

> >   * Make COMPLETE_TYPE_P local to the frontends and rename all uses

> >     outside the frontends.

> >

> > As far as the second point goes, I wasn't sure what new name to use

> > outside the front ends.  Possibilities include:

> >

> >   - DEFINITE_TYPE_P

> >   - USABLE_TYPE_P

> >   - VALID_VAR_TYPE_P

> >   - TYPE_LAID_OUT_P

> >   - TYPE_DEFINED_P

> >   - TYPE_FULLY_DEFINED_P

> >   - TYPE_READY_P

> >   ...other suggestions welcome...

> >

> > I went for DEFINITE_TYPE_P because that's what the SVE specification

> > uses, but something more neutral like TYPE_DEFINED_P might be better.

> >

> > Frontend changes

> > ----------------

> >

> > The frontend patches change COMPLETE_TYPE_P to DEFINITE_TYPE_P where

> > necessary.  I've tried where possible to accompany each individual

> > change with a test.

> >

> > This worked fairly naturally (IMO) for C, and most of the changes could

> > be tied directly to the language edits above.

> >

> > For C++ it was more difficult (not surprisingly).  There are a lot of

> > tests for COMPLETE_TYPE_P that are obviously testing whether a class

> > has been fully defined, and are more concerned with name lookup than

> > TYPE_SIZE.  The same goes for COMPLETE_OR_OPEN_TYPE_P and whether the

> > definition has been started.  So while the C changes were relatively

> > small and self-contained, the C++ changes replace many more uses of

> > COMPLETE_TYPE_P than they keep.  This makes me wonder whether it's a

> > good idea to keep COMPLETE_TYPE_P at all, or whether it would be better

> > to replace the remaining uses with something more explicit like:

> >

> >   TYPE_SIZE_KNOWN_P

> >   TYPE_SIZE_DEFINED_P

> >   TYPE_SIZE_MEASURABLE_P

> >   TYPE_SIZE_COMPLETE_P

> >   ...suggestions again welcome...

> >

> > Thanks,

> > Richard
Richard Sandiford Oct. 16, 2018, 10:22 a.m. | #4
Hi Martin,

Thanks for the reply.

"Uecker, Martin" <Martin.Uecker@med.uni-goettingen.de> writes:
> Hi Richard,

>

> as Joseph pointed out, there are some related discussions

> on the WG14 reflector. How a about moving the discussion

> there?


The idea was to get a feel for what would be acceptable to GCC
maintainers.  When Arm presented an extension of P0214 to support SVE
at the last C++ committee meeting, using this sizeless type extension
as a possible way of providing the underlying vector types, the feeling
seemed to be that it wouldn't be considered unless it had already been
proven in compilers.

> I find your approach very interesting and that it already

> comes with an implementation is of course very useful

>

> But I don't really understand the reasons why this is not based

> on (2). These types are not "sizeless" at all, their size

> just isn't known at compile time. So to me this seems to me

> a misnomer.

>

> In fact, to me these types *do* in fact seem very similar

> to VLAs as VLAs are also complete types which also do no

> have a known size at compile time.

>

> That arrays decay to pointers doesn't mean that we

> couldn't have similar vectors types which don't decay.

> This is hardly a fundamental problem.


I think it is for some poople though.  If the vectors don't decay to
pointers, they're moe akin to a VLA wrapped in a structure rather than
a stand-alone VLA.  There is a GNU extension for that, e.g.:

  int
  f (int n)
  {
    struct s {
      int x[n];
    } foo;
    return sizeof (foo.x);
  }

But even though clang supports VLAs (of course), it rejects the
above with:

  error: fields must have a constant size: 'variable length array in structure' extension will never be supported

This gives a strong impression that wrapping a VLA type like this
is a bridge too far for some :-)  The message makes it clear that's
a case of "don't even bother asking".

The vector tuple types would be very similar to this if modelled as VLAs.

> I also don't understand the problem about the array

> size. If I understand this correctly, the size is somehow

> known at run-time and implicitly passed along with the

> values. So these new types do not need to have a

> size expression (as in your proposal). 


The problem isn't so much that the size is only known at runtime,
but that the size isn't necessarily invariant, and the size of an
object doesn't carry the size information with it.

This means you can't tell what size a given object is, even at runtime.
All you can tell is what size the object would be if you created it
from scratch.  E.g.:

  svint8_t *ptr;  // pointer to variable-length vector type

  void thread1 (void)
  {
    svint8_t local;
    *ptr = &local;
    ...run for a long time...
  }

  void thread2 (void)
  {
    ... sizeof (*ptr); ...;
  }

If thread1 and thread2 have different vector lengths, thread2 has no way
of knowing what size *ptr is.

Of course, thread2 can't validly use *ptr if it has wider vectors than
thread1, but if we resort to saying "undefined behavior" for the above,
then it becomes difficult to define when the size actually is defined.
It's simpler not to make it measurable via sizeof at all.  (And that's
a much less invasive change to the language.)

> Assignment, the possibility to return the type from

> functions, and something like __sizeless_structs would

> make sense for VLAs too.

>

> So creating a new category "variable-length types" for 

> both VLAs and variably-length vector types seems do make

> much more sense to me. As I see it, this would be mainly

> a change in terminology and not so much of the underlying

> approach.


But do you have any feel for whether this would ever be acceptable
in C++?  One of the main requirements for this was that it needs
to work in both C and C++, with the same ABI representation.
I thought VLAs were added to an early draft of C++14 and then
removed before it was published.  They weren't added back for C++17,
and I'd seen other proposals about classes having a "sizeof field"
instead (i.e. the type would carry the size information with it,
which we don't want).  So the prospects didn't look good.

Thanks,
Richard
Joseph Myers Oct. 16, 2018, 9:44 p.m. | #5
On Tue, 16 Oct 2018, Richard Sandiford wrote:

> > as Joseph pointed out, there are some related discussions

> > on the WG14 reflector. How a about moving the discussion

> > there?

> 

> The idea was to get a feel for what would be acceptable to GCC

> maintainers.  When Arm presented an extension of P0214 to support SVE

> at the last C++ committee meeting, using this sizeless type extension

> as a possible way of providing the underlying vector types, the feeling

> seemed to be that it wouldn't be considered unless it had already been

> proven in compilers.


But as shown in the related discussions, there are other possible features 
that might also involve non-VLA types whose size is not a compile-time 
constant.  And so it's necessary to work with the people interested in 
those features in order to clarify what the underlying concepts ought to 
look like to support different such features.

> I think it is for some poople though.  If the vectors don't decay to

> pointers, they're moe akin to a VLA wrapped in a structure rather than

> a stand-alone VLA.  There is a GNU extension for that, e.g.:

> 

>   int

>   f (int n)

>   {

>     struct s {

>       int x[n];

>     } foo;

>     return sizeof (foo.x);

>   }

> 

> But even though clang supports VLAs (of course), it rejects the

> above with:

> 

>   error: fields must have a constant size: 'variable length array in structure' extension will never be supported

> 

> This gives a strong impression that wrapping a VLA type like this

> is a bridge too far for some :-)  The message makes it clear that's

> a case of "don't even bother asking".


What are the clang concerns about VLAs in structs that are the reason for 
not supporting them?  How do the sizeless structs with sizeless members in 
your proposal avoid those concerns about the definition of VLAs in 
structs?

> The problem isn't so much that the size is only known at runtime,

> but that the size isn't necessarily invariant, and the size of an

> object doesn't carry the size information with it.

> 

> This means you can't tell what size a given object is, even at runtime.


How then is e.g. passing a pointer to such a struct (containing such 
unknown-size members) to another function supposed to work?  Or is there 
something in your proposed standard text edits that would disallow passing 
such a pointer, or disallow using "->" with it to access members?

> All you can tell is what size the object would be if you created it

> from scratch.  E.g.:

> 

>   svint8_t *ptr;  // pointer to variable-length vector type

> 

>   void thread1 (void)

>   {

>     svint8_t local;

>     *ptr = &local;

>     ...run for a long time...

>   }

> 

>   void thread2 (void)

>   {

>     ... sizeof (*ptr); ...;

>   }

> 

> If thread1 and thread2 have different vector lengths, thread2 has no way

> of knowing what size *ptr is.

> 

> Of course, thread2 can't validly use *ptr if it has wider vectors than

> thread1, but if we resort to saying "undefined behavior" for the above,

> then it becomes difficult to define when the size actually is defined.


What in your standard text edits serves to make that undefined?  
Generally, what in those edits serves to say when conversions involving 
such types, or pointers thereto, or accesses through compatible types in 
different places, are or are not defined?

In standard C, for example, we have for VLAs 6.7.6.2#6, "If the two array 
types are used in a context which requires them to be compatible, it is 
undefined behavior if the two size specifiers evaluate to unequal 
values.".  What is the analogue of this for sizeless types?  Since unlike 
VLAs you're allowing these types, and sizeless structs containing them, to 
be passed by value, assigned, etc., you need something like that to 
determine whether assignment, conditional expression, function argument 
passing, function return, access via a pointer, etc., are valid.

Can these types be used with _Atomic?  I don't see anything to say they 
can't.

Can these types be passed to variadic functions and named in va_arg?  
Again, I don't see anything to say they can't.

Can you have file-scope, and so static-storage-duration, compound literals 
with these types?  You're allowing compound literals with these types, and 
what you have disallowing objects with these types with non-automatic 
storage duration seems to be specific to the case of "an identifier for an 
object".

I don't see any change proposed to 6.2.6.1#2 corresponding to what you say 
elsewhere about discontiguous representations of sizeless structures.

> But do you have any feel for whether this would ever be acceptable

> in C++?  One of the main requirements for this was that it needs

> to work in both C and C++, with the same ABI representation.

> I thought VLAs were added to an early draft of C++14 and then

> removed before it was published.  They weren't added back for C++17,

> and I'd seen other proposals about classes having a "sizeof field"

> instead (i.e. the type would carry the size information with it,

> which we don't want).  So the prospects didn't look good.


What were the C++ concerns with VLAs, and how do the variable-size types 
in this proposal avoid those concerns?

-- 
Joseph S. Myers
joseph@codesourcery.com
Richard Sandiford Oct. 17, 2018, 12:30 p.m. | #6
[ Sorry that there were so many typos in my last reply, will try to do better
  this time... ]

Joseph Myers <joseph@codesourcery.com> writes:
> On Tue, 16 Oct 2018, Richard Sandiford wrote:

>> The patches therefore add a new "__sizeless_struct" keyword to denote

>> structures that are sizeless rather than sized.  Unlike normal

>> structures, these structures can have members of sizeless type in

>> addition to members of sized type.  On the other hand, they have all

>> the same limitations as other sizeless types (described in earlier

>> sections).

>

> I don't see anything here disallowing offsetof on such structures.


I didn't think this needed to be done explicitly since:

	offsetof(type, member-designator)

    which expands to an integer constant expression that has type size_t,
    the value of which is the offset in bytes, to the structure
    member (designated by member-designator), from the beginning of its
    structure (designated by type). The type and member designator shall be
    such that given

        static type t;

    then the expression &(t.member-designator) evaluates to an address
    constant. (If the specified member is a bit-field, the behavior is
    undefined.)

implicitly rejects sizeless types on the basis that "static type t;"
would be invalid.  I think that's the same way that it rejects
incomplete structure types.

But yeah, it looks like I forgot to handle this in GCC. :-(

> On Tue, 16 Oct 2018, Richard Sandiford wrote:

>> > as Joseph pointed out, there are some related discussions

>> > on the WG14 reflector. How a about moving the discussion

>> > there?

>> 

>> The idea was to get a feel for what would be acceptable to GCC

>> maintainers.  When Arm presented an extension of P0214 to support SVE

>> at the last C++ committee meeting, using this sizeless type extension

>> as a possible way of providing the underlying vector types, the feeling

>> seemed to be that it wouldn't be considered unless it had already been

>> proven in compilers.

>

> But as shown in the related discussions, there are other possible features 

> that might also involve non-VLA types whose size is not a compile-time 

> constant.  And so it's necessary to work with the people interested in 

> those features in order to clarify what the underlying concepts ought to 

> look like to support different such features.


Could you give pointers to the specific proposals/papers you mean?

>> I think it is for some people though.  If the vectors don't decay to

>> pointers, they're more akin to a VLA wrapped in a structure rather than

>> a stand-alone VLA.  There is a GNU extension for that, e.g.:

>> 

>>   int

>>   f (int n)

>>   {

>>     struct s {

>>       int x[n];

>>     } foo;

>>     return sizeof (foo.x);

>>   }

>> 

>> But even though clang supports VLAs (of course), it rejects the

>> above with:

>> 

>>   error: fields must have a constant size: 'variable length array in structure' extension will never be supported

>> 

>> This gives a strong impression that wrapping a VLA type like this

>> is a bridge too far for some :-)  The message makes it clear that's

>> a case of "don't even bother asking".

>

> What are the clang concerns about VLAs in structs that are the reason for 

> not supporting them?


The user manual says:

-  clang does not support the gcc extension that allows variable-length
   arrays in structures. This is for a few reasons: one, it is tricky to
   implement, two, the extension is completely undocumented, and three,
   the extension appears to be rarely used. Note that clang *does*
   support flexible array members (arrays with a zero or unspecified
   size at the end of a structure).

So I guess defining it would remove the second objection.

> How do the sizeless structs with sizeless members in your proposal

> avoid those concerns about the definition of VLAs in structs?


The key difference is that the size, offset and layout don't have to be
known to the frontend and available during semantic analysis (unlike for
VLAs in structs).  In the clang implementation of sizeless types those
details only start to matter when translating clang ASTs into LLVM IR.
(With GCC it's a bit different, since TYPE_SIZE is set as soon as the
type definition is complete, even though for SVE TYPE_SIZE should only
matter in the mid and backend.)

>> The problem isn't so much that the size is only known at runtime,

>> but that the size isn't necessarily invariant, and the size of an

>> object doesn't carry the size information with it.

>> 

>> This means you can't tell what size a given object is, even at runtime.

>

> How then is e.g. passing a pointer to such a struct (containing such 

> unknown-size members) to another function supposed to work?  Or is there 

> something in your proposed standard text edits that would disallow passing 

> such a pointer, or disallow using "->" with it to access members?


The idea here...

>> All you can tell is what size the object would be if you created it

>> from scratch.  E.g.:

>> 

>>   svint8_t *ptr;  // pointer to variable-length vector type

>> 

>>   void thread1 (void)

>>   {

>>     svint8_t local;

>>     *ptr = &local;

>>     ...run for a long time...

>>   }

>> 

>>   void thread2 (void)

>>   {

>>     ... sizeof (*ptr); ...;

>>   }

>> 

>> If thread1 and thread2 have different vector lengths, thread2 has no way

>> of knowing what size *ptr is.

>> 

>> Of course, thread2 can't validly use *ptr if it has wider vectors than

>> thread1, but if we resort to saying "undefined behavior" for the above,

>> then it becomes difficult to define when the size actually is defined.

>

> What in your standard text edits serves to make that undefined?  

> Generally, what in those edits serves to say when conversions involving 

> such types, or pointers thereto, or accesses through compatible types in 

> different places, are or are not defined?

>

> In standard C, for example, we have for VLAs 6.7.6.2#6, "If the two array 

> types are used in a context which requires them to be compatible, it is 

> undefined behavior if the two size specifiers evaluate to unequal 

> values.".  What is the analogue of this for sizeless types?  Since unlike 

> VLAs you're allowing these types, and sizeless structs containing them, to 

> be passed by value, assigned, etc., you need something like that to 

> determine whether assignment, conditional expression, function argument 

> passing, function return, access via a pointer, etc., are valid.


...and here is that any size changes come only from changes in the
implementation-defined built-in sizeless types.  The user can't define
a new type whose size varies in new ways.  E.g. the size and layout of:

    __sizeless_struct s1 { svuint32_t v0, v1; };

can only vary because the size of the implementation-defined svuint32_t
can vary.  Something like:

    __sizeless_struct s2 { uint32_t v0, v1; };

would never change size or layout dynamically and the above scenarios
would be valid whenever they would be valid for "struct s2".

Since the built-in types are implementation-defined, the idea was
that the situations in which their size could vary should be
implementation-defined as well.

So passing a pointer to a sizeless struct containing a vector is OK if
nothing causes the vector length to change in the meantime.  The exact
circumstances in which that could happen are implementation-defined.
The same goes for the thread example above: in normal SVE usage it
would be fine for thread2 to use the vector at *ptr, since normally
all threads would run with the same vector length.  But there are some
implementation-defined situations in which the length could be different.

The situations in which the vector length can change for SVE (and thus
the situations in which the above examples would be undefined behaviour)
are very SVE-specific.  It's likely that the rules for any future sizeless
types would also be very specific to those types.  E.g. my understanding
of the proposed RISC-V vector extension is that the vector length would
change much more often than it does for SVE.

> Can these types be used with _Atomic?  I don't see anything to say they 

> can't.


At the moment that's allowed, although of course it probably isn't
useful in practice.

> Can these types be passed to variadic functions and named in va_arg?  

> Again, I don't see anything to say they can't.


Yes, this is allowed (and covered by the tests FWIW).

> Can you have file-scope, and so static-storage-duration, compound literals 

> with these types?  You're allowing compound literals with these types, and 

> what you have disallowing objects with these types with non-automatic 

> storage duration seems to be specific to the case of "an identifier for an 

> object".


Ah, you mean something like:

    typedef __sizeless_struct s { int i; } s;
    s *ptr = &(s) { 1 };

?  Yeah, good point, hadn't thought of that.  That should be invalid too.

> I don't see any change proposed to 6.2.6.1#2 corresponding to what you say 

> elsewhere about discontiguous representations of sizeless structures.


Yeah, good point.  It should be edited to say:

    Except for bit-fields *and sizeless structures*, objects are
    composed of contiguous sequences of one or more bytes, the number,
    order, and encoding of which are either explicitly specified or
    implementation-defined.

TBH the possibility of a discontiguous representation was an early idea
that we've never actually used so far, so if that's a problem, we could
probably drop it.  It just seemed to be a natural extension of the
principle that the layout is completely implementation-defined.

>> But do you have any feel for whether this would ever be acceptable

>> in C++?  One of the main requirements for this was that it needs

>> to work in both C and C++, with the same ABI representation.

>> I thought VLAs were added to an early draft of C++14 and then

>> removed before it was published.  They weren't added back for C++17,

>> and I'd seen other proposals about classes having a "sizeof field"

>> instead (i.e. the type would carry the size information with it,

>> which we don't want).  So the prospects didn't look good.

>

> What were the C++ concerns with VLAs,


The sizeless type proposal was drawn up while SVE was still
confidential, so it wasn't something we could openly talk about.
At the time it wasn't obvious from the online trail why VLAs
(well, ARBs) were removed.  The proposal was:

   http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3639.html

which says that it "was approved by EWG during the Portland meeting of
WG21 and was updated to reflect CWG review".  At the time we were doing
the sizeless type proposal, we were in pretty much the same situation
as this reddit poster:

    https://www.reddit.com/r/cpp_questions/comments/3clm34/why_was_n3639_runtimesized_arrays_with_automatic/

in that all we could find was a statement of its removal, with no
explanation of the reasons.

I see now there's a stackoverflow answer with some of the history
(this postdates the original sizeless type work):

    https://stackoverflow.com/questions/40633344/variable-length-arrays-in-c14

It ends with:

    Sadly [...] there are no future plans to resurrect ARBs/VLAs with
    C++ in the simple c99 VLA form.

> and how do the variable-size types in this proposal avoid those concerns?


I think the key difference between sizeless types and ARBs is that
ARBs were intended to provide user-controlled sources of variability.
That would only be useful if having variable-length arrays as part of
the core language rather than the library is useful.  Here we're simply
providing canned built-in types with a fixed source of variability,
with that variability not being modelled in the language at all.
Users can combine those canned types together but they can't create
new sources of variability.  The sizeless type proposal is mostly just
a means to an end: a core language change that allows new library
extensions to be defined for targets like SVE.

I think the key difference between sizeless types and full C99-style
VLAs is that the size and layout of sizeless types never matters for
semantic analysis.  Rather than the sizes of types becoming variable
(and the offsets of members becoming variable, and constexprs becoming
variable-sized, etc.), we simply don't make those concepts available
for sizeless types.

So nothing at the language level becomes variable that was constant before.
All that happens is that some things become invalid for sizeless types
that would be valid for sized ones.

The idea was really for the language to provide a framework for
implementations to define implementation-specific types with
implementation-specific rules while disturbing the language itself
as little as possible.

Thanks,
Richard
Uecker, Martin Oct. 17, 2018, 12:47 p.m. | #7
Am Mittwoch, den 17.10.2018, 13:30 +0100 schrieb Richard Sandiford:
> [ Sorry that there were so many typos in my last reply, will try to

> do better

>   this time... ]


...
> I think the key difference between sizeless types and full C99-style

> VLAs is that the size and layout of sizeless types never matters for

> semantic analysis.  Rather than the sizes of types becoming variable

> (and the offsets of members becoming variable, and constexprs

> becoming

> variable-sized, etc.), we simply don't make those concepts available

> for sizeless types.

> 

> So nothing at the language level becomes variable that was constant

> before.

> All that happens is that some things become invalid for sizeless

> types

> that would be valid for sized ones.

> 

> The idea was really for the language to provide a framework for

> implementations to define implementation-specific types with

> implementation-specific rules while disturbing the language itself

> as little as possible.


I guess this makes it much easier for C++, but also much less useful.
Surely, the processor knows the size when it computes using these
types, so one could make it available using 'sizeof'. If a value
of the type is stores in addressable memory (on the stack), can't
we also store the size so that it is available for other threads? 
Just making it undefined to access a variable with the wong size
for the current thread seems rather fragile to me. 

Best,
Martin
Joseph Myers Oct. 17, 2018, 12:54 p.m. | #8
On Wed, 17 Oct 2018, Richard Sandiford wrote:

> > But as shown in the related discussions, there are other possible features 

> > that might also involve non-VLA types whose size is not a compile-time 

> > constant.  And so it's necessary to work with the people interested in 

> > those features in order to clarify what the underlying concepts ought to 

> > look like to support different such features.

> 

> Could you give pointers to the specific proposals/papers you mean?


They're generally reflector discussions rather than written up as papers, 
exploring the space of problems and solutions in various areas (including 
bignums and runtime introspection of types).  I think the first message in 
those discussions is number 15529 
<http://www.open-std.org/jtc1/sc22/wg14/15529> and then relevant 
discussions continue for much of the next 200 messages or so.

> ...and here is that any size changes come only from changes in the

> implementation-defined built-in sizeless types.  The user can't define


But then I think you still need to define in the standard edits something 
of what the type-compatibility rules are.

> > Can these types be passed to variadic functions and named in va_arg?  

> > Again, I don't see anything to say they can't.

> 

> Yes, this is allowed (and covered by the tests FWIW).


How does that work with not knowing the size even at runtime?

At least, this seems like another place where there would be special type 
compatibility considerations that need to be applied between caller and 
callee.

>     Except for bit-fields *and sizeless structures*, objects are

>     composed of contiguous sequences of one or more bytes, the number,

>     order, and encoding of which are either explicitly specified or

>     implementation-defined.

> 

> TBH the possibility of a discontiguous representation was an early idea

> that we've never actually used so far, so if that's a problem, we could

> probably drop it.  It just seemed to be a natural extension of the

> principle that the layout is completely implementation-defined.


If you have discontiguous representations, I don't see how "->" on 
structure pointers (or indeed unary "*") is supposed to work; disallowing 
discontiguous representations would seem to fit a lot more naturally with 
the C object model.

-- 
Joseph S. Myers
joseph@codesourcery.com
Richard Sandiford Oct. 17, 2018, 2:23 p.m. | #9
"Uecker, Martin" <Martin.Uecker@med.uni-goettingen.de> writes:
> Am Mittwoch, den 17.10.2018, 13:30 +0100 schrieb Richard Sandiford:

>> [ Sorry that there were so many typos in my last reply, will try to

>> do better

>>   this time... ]

>

> ...

>> I think the key difference between sizeless types and full C99-style

>> VLAs is that the size and layout of sizeless types never matters for

>> semantic analysis.  Rather than the sizes of types becoming variable

>> (and the offsets of members becoming variable, and constexprs

>> becoming

>> variable-sized, etc.), we simply don't make those concepts available

>> for sizeless types.

>> 

>> So nothing at the language level becomes variable that was constant

>> before.

>> All that happens is that some things become invalid for sizeless

>> types

>> that would be valid for sized ones.

>> 


>> The idea was really for the language to provide a framework for

>> implementations to define implementation-specific types with

>> implementation-specific rules while disturbing the language itself

>> as little as possible.

>

> I guess this makes it much easier for C++, but also much less useful.


Yeah, can't deny that if you look at it as a general-purpose extension.
But that's not really what this is supposed to be.  It's fairly special
purpose: there has to be some underlying variable-length/sizeless
built-in type that you want to provide via a library.

What the extension allows is enough to support the intended use case,
and it does that with no enforced overhead.

The examples with one thread accessing a vector from a different thread
aren't interesting in practice; any sharing or caching should happen via
normal arrays or malloced memory instead.  These corner cases are just
something that needs to be addressed once you allow pointers to things.

> Surely, the processor knows the size when it computes using these

> types, so one could make it available using 'sizeof'.


The argument's similar here: we don't really need sizeof to be available
for vector use because the library provides easy ways of getting
vector-length-based constants.  Usually what you want to know is
"how many elements of type X are there?", with bytes just being one
of the available element sizes.

And of course, making sizeof variable would be a can of worms in C++...
(The rejected ARB proposal didn't try to do that.)

> If a value of the type is stores in addressable memory (on the stack),

> can't we also store the size so that it is available for other threads? 


But the problem is that once the size becomes a part of the object,
it becomes difficult to get rid of it again for the intended use case.
E.g. say a vector is passed on the stack due to running out of registers.
Does the caller provide both the size and the contents, or just the
contents?  In the latter case it would be the callee's reponsibility
to "fill in" the missing size, but at what point should it compute the
size?  In the former case, would a callee-copies ABI require the callee
to copy the contents with the size given in the argument or the value
that the callee would use if it were creating an object from scratch?

These aren't insurmountable problems.  They just seem like an unnecessary
complication when the only reason for doing them is to support sizeof,
which isn't something that the use case needs.

Also, storing the size with the object would make the size field
*become* part of the size of the object, so sizeof (vector) would give
you something bigger than the size of the vector itself.  It would also
open up oddities like:

  sizeof (x) != sizeof (typeof (x))

being false in some cases.  I.e. even if sizeof (x) correctly reported
the size that an object x actually has, it isn't necessarily the size
that a new object of that type would have, so users would have to be
very careful about what they ask.  I think both these things would just
open the door to more confusion.

> Just making it undefined to access a variable with the wong size for the

> current thread seems rather fragile to me.


In many ways it seems similar to memory management.  It's the
programmer's responsibility to ensure that they don't access vectors
with the "wrong" size in the same way that it's their responsibility
not to dereference freed memory or access beyond the amount of memory
allocated.

And as I mentioned above, noone should be doing that anyway :-)
These types shouldn't live longer than a vector loop, with that loop
potentially calling functions that are easily identified as "vector
functions".

Thanks,
Richard
Joseph Myers Oct. 17, 2018, 2:35 p.m. | #10
On Wed, 17 Oct 2018, Richard Sandiford wrote:

> Yeah, can't deny that if you look at it as a general-purpose extension.

> But that's not really what this is supposed to be.  It's fairly special

> purpose: there has to be some underlying variable-length/sizeless

> built-in type that you want to provide via a library.

> 

> What the extension allows is enough to support the intended use case,

> and it does that with no enforced overhead.


Part of my point is that there are various *other* possible cases of 
non-VLA-variable-size-type people have suggested in WG14 reflector 
discussions - so any set of concepts for such types ought to take into 
account more than just the SVE use case (even if other use cases need 
further concepts added on top of the ones needed for SVE).

> > Surely, the processor knows the size when it computes using these

> > types, so one could make it available using 'sizeof'.

> 

> The argument's similar here: we don't really need sizeof to be available

> for vector use because the library provides easy ways of getting

> vector-length-based constants.  Usually what you want to know is

> "how many elements of type X are there?", with bytes just being one

> of the available element sizes.


But if having sizeof available makes for a more natural language feature 
(one where a few places referencing VLAs need to change to reference a 
more general class of variable-size types, and a few constraints on VLAs 
and variably modified types need to be relaxed to allow what you want with 
these types), that may be a case for doing so, even if sizeof won't 
generally be used.

If the processor in fact knows the size, do you actually need to include 
it in the object to be able to provide it when sizeof is called?  (With 
undefined behavior still present if passing the object from a thread with 
one value of sizeof for that type to a thread with a different value of 
sizeof for that type, of course - the rule on VLA type compatibility would 
still need to be extended to apply to sizes of these types, and those they 
contain, recursively.)

-- 
Joseph S. Myers
joseph@codesourcery.com
Richard Sandiford Oct. 18, 2018, 11:27 a.m. | #11
Joseph Myers <joseph@codesourcery.com> writes:
> On Wed, 17 Oct 2018, Richard Sandiford wrote:

>

>> > But as shown in the related discussions, there are other possible features 

>> > that might also involve non-VLA types whose size is not a compile-time 

>> > constant.  And so it's necessary to work with the people interested in 

>> > those features in order to clarify what the underlying concepts ought to 

>> > look like to support different such features.

>> 

>> Could you give pointers to the specific proposals/papers you mean?

>

> They're generally reflector discussions rather than written up as papers, 

> exploring the space of problems and solutions in various areas (including 

> bignums and runtime introspection of types).  I think the first message in 

> those discussions is number 15529 

> <http://www.open-std.org/jtc1/sc22/wg14/15529> and then relevant 

> discussions continue for much of the next 200 messages or so.


OK, thanks.  I've read from there to the latest message at the time
of writing (15720).  There seemed to be various ideas:

- a new int128_t, which started the discussion off.

- support for parameterised fixed-size integers like _Int(40), which
  seemed to be a C version of C++ template<int> and wouldn't need
  variable-length types.

- bignums that extend as necessary.  On that I agree with what you said in:

    <http://www.open-std.org/jtc1/sc22/wg14/15572>
    A bignum type, in the sense of one that grows its storage if you
    store a too-big number in it (as opposed to fixed-width int<N> where
    you can specify an arbitrary integer constant expression for N),
    cannot meet other requirements for C integer types such as being
    directly represented in binary - it has to, effectively, be a fixed
    size but contain a pointer to allocated storage (and then there are
    considerations of how such a type should handle errors for
    allocation failure).

  and Hans Boehm said in:

    <http://www.open-std.org/jtc1/sc22/wg14/15573>
    2) Provide an integral type that is reasonably efficient for small
    integers, but gracefully overflows to something along the lines of
    (1). A common way to do that in other languages is to represent
    e.g. 63-bit integers directly by adding a zero bit on the right.
    On overflow a more complex result is represented by e.g. a 64-bit
    aligned pointer with the low bit set to one. That way integer
    addition is just an add instruction followed by an overflow check in
    the normal case. Probably a better way to do integer arithmetic in
    many, maybe even most, cases. Especially since such integers need to
    be usable as array elements, I don't see how to avoid memory
    allocation under the covers, along the slow path.

  This IIRC is how LLVM's APInt is implemented.  It doesn't need
  variable-length types, and although it would need some kind of
  memory management support for C, it doesn't need any language
  changes at all for C++.

  It's also similar to what GCC does with auto_vec<T, N> and LLVM does
  with SmallVector: the types have embedded room for common cases and
  fall back to separately-allocated storage if the contents get too big.

  There was talk about having it as a true variable-length type in:

    <http://www.open-std.org/jtc1/sc22/wg14/15577>
    (2) is difficult because of the requirements for memory management and
    the necessity to deal with allocation failures.

    For avoiding integer overflow vulnerabilities, there is a variant of (2)
    which is not possible to implement in a library, where expressions are
    evaluated with a sufficient number of bits to obtain the mathematically
    correct result.  GNAT has implemented something in this direction
    (MINIMIZED and ELIMINATED):

    <https://gcc.gnu.org/onlinedocs/gnat_ugn/Management-of-Overflows-in-GNAT.html#Management-of-Overflows-in-GNAT>

    I think that for expressions which do not involve shifts by
    non-constants, it should be possible to determine the required storage
    at compile time, so it would avoid the memory allocation issue.  Unlike
    Ada, C doesn't have a power operator, so the storage requirements would
    grow with the size of the expression (still under the assumption that
    left shifts are excluded).

  But AIUI that was intended to be more special purpose, for
  intermediate results while evaluating an expression.  It solves
  the memory allocation issue because the (stack) memory used for
  evaluating the expression could be recovered after evaluation is
  complete.

  This approach wouldn't work if it was extended to an assignable bignum
  object type.  E.g. prohibiting left shifts wouldn't then help since:

     bignum x = ...;
     x <<= var; // invalid

  would be equivalent to:

     bignum x = ...;
     for (int i = 0; i < var; ++i)
       x += x; // valid

  Thus it would be easy to create what are effectively allocas of O(1<<var)
  bytes for some variable var.  And if the memory was always allocated on
  the stack, it would be hard to recover memory from discarded objects
  until the function returns.

  Hans went on to say:  

    I personally think that, especially in light of various integer overflow
    vulnerabilities, (2) would be really nice to have.

    I unfortunately haven't had time to follow the WG21 bignum discussion on
    this very closely. But my impression is that they're aiming to enable (2).

  So it sounds like bignums are being solved on the C++ side at least
  without having to add true variable-length types.

  FWIW, this corresponds to (3b) in the RFC, where a fixed-size type
  refers to separate storage where necessary.

- Type introspection for things like parsing format strings

  It sounded like the type descriptors would be fixed-sized types,
  a bit like a C version of std::type_info.

So I didn't see anything there that was really related, or anything that
relied on sizeof being variable (which as I say seems to be a very high
hurdle for C++).

Also, I thought opinion was turning/had turned against using what are
effectively unbounded allocas, so it would seem strange to spend a lot
of effort providing a more convenient wrapper for them.  (The SVE use
isn't unbounded because all sizeless objects are a X*VL+Y for constant
X and Y and bounded VL.)

>> ...and here is that any size changes come only from changes in the

>> implementation-defined built-in sizeless types.  The user can't define

>

> But then I think you still need to define in the standard edits something 

> of what the type-compatibility rules are.


I think it would look something like this (referring back to

    *Object types are further partitioned into sized and
    sizeless; all basic and derived types defined in this standard are
    sized, but an implementation may provide additional sizeless types.*

in the RFC), not really in standardese yet:

    Each implementation-specific sizeless type may have a set of
    implementation-specific "configurations".  The configuration of
    such a type may change in implementation-defined ways at any given
    sequence point.

    The configuration of a sizeless structure is a tuple containing the
    configuration of each member.  Thus the configuration of a sizeless
    structure changes if and only if the configuration of one of its
    members changes.

    The configuration of an object of sizeless type T is the configuration
    of T at the point that the object is created.

And then borrowing slightly from your 6.7.6.2#6 reference:

    If an object of sizeless type T is accessed when T has a different
    configuration from the object, the behavior is undefined.

Is that the kind of thing you mean?

>> > Can these types be passed to variadic functions and named in va_arg?  

>> > Again, I don't see anything to say they can't.

>> 

>> Yes, this is allowed (and covered by the tests FWIW).

>

> How does that work with not knowing the size even at runtime?

>

> At least, this seems like another place where there would be special type 

> compatibility considerations that need to be applied between caller and 

> callee.


Yeah, it requires the caller and callee to agree on what the type
represents (in SVE terms, to have the same vector length).

>>     Except for bit-fields *and sizeless structures*, objects are

>>     composed of contiguous sequences of one or more bytes, the number,

>>     order, and encoding of which are either explicitly specified or

>>     implementation-defined.

>> 

>> TBH the possibility of a discontiguous representation was an early idea

>> that we've never actually used so far, so if that's a problem, we could

>> probably drop it.  It just seemed to be a natural extension of the

>> principle that the layout is completely implementation-defined.

>

> If you have discontiguous representations, I don't see how "->" on 

> structure pointers (or indeed unary "*") is supposed to work;


The idea was that there would be some indirection under the covers
where necessary.  E.g. the data pointed to the pointer may have a
hidden field that gives the offset or pointer to other storage.

The specific reason for thinking that might be useful was that it would
allow the compiler to divide a frame into "VL data" and "constant-sized
data".  A sizeless structure could be in one but refer to data in the
other.  But as I say, we never actually used that.

> disallowing discontiguous representations would seem to fit a lot more

> naturally with the C object model.


OK, I'll take out the discontiguous part.

Thanks,
Richard
Richard Sandiford Oct. 18, 2018, 12:47 p.m. | #12
Joseph Myers <joseph@codesourcery.com> writes:
> On Wed, 17 Oct 2018, Richard Sandiford wrote:

>> Yeah, can't deny that if you look at it as a general-purpose extension.

>> But that's not really what this is supposed to be.  It's fairly special

>> purpose: there has to be some underlying variable-length/sizeless

>> built-in type that you want to provide via a library.

>> 

>> What the extension allows is enough to support the intended use case,

>> and it does that with no enforced overhead.

>

> Part of my point is that there are various *other* possible cases of 

> non-VLA-variable-size-type people have suggested in WG14 reflector 

> discussions - so any set of concepts for such types ought to take into 

> account more than just the SVE use case (even if other use cases need 

> further concepts added on top of the ones needed for SVE).


[Answered this in the other thread -- sorry, took me a while to go
through the full discussion.]

>> > Surely, the processor knows the size when it computes using these

>> > types, so one could make it available using 'sizeof'.

>> 

>> The argument's similar here: we don't really need sizeof to be available

>> for vector use because the library provides easy ways of getting

>> vector-length-based constants.  Usually what you want to know is

>> "how many elements of type X are there?", with bytes just being one

>> of the available element sizes.

>

> But if having sizeof available makes for a more natural language feature 

> (one where a few places referencing VLAs need to change to reference a 

> more general class of variable-size types, and a few constraints on VLAs 

> and variably modified types need to be relaxed to allow what you want with 

> these types), that may be a case for doing so, even if sizeof won't 

> generally be used.


I agree that might be all that's needed in C.  But since C++ doesn't
even have VLAs yet (and since something less ambituous than VLAs was
rejected) the situation is very different there.

I think we'd need a compelling reason to make sizeof variable in C++.
The fact that it isn't going to be generally used for SVE anyway
would undercut that.

> If the processor in fact knows the size, do you actually need to include 

> it in the object to be able to provide it when sizeof is called?  (With 

> undefined behavior still present if passing the object from a thread with 

> one value of sizeof for that type to a thread with a different value of 

> sizeof for that type, of course - the rule on VLA type compatibility would 

> still need to be extended to apply to sizes of these types, and those they 

> contain, recursively.)


No, if we go the undefined behaviour route, we wouldn't need to store it.
This was just to answer Martin's suggestion that we could make sizeof(x)
do the right thing for a sizeless object x by storing the size with x.

Thanks,
Richard
Uecker, Martin Oct. 18, 2018, 7:32 p.m. | #13
Hi Richard,

responding here to a couple of points.

For bignums and for a type-descibing type 'type'
there were proposals (including from me) to implement
these as variable-sized types which have some restrictions,
i.e. they cannot be stored in a struct/union.

Most of the restrictions for these types would be the same
as proposed for your sizeless types. 

Because all these types fall into the same overall class
of types which do not have a size known at compile
time, I would suggest to add this concept to the standard
and then define your vector types as a subclass which
may have additional restrictions (no sizeof) instead
of adding a very specific concept which only works for
your proposal.

Best,
Martin





Am Donnerstag, den 18.10.2018, 13:47 +0100 schrieb Richard Sandiford:
> Joseph Myers <joseph@codesourcery.com> writes:

> > On Wed, 17 Oct 2018, Richard Sandiford wrote:

> > > Yeah, can't deny that if you look at it as a general-purpose extension.

> > > But that's not really what this is supposed to be.  It's fairly special

> > > purpose: there has to be some underlying variable-length/sizeless

> > > built-in type that you want to provide via a library.

> > > 

> > > What the extension allows is enough to support the intended use case,

> > > and it does that with no enforced overhead.

> > 

> > Part of my point is that there are various *other* possible cases of 

> > non-VLA-variable-size-type people have suggested in WG14 reflector 

> > discussions - so any set of concepts for such types ought to take into 

> > account more than just the SVE use case (even if other use cases need 

> > further concepts added on top of the ones needed for SVE).

> 

> [Answered this in the other thread -- sorry, took me a while to go

> through the full discussion.]

> 

> > > > Surely, the processor knows the size when it computes using these

> > > > types, so one could make it available using 'sizeof'.

> > > 

> > > The argument's similar here: we don't really need sizeof to be available

> > > for vector use because the library provides easy ways of getting

> > > vector-length-based constants.  Usually what you want to know is

> > > "how many elements of type X are there?", with bytes just being one

> > > of the available element sizes.

> > 

> > But if having sizeof available makes for a more natural language feature 

> > (one where a few places referencing VLAs need to change to reference a 

> > more general class of variable-size types, and a few constraints on VLAs 

> > and variably modified types need to be relaxed to allow what you want with 

> > these types), that may be a case for doing so, even if sizeof won't 

> > generally be used.

> 

> I agree that might be all that's needed in C.  But since C++ doesn't

> even have VLAs yet (and since something less ambituous than VLAs was

> rejected) the situation is very different there.

> 

> I think we'd need a compelling reason to make sizeof variable in C++.

> The fact that it isn't going to be generally used for SVE anyway

> would undercut that.

> 

> > If the processor in fact knows the size, do you actually need to include 

> > it in the object to be able to provide it when sizeof is called?  (With 

> > undefined behavior still present if passing the object from a thread with 

> > one value of sizeof for that type to a thread with a different value of 

> > sizeof for that type, of course - the rule on VLA type compatibility would 

> > still need to be extended to apply to sizes of these types, and those they 

> > contain, recursively.)

> 

> No, if we go the undefined behaviour route, we wouldn't need to store it.

> This was just to answer Martin's suggestion that we could make sizeof(x)

> do the right thing for a sizeless object x by storing the size with x.

> 

> Thanks,

> Richard
Richard Sandiford Oct. 18, 2018, 7:53 p.m. | #14
"Uecker, Martin" <Martin.Uecker@med.uni-goettingen.de> writes:
> Hi Richard,

>

> responding here to a couple of points.

>

> For bignums and for a type-descibing type 'type'

> there were proposals (including from me) to implement

> these as variable-sized types which have some restrictions,

> i.e. they cannot be stored in a struct/union.


But do you mean variable-sized types in the sense that they
are completely self-contained and don't refer to separate storage?
I.e. the moral equivalent of:

  1: struct { int size; int contents[size]; };

rather than either:

  2: struct { int size; int *contents; };

or:

  3: union {
       // embedded storage up to N bits (N constant)
       // description of separately-allocated storage (for >N bits)
     };
    
?  If so, how would that work with the example I gave in the earlier
message:

    bignum x = ...;
    for (int i = 0; i < var; ++i)
      x += x;

Each time the addition result grows beyond the original size of x,
I assume you'd need to allocate a new stack bignum for the new size,
which would result in a series of ever-increasing allocas.  Won't that
soon blow the stack?

Option 3 (as for LLVM's APInt) seems far less surprising, and can
be made efficient for a chosen N.  What makes it difficult for C
isn't the lack of general variable-length types but the lack of
user-defined contructor, destructor, copy and move operations.

Thanks,
Richard

> Most of the restrictions for these types would be the same

> as proposed for your sizeless types. 

>

> Because all these types fall into the same overall class

> of types which do not have a size known at compile

> time, I would suggest to add this concept to the standard

> and then define your vector types as a subclass which

> may have additional restrictions (no sizeof) instead

> of adding a very specific concept which only works for

> your proposal.

>

> Best,

> Martin

>

>

>

>

>

> Am Donnerstag, den 18.10.2018, 13:47 +0100 schrieb Richard Sandiford:

>> Joseph Myers <joseph@codesourcery.com> writes:

>> > On Wed, 17 Oct 2018, Richard Sandiford wrote:

>> > > Yeah, can't deny that if you look at it as a general-purpose extension.

>> > > But that's not really what this is supposed to be.  It's fairly special

>> > > purpose: there has to be some underlying variable-length/sizeless

>> > > built-in type that you want to provide via a library.

>> > > 

>> > > What the extension allows is enough to support the intended use case,

>> > > and it does that with no enforced overhead.

>> > 

>> > Part of my point is that there are various *other* possible cases of 

>> > non-VLA-variable-size-type people have suggested in WG14 reflector 

>> > discussions - so any set of concepts for such types ought to take into 

>> > account more than just the SVE use case (even if other use cases need 

>> > further concepts added on top of the ones needed for SVE).

>> 

>> [Answered this in the other thread -- sorry, took me a while to go

>> through the full discussion.]

>> 

>> > > > Surely, the processor knows the size when it computes using these

>> > > > types, so one could make it available using 'sizeof'.

>> > > 

>> > > The argument's similar here: we don't really need sizeof to be available

>> > > for vector use because the library provides easy ways of getting

>> > > vector-length-based constants.  Usually what you want to know is

>> > > "how many elements of type X are there?", with bytes just being one

>> > > of the available element sizes.

>> > 

>> > But if having sizeof available makes for a more natural language feature 

>> > (one where a few places referencing VLAs need to change to reference a 

>> > more general class of variable-size types, and a few constraints on VLAs 

>> > and variably modified types need to be relaxed to allow what you want with 

>> > these types), that may be a case for doing so, even if sizeof won't 

>> > generally be used.

>> 

>> I agree that might be all that's needed in C.  But since C++ doesn't

>> even have VLAs yet (and since something less ambituous than VLAs was

>> rejected) the situation is very different there.

>> 

>> I think we'd need a compelling reason to make sizeof variable in C++.

>> The fact that it isn't going to be generally used for SVE anyway

>> would undercut that.

>> 

>> > If the processor in fact knows the size, do you actually need to include 

>> > it in the object to be able to provide it when sizeof is called?  (With 

>> > undefined behavior still present if passing the object from a thread with 

>> > one value of sizeof for that type to a thread with a different value of 

>> > sizeof for that type, of course - the rule on VLA type compatibility would 

>> > still need to be extended to apply to sizes of these types, and those they 

>> > contain, recursively.)

>> 

>> No, if we go the undefined behaviour route, we wouldn't need to store it.

>> This was just to answer Martin's suggestion that we could make sizeof(x)

>> do the right thing for a sizeless object x by storing the size with x.

>> 

>> Thanks,

>> Richard
Joseph Myers Oct. 18, 2018, 8:07 p.m. | #15
On Thu, 18 Oct 2018, Richard Sandiford wrote:

> - Type introspection for things like parsing format strings

> 

>   It sounded like the type descriptors would be fixed-sized types,

>   a bit like a C version of std::type_info.


It wasn't clear if people might also want to e.g. extract a list of all 
members of a structure type from such an object (which of course could 
either involve variable-sized data, or fixed-size data pointing to arrays, 
or something else along those lines).

> So I didn't see anything there that was really related, or anything that

> relied on sizeof being variable (which as I say seems to be a very high

> hurdle for C++).


The references you gave regarding the removal of one version of VLAs from 
C++ didn't seem to make clear whether there were supposed to be general 
issues with variable-size types fitting in the overall C++ object model, 
or whether the concerns were more specific to things in the particular 
proposal - but in either case, the SVE proposals would need to be compared 
to the actual specific concerns.

Anyway, the correct model in C++ need not be the same as the correct model 
in C.  For example, for decimal floating point, C++ chose a class-based 
model whereas C chose _Decimal* keywords (and then there's some compiler 
magic to use appropriate ABIs for std::decimal types, I think).

If you were implementing the SVE API for C++ for non-SVE hardware, you 
might have a class-based implementation where the class internally 
contains a pointer to underlying storage and does allocation / 
deallocation, for example - sizeof would give some fixed small size to the 
objects with that class type, but e.g. copying them with memcpy would not 
work correctly (and would be diagnosed with -Wclass-memaccess).  Is there 
something wrong with a model in C++ where these types have some fixed 
small sizeof (which carries through to sizeof for containing types), but 
where different ABIs are used for them, and where much the same raw memory 
operations on them are disallowed as would be disallowed for a class-based 
implementation?  (Whether implemented entirely in the compiler or through 
some combination of the compiler and class implementations in a header - 
though with the latter you might still need some new language feature, 
albeit only for use within the header rather than more generally.)

Even if that model doesn't work for some reason, it doesn't mean the only 
alternatives for C++ are something like VLAs or a new concept of sizeless 
types for C++ - but I don't have the C++ expertise to judge what other 
options for interfacing to SVE might fit best into the C++ language.

> I think it would look something like this (referring back to

> 

>     *Object types are further partitioned into sized and

>     sizeless; all basic and derived types defined in this standard are

>     sized, but an implementation may provide additional sizeless types.*

> 

> in the RFC), not really in standardese yet:

> 

>     Each implementation-specific sizeless type may have a set of

>     implementation-specific "configurations".  The configuration of

>     such a type may change in implementation-defined ways at any given

>     sequence point.

> 

>     The configuration of a sizeless structure is a tuple containing the

>     configuration of each member.  Thus the configuration of a sizeless

>     structure changes if and only if the configuration of one of its

>     members changes.

> 

>     The configuration of an object of sizeless type T is the configuration

>     of T at the point that the object is created.

> 

> And then borrowing slightly from your 6.7.6.2#6 reference:

> 

>     If an object of sizeless type T is accessed when T has a different

>     configuration from the object, the behavior is undefined.

> 

> Is that the kind of thing you mean?


Yes.  But I wonder if it would be better to disallow such changing of 
configurations, so that all code in a program always uses the same 
configuration as far as the standard is concerned, so that there is indeed 
a size for a given vector type that's constant throughout the execution of 
a program (which would be used by calls to sizeof on such types), and so 
that communicating with a thread using a different configuration is just 
as much outside the scope of the defined language as processes using 
different ABIs communicating is today.

-- 
Joseph S. Myers
joseph@codesourcery.com
Joseph Myers Oct. 18, 2018, 8:20 p.m. | #16
On Thu, 18 Oct 2018, Uecker, Martin wrote:

> Most of the restrictions for these types would be the same

> as proposed for your sizeless types. 

> 

> Because all these types fall into the same overall class

> of types which do not have a size known at compile

> time, I would suggest to add this concept to the standard

> and then define your vector types as a subclass which

> may have additional restrictions (no sizeof) instead

> of adding a very specific concept which only works for

> your proposal.


And an underlying point here is:

Various people are exploring various ideas for C language and library 
features that might involve extending the kinds of types present in C.  
Maybe some of the ideas will turn out to be fundamentally flawed; maybe 
some will work with existing kinds of types rather than needing new kinds 
of variable-sized types.  But since all those ideas are currently under 
discussion in WG14, the SVE issues should be brought into the exploration 
process taking place there, with a view to getting a better-defined set of 
concepts for such types out of that process than from considering just one 
proposal for concepts for one set of requirements in the context of one 
implementation.

Once that discussion has resulted in a more generally applicable set of 
concepts, experience in implementing that set of concepts - likely various 
different people implementing them, in different C implementations, with a 
view to the different use cases they are exploring - could help inform any 
standardization of such features.

-- 
Joseph S. Myers
joseph@codesourcery.com
Uecker, Martin Oct. 18, 2018, 8:24 p.m. | #17
Am Donnerstag, den 18.10.2018, 20:53 +0100 schrieb Richard Sandiford:
> "Uecker, Martin" <Martin.Uecker@med.uni-goettingen.de> writes:

> > Hi Richard,

> > 

> > responding here to a couple of points.

> > 

> > For bignums and for a type-descibing type 'type'

> > there were proposals (including from me) to implement

> > these as variable-sized types which have some restrictions,

> > i.e. they cannot be stored in a struct/union.

> 

> But do you mean variable-sized types in the sense that they

> are completely self-contained and don't refer to separate storage?

> I.e. the moral equivalent of:

> 

>   1: struct { int size; int contents[size]; };

> 

> rather than either:

> 

>   2: struct { int size; int *contents; };


I was thinking about 1 not 2. But I would leave this to the
implementation. If it can unwind the stack and free
all allocated storage automatically whenever this is
necessary, it could also allocate it somewhere else.
Not that this would offer any real advantage...

In both cases the only real problem is when storing
these in structs. So this should simply be forbidden
as it is for VLAs.

> or:

> 

>   3: union {

>        // embedded storage up to N bits (N constant)

>        // description of separately-allocated storage (for >N bits)

>      };


This is essentially an optimized version of 2.
    
> ?  If so, how would that work with the example I gave in the earlier

> message:

> 

>     bignum x = ...;

>     for (int i = 0; i < var; ++i)

>       x += x;

> 

> Each time the addition result grows beyond the original size of x,

> I assume you'd need to allocate a new stack bignum for the new size,

> which would result in a series of ever-increasing allocas.  Won't that

> soon blow the stack?


That depends on the final size of x relative to the size of the stack.
But this is no different to:

for (int i = 0; i < var; ++)
{
   int x[i];
}

or to a recursive function. There are many ways to exhaust the
stack. It is also possible to exhaust other kinds of resources.
I don't really see the problem.

> Option 3 (as for LLVM's APInt) seems far less surprising, and can

> be made efficient for a chosen N.


Far less surprising in what sense?

>  What makes it difficult for C

> isn't the lack of general variable-length types but the lack of

> user-defined contructor, destructor, copy and move operations.


C already has generic variable-length types (VLAs). So yes, 
this is not what makes it difficult.

Yes, descructors would be needed to make it possible to store
these types in struct without memory leakage. But the destructors
don't need to be user defined, it could be a special purpose
destructor which only frees the special type.

But it doesn't really fit in the way C works and I kind of like
that C doesn't do anything behind my back.

Best,
Martin


> Thanks,

> Richard

> 

> > Most of the restrictions for these types would be the same

> > as proposed for your sizeless types. 

> > 

> > Because all these types fall into the same overall class

> > of types which do not have a size known at compile

> > time, I would suggest to add this concept to the standard

> > and then define your vector types as a subclass which

> > may have additional restrictions (no sizeof) instead

> > of adding a very specific concept which only works for

> > your proposal.

> > 

> > Best,

> > Martin

> > 

> > 

> > 

> > 

> > 

> > Am Donnerstag, den 18.10.2018, 13:47 +0100 schrieb Richard Sandiford:

> > > Joseph Myers <joseph@codesourcery.com> writes:

> > > > On Wed, 17 Oct 2018, Richard Sandiford wrote:

> > > > > Yeah, can't deny that if you look at it as a general-purpose extension.

> > > > > But that's not really what this is supposed to be.  It's fairly special

> > > > > purpose: there has to be some underlying variable-length/sizeless

> > > > > built-in type that you want to provide via a library.

> > > > > 

> > > > > What the extension allows is enough to support the intended use case,

> > > > > and it does that with no enforced overhead.

> > > > 

> > > > Part of my point is that there are various *other* possible cases of 

> > > > non-VLA-variable-size-type people have suggested in WG14 reflector 

> > > > discussions - so any set of concepts for such types ought to take into 

> > > > account more than just the SVE use case (even if other use cases need 

> > > > further concepts added on top of the ones needed for SVE).

> > > 

> > > [Answered this in the other thread -- sorry, took me a while to go

> > > through the full discussion.]

> > > 

> > > > > > Surely, the processor knows the size when it computes using these

> > > > > > types, so one could make it available using 'sizeof'.

> > > > > 

> > > > > The argument's similar here: we don't really need sizeof to be available

> > > > > for vector use because the library provides easy ways of getting

> > > > > vector-length-based constants.  Usually what you want to know is

> > > > > "how many elements of type X are there?", with bytes just being one

> > > > > of the available element sizes.

> > > > 

> > > > But if having sizeof available makes for a more natural language feature 

> > > > (one where a few places referencing VLAs need to change to reference a 

> > > > more general class of variable-size types, and a few constraints on VLAs 

> > > > and variably modified types need to be relaxed to allow what you want with 

> > > > these types), that may be a case for doing so, even if sizeof won't 

> > > > generally be used.

> > > 

> > > I agree that might be all that's needed in C.  But since C++ doesn't

> > > even have VLAs yet (and since something less ambituous than VLAs was

> > > rejected) the situation is very different there.

> > > 

> > > I think we'd need a compelling reason to make sizeof variable in C++.

> > > The fact that it isn't going to be generally used for SVE anyway

> > > would undercut that.

> > > 

> > > > If the processor in fact knows the size, do you actually need to include 

> > > > it in the object to be able to provide it when sizeof is called?  (With 

> > > > undefined behavior still present if passing the object from a thread with 

> > > > one value of sizeof for that type to a thread with a different value of 

> > > > sizeof for that type, of course - the rule on VLA type compatibility would 

> > > > still need to be extended to apply to sizes of these types, and those they 

> > > > contain, recursively.)

> > > 

> > > No, if we go the undefined behaviour route, we wouldn't need to store it.

> > > This was just to answer Martin's suggestion that we could make sizeof(x)

> > > do the right thing for a sizeless object x by storing the size with x.

> > > 

> > > Thanks,

> > > Richard
Richard Sandiford Oct. 19, 2018, 9:18 a.m. | #18
Joseph Myers <joseph@codesourcery.com> writes:
> On Thu, 18 Oct 2018, Richard Sandiford wrote:

>> - Type introspection for things like parsing format strings

>> 

>>   It sounded like the type descriptors would be fixed-sized types,

>>   a bit like a C version of std::type_info.

>

> It wasn't clear if people might also want to e.g. extract a list of all 

> members of a structure type from such an object (which of course could 

> either involve variable-sized data, or fixed-size data pointing to arrays, 

> or something else along those lines).


OK.  But wouldn't that basically be a tree structure?  Or a flexible
array if flattened?  It doesn't sound like it would need changes to
the type system.  We can already describe this kind of thing with tree
types in GCC.  (The memory needed to represent the data could of course
be allocated using a single block of stack if that's what's wanted.)

>> So I didn't see anything there that was really related, or anything that

>> relied on sizeof being variable (which as I say seems to be a very high

>> hurdle for C++).

>

> The references you gave regarding the removal of one version of VLAs from 

> C++ didn't seem to make clear whether there were supposed to be general 

> issues with variable-size types fitting in the overall C++ object model, 

> or whether the concerns were more specific to things in the particular 

> proposal - but in either case, the SVE proposals would need to be compared 

> to the actual specific concerns.


But this is also one of my concerns about moving this discussing to the
WG14 list.  It doesn't seem to be publicly readable, and I only knew
about the bignum discussion because you gave me a direct link to the
first article in the thread.  I had to read the rest by wgetting the
individual messages.  So any objections raised there would presumably
be shrouded in mystery to most people, and wouldn't e.g. show up in a
web search.

If we move it to a different forum, I'd rather it be a public one that
would treat C and C++ equally.  But maybe such a thing doesn't exist. :-)

> Anyway, the correct model in C++ need not be the same as the correct model 

> in C.  For example, for decimal floating point, C++ chose a class-based 

> model whereas C chose _Decimal* keywords (and then there's some compiler 

> magic to use appropriate ABIs for std::decimal types, I think).

>

> If you were implementing the SVE API for C++ for non-SVE hardware, you 

> might have a class-based implementation where the class internally 

> contains a pointer to underlying storage and does allocation / 

> deallocation, for example - sizeof would give some fixed small size to the 

> objects with that class type, but e.g. copying them with memcpy would not 

> work correctly (and would be diagnosed with -Wclass-memaccess).


One important point here is that the SVE API isn't a new API whose
primary target happens to be SVE.  It's an API whose *only* target
is SVE.  Anyone wanting to write vector code that runs on non-SVE
hardware should use something that's designed to be cross-platform,
(e.g. P0214 or whatever).  They certainly shouldn't be using this.

Like other vector intrinsics, the SVE ACLE is supposed to be the last
line of defence before resorting to asm, and isn't designed to be any
more portable than asm would be.

> Is there something wrong with a model in C++ where these types have

> some fixed small sizeof (which carries through to sizeof for

> containing types), but where different ABIs are used for them, and

> where much the same raw memory operations on them are disallowed as

> would be disallowed for a class-based implementation?  (Whether

> implemented entirely in the compiler or through some combination of

> the compiler and class implementations in a header - though with the

> latter you might still need some new language feature, albeit only for

> use within the header rather than more generally.)


Having different ABIs would defeat the primary purpose of the extension,
which is to provide access to the single-vector SVE ABI types in C and C++.
We want types that in both C and C++ represent the contents of SVE vector
and predicate registers.  E.g.:

  svfloat64_t vector_sin(svbool_t pg, svfloat64_t vx)

has to map pg to a predicate register (P0), vx to a vector register (Z0)
and return the result in a vector register (Z0), in both C and C++.

The main objection to the details of the sizeless type proposal seems
to be that sizeof was too useful for us to make it invalid.  But if
sizeof has different values for C and C++, wouldn't that defeat the
point?  Users would be forced to use the SVE vector length functions
after all.  Also, for:

  void (*update_vector)(svfloat64_t *px);

how would the caller of update_vector know whether the target
function is using the C or the C++ representation of svfloat64_t
when accessing *px?

> Even if that model doesn't work for some reason, it doesn't mean the only 

> alternatives for C++ are something like VLAs or a new concept of sizeless 

> types for C++ - but I don't have the C++ expertise to judge what other 

> options for interfacing to SVE might fit best into the C++ language.


This is one of the reasons I was raising this as a joint RFC about what
would be acceptable in both the C and C++ frontends (treating it as
either a GNU extension or a target extension for now).

The sizeless type proposal keeps the new built-in vector types in
the common subset of C and C++ by "opting out of" (among other things)
features in one language that would make them problematic in the other.

>> I think it would look something like this (referring back to

>> 

>>     *Object types are further partitioned into sized and

>>     sizeless; all basic and derived types defined in this standard are

>>     sized, but an implementation may provide additional sizeless types.*

>> 

>> in the RFC), not really in standardese yet:

>> 

>>     Each implementation-specific sizeless type may have a set of

>>     implementation-specific "configurations".  The configuration of

>>     such a type may change in implementation-defined ways at any given

>>     sequence point.

>> 

>>     The configuration of a sizeless structure is a tuple containing the

>>     configuration of each member.  Thus the configuration of a sizeless

>>     structure changes if and only if the configuration of one of its

>>     members changes.

>> 

>>     The configuration of an object of sizeless type T is the configuration

>>     of T at the point that the object is created.

>> 

>> And then borrowing slightly from your 6.7.6.2#6 reference:

>> 

>>     If an object of sizeless type T is accessed when T has a different

>>     configuration from the object, the behavior is undefined.

>> 

>> Is that the kind of thing you mean?

>

> Yes.  But I wonder if it would be better to disallow such changing of 

> configurations, so that all code in a program always uses the same 

> configuration as far as the standard is concerned, so that there is indeed 

> a size for a given vector type that's constant throughout the execution of 

> a program (which would be used by calls to sizeof on such types), and so 

> that communicating with a thread using a different configuration is just 

> as much outside the scope of the defined language as processes using 

> different ABIs communicating is today.


The problem isn't just communicating with different threads though.
If the program changes the vector length and consistently uses objects
created with that new vector length, the size of the object would still
be different from the size of the real payload.  We would have to resort
to the type having implementation-defined amounts of padding, with the
amount of padding varying at sequence points in the same way as above.
(This would effectively be (3a) from the RFC FWIW.)

The reason for adding the above was to describe the ways in which
accessing an object with the "wrong length" would invoke undefined
behaviour.  If we say that there never is a wrong length (and thus
no undefined behaviour from using the wrong length) we'd just end
up with a legal fiction.  It'd seem better not to add it at all.

Thanks,
Richard
Joseph Myers Oct. 19, 2018, 1:14 p.m. | #19
On Fri, 19 Oct 2018, Richard Sandiford wrote:

> Joseph Myers <joseph@codesourcery.com> writes:

> > On Thu, 18 Oct 2018, Richard Sandiford wrote:

> >> - Type introspection for things like parsing format strings

> >> 

> >>   It sounded like the type descriptors would be fixed-sized types,

> >>   a bit like a C version of std::type_info.

> >

> > It wasn't clear if people might also want to e.g. extract a list of all 

> > members of a structure type from such an object (which of course could 

> > either involve variable-sized data, or fixed-size data pointing to arrays, 

> > or something else along those lines).

> 

> OK.  But wouldn't that basically be a tree structure?  Or a flexible

> array if flattened?  It doesn't sound like it would need changes to


I don't know (but you mention flexible arrays, and initializers for 
flexible array members, where the size of the object ends up bigger than 
sizeof its type, are also a GNU extension).  Raise that question in the 
WG14 discussion; I'm not the right person to answer questions around 
everyone else's ideas for extensions to the C type system.  As far as I'm 
concerned, this is all a preliminary exploration of ideas that might or 
might not end up involving type system additions, and WG14 is a much 
better place for that than separate single-implementation discussions - 
the point should be to float and explore possible ideas in this space, and 
their benefits and disadvantages, rather than pushing too early for one 
particular approach.  And given how much C++ tends to use class-based 
interfaces where C uses built-in types (complex numbers, decimal floating 
point, ...), I definitely do not want to start from an assumption that the 
right interface or language concepts for this in C++ should look like 
those in C.

For me, thinking of SVE types as something like VLAs but passed by value 
seems a more natural model in C than having them sizeless - but if they 
are sizeless, that pushes them closer to other ideas for types that might 
also be sizeless (and if those other use cases are indeed best specified 
using sizeless types, that provides more justification for using sizeless 
types for SVE).

> > Is there something wrong with a model in C++ where these types have

> > some fixed small sizeof (which carries through to sizeof for

> > containing types), but where different ABIs are used for them, and

> > where much the same raw memory operations on them are disallowed as

> > would be disallowed for a class-based implementation?  (Whether

> > implemented entirely in the compiler or through some combination of

> > the compiler and class implementations in a header - though with the

> > latter you might still need some new language feature, albeit only for

> > use within the header rather than more generally.)

> 

> Having different ABIs would defeat the primary purpose of the extension,

> which is to provide access to the single-vector SVE ABI types in C and C++.


My suggestion is that the ABI for C++ would be different from that 
resulting for a class-based implementation using purely standard C++ (the 
difference being to make it the same as the SVE C API - as with the 
decimal floating-point classes).

-- 
Joseph S. Myers
joseph@codesourcery.com