Index: docs/ScalableVectorType.rst =================================================================== --- /dev/null +++ docs/ScalableVectorType.rst @@ -0,0 +1,132 @@ +============================================================= +Extending VectorType to support scalable vector architectures +============================================================= + +To represent a vector of unknown length a boolean `Scalable` property has been +added to the `VectorType` class, which indicates that the number of elements in +the vector is a runtime-determined integer multiple of the `NumElements` field. +Most code that deals with vectors doesn't need to know the exact length, but +does need to know relative lengths -- e.g. get a vector with the same number of +elements but a different element type, or with half or double the number of +elements. + +In order to allow code to transparently support scalable vectors, we introduce +an `ElementCount` class with two members: + +- `unsigned Min`: the minimum number of elements. +- `bool Scalable`: is the element count an unknown multiple of `Min`? + +For non-scalable vectors (``Scalable=false``) the scale is considered to be +equal to one and thus `Min` represents the exact number of elements in the +vector. + +The intent for code working with vectors is to use convenience methods and avoid +directly dealing with the number of elements. If needed, calling +`getElementCount` on a vector type instead of `getVectorNumElements` can be used +to obtain the (potentially scalable) number of elements. Overloaded division and +multiplication operators allow an ElementCount instance to be used in much the +same manner as an integer for most cases. + +This mixture of compile-time and runtime quantities allow us to reason about the +relationship between different scalable vector types without knowing their +exact length. + +The runtime multiple is not expected to change during program execution for SVE, +but it is possible. The model of scalable vectors presented in this RFC assumes +that the multiple will be constant within a function but not necessarily across +functions. As suggested in the recent RISC-V rfc, a new function attribute to +inherit the multiple across function calls will allow for function calls with +vector arguments/return values and inlining/outlining optimizations. + +IR Textual Form +--------------- + +The textual form for a scalable vector is: + +`` x >`` + +where `type` is the scalar type of each element, `n` is the minimum number of +elements, and the string literal `scalable` indicates that the total number of +elements is an unknown multiple of `n`; `scalable` is just an arbitrary choice +for indicating that the vector is scalable, and could be substituted by another. +For fixed-length vectors, the `scalable` is omitted, so there is no change in +the format for existing vectors. + +Scalable vectors with the same `Min` value have the same number of elements, and +the same number of bytes if `Min * sizeof(type)` is the same (assuming they are +used within the same function): + +```` and ```` have the same number of + elements. + +```` and ```` have the same number of + bytes. + +IR Bitcode Form +--------------- + +To serialize scalable vectors to bitcode, a new boolean field is added to the +type record. If the field is not present the type will default to a fixed-length +vector type, preserving backwards compatibility. + +Size Queries +------------ + +This is a proposal for how to deal with querying the size of scalable types for +analysis of IR. While it has not been implemented in full, the general approach +works well for calculating offsets into structures with scalable types in a +modified version of ComputeValueVTs in our downstream compiler. + +For current IR types that have a known size, all query functions return a single +integer constant. For scalable types a second integer is needed to indicate the +number of bytes/bits which need to be scaled by the runtime multiple to obtain +the actual length. + +For primitive types, `getPrimitiveSizeInBits()` will function as it does today, +except that it will no longer return a size for vector types (it will return 0, +as it does for other derived types). The majority of calls to this function are +already for scalar rather than vector types. + +For derived types, a function `getScalableSizePairInBits()` will be added, which +returns a pair of integers (one to indicate unscaled bits, the other for bits +that need to be scaled by the runtime multiple). For backends that do not need +to deal with scalable types the existing methods will suffice, but a debug-only +assert will be added to them to ensure they aren't used on scalable types. + +Similar functionality will be added to DataLayout. + +Comparisons between sizes will use the following methods, assuming that X and +Y are non-zero integers and the form is of { unscaled, scaled }. + +{ X, 0 } { Y, 0 }: Normal unscaled comparison. + +{ 0, X } { 0, Y }: Normal comparison within a function, or across + functions that inherit vector length. Cannot be + compared across non-inheriting functions. + +{ X, 0 } > { 0, Y }: Cannot return true. + +{ X, 0 } = { 0, Y }: Cannot return true. + +{ X, 0 } < { 0, Y }: Can return true. + +{ Xu, Xs } { Yu, Ys }: Gets complicated, need to subtract common + terms and try the above comparisons; it + may not be possible to get a good answer. + +It's worth noting that we don't expect the last case (mixed scaled and +unscaled sizes) to occur. Richard Sandiford's proposed C extensions +(http://lists.llvm.org/pipermail/cfe-dev/2018-May/057830.html) explicitly +prohibits mixing fixed-size types into sizeless struct. + +I don't know if we need a 'maybe' or 'unknown' result for cases comparing scaled +vs. unscaled; I believe the gcc implementation of SVE allows for such +results, but that supports a generic polynomial length representation. + +My current intention is to rely on functions that clone or copy values to +check whether they are being used to copy scalable vectors across function +boundaries without the inherit vlen attribute and raise an error there instead +of requiring passing the Function a type size is from for each comparison. If +there's a strong preference for moving the check to the size comparison function +let me know; I will be starting work on patches for this later in the year if +there's no major problems with the idea.