[llvm-dev] RFC: Supporting the RISC-V vector extension in LLVM

[Graham Hunter via llvm-dev]

Hi,

Nice to see another group tackling length agnostic vectorization :)

I'm still reading through all the details, but I do have one initial question related to the vector type; why not use the same mechanism Arm is proposing for SVE?

We chose the format "<n x m x <ty>>" to represent two crucial concepts: arbitrary length vectors with the same number of elements, or with the same number of bits. From what I gather, you're just interested in the former, so is there a good reason "<n x 1 x <ty>>" wouldn't work for your use case? The 'n' is just a term to indicate it's a multiple only known at runtime; you've used 'vlen', and there are other suggested names, but there's nothing to tie it to an exact size -- if your dynamic vlen changes with each function, the 'n'/'vlen' just represents the current value.

I'll continue looking through this, and will have more feedback next week.

-Graham

On 11/04/2018, 10:45, "llvm-dev on behalf of Robin Kruppe via llvm-dev" <llvm-dev-bounces at lists.llvm.org on behalf of llvm-dev at lists.llvm.org> wrote:

    RISC-V is an open and free instruction set architecture (ISA) used in numerous domains in industry and research. The vector extension (short: 'V') supplements the basic ISA with support for data parallel computations. This RFC sketches a strategy
     for targeting this instruction set extension in LLVM.
    
    Some but not all of what is proposed here has already been implemented out of tree. It is explicitly not proposed to upstream any of this yet: the vector extension is still evolving (though the core concepts are reasonably stable), and the implementation is
     currently very much prototype quality. Nevertheless, I want to kick off a discussion about this with the LLVM community now to make sure I'm on the right track and to make the eventual upstreaming go more smoothly. In particular, a large and potentially controversial
     part of the strategy is a proposal for extending LLVM IR with a new vector type.
    
    There is also much to be said about how to structure the code generation for this ISA. However, since that aspect somewhat simpler, largely orthogonal and affects a smaller subset of the community, the details will be left to a future RFC.
    
    This RFC is intended to be self-contained, but interested readers can learn more about the vector extension from Roger Espasa's talk at the 7th RISC-V workshop (slides [1], recording [2]). The draft specification is also available as part of the RISC-V Instruction
     Set Manual [3], but right now it is unfortunately incomplete and in the process of being updated.
    
    I will also be at EuroLLVM with a lightning talk and poster on this subject, so if you're there as well, we can discuss in person.
    
    [1] 
    https://content.riscv.org/wp-content/uploads/2017/12/Wed-1330-RISCVRogerEspasaVEXT-v4.pdf <https://content.riscv.org/wp-content/uploads/2017/12/Wed-1330-RISCVRogerEspasaVEXT-v4.pdf>
    [2] https://www.youtube.com/watch?v=GzZ-8bHsD5s
    [3] https://github.com/riscv/riscv-isa-manual/
    
    
    # Summary
    
    First-class support for the RISC-V vector ISA requires representing a hardware vector length that is not just unknown at compile time, but also changes during execution. This in turn places some restrictions on code motion: the vector length must not change
     while any vector values are live. This RFC proposes to add a new vector type to LLVM IR for this purpose. Simply put, its length is tied to the surrounding function and the existing `token` type is leveraged to tell optimization passes that certain vector
     operations must remain together (i.e., in the same function).
    
    
    # Background
    
    The RISC-V vector extension has many interesting properties. This RFC is not the right place to talk about it in detail, but this section will briefly introduce the aspect that is most difficult to support in LLVM IR, and which is consequently the focus of
     this RFC: the runtime-variable vector length.
    
    The number of elements in a vector register is determined by the microarchitecture. Software uses strip-mined loops to transparently process as many elements per iteration as the hardware can support. But even beyond that, the vector length can vary during
     the execution of a program: different kernels may *configure* the vector unit differently depending on their needs, leading to different parts of the program having differently-sized vector registers.
    
    The vector length being determined by the microarchitecture is similar to Arm's Scalable Vector Extension (SVE), for which support is being upstreamed at the moment. However, in SVE the vector length is fixed once a program starts running, while full use of
     the RISC-V vector extension will lead to the vector length changing regularly during execution. It's possible to maintain the same configuration -- and therefore the same vector length -- throughout the entire program, but this will often perform worse than
     a tailored configuration.
    
    ## Maximum vs active vs application vector length
    
    The V ISA has two notions of vector length: the *maximum* vector length (called MVL), which describes the number of elements in each vector register, and the *active* vector length (called vl), which limits how many of those elements are actually processed
     by each vector instruction.
    
    The latter is used to express loops of any application-specified length with a single copy of the loop body. Instead of handling the tail iterations not divisible by MVL separately with scalar code, the active length length is set up so that the last few iterations
     process as many elements as are left to process.
    
    The effect of the active vector length is similar to a mask of the form `<true, ..., true, false, ..., false>`, aside from the scalar control logic that sets and maintains the active vector length. Thus it can be modeled in IR with judicious use of intrinsics
     and masking. This still allows also having a single loop body in IR, without introducing new IR concepts in addition to those already needed for the variable MVL.
    
    Thus, the rest of this RFC focuses on handling the MVL: all references to "vector length" from this point on should be taken to refer to the MVL, not the active vector length.
    
    
    # Scope of the support
    
    To preempt misunderstandings, this section outlines what is meant and not meant by "support for the vector extension".
    
    ## Variable vector length
    
    There *is* an option to entirely avoid the concept of the vector length changing during execution. Keeping the same vector unit configuration throughout the entire program execution also leads to the vector length being fixed once the program starts executing.
     In this case, compiler support works out rather rather similar to support for Arm SVE, with the biggest difference being that vectors lengths are not multiples of 128 bit (which legalization can paper over). Indeed, no IR changes beyond those proposed for
     SVE support appear to be necessary to implement this approach to RISC-V vector extension support.
    
    However, this approach is wasteful, as a tailored configuration can improve performance and energy efficiency significantly. As one data point, the Hwacha project reported [4] up to 9.5% fewer cycles taken and up to 11% less energy consumed on a microarchitecture
     built to exploit narrower bit widths of vector elements (comparing "mvp, packed: yes" to "mvp, packed: no"). Besides such microarchitectural optimizations, enabling fewer registers can improve context switch times because fewer registers need to be saved,
     and being more flexible in how registers can be used (in particular, how many are reserved for scalar values) aids register allocation.
    
    Thus, restricting programs to a single configuration may be a good first step to get things up and running, but ultimately support for runtime-varying vector lengths is desired to make the most of hardware capabilities.
    
    [4] "A Case for MVPs: Mixed-Precision Vector Processors", Albert Ou, Quan Nguyen, Yunsup Lee, Krste Asanović,
    http://hwacha.org/papers/hwacha-mvp-prism2014.pdf
    
    
    ## Producing vector code
    
    It is intended that vector code is primarily produced via loop vectorization and other IR-level auto-vectorizers (e.g., the region vectorizer), not written by hand. Supporting loop vectorization is of highest priority. The groundwork for loop vectorization
     should be useful for other kinds of automatic vectorization as well, but loop vectorization will be implemented first.
    
    It's not required or expected that the stock loop vectorizer can generate RISC-V vector code from the start. Considering the many significant differences to the packed-SIMD architectures the loop vectorizer is tailored to, it's quite likely that some experimentation
     in this space is required (e.g., building on VPlan and writing custom recipes). Of course, in the long term there should be as much code sharing as possible.
    
    Support for hand-written vector code va source-language-level intrinsics (as opposed to inline assembly) would be nice to have and probably falls out for free, but is rather low priority.
    
    
    ## No vector unit configuration in IR
    
    While configuring the vector unit is an essential part of compiling for the V ISA, it has no place in LLVM IR. Vectors should be regular SSA values that don't reference any extra state other than (by necessity) the vector length. Deciding how to configure the
     vector unit for a given piece of code is target-dependent and intertwined with register allocation, and will therefore be left to the backend.
    
    # Challenge: Code motion around vector length changes
    
    When the vector length can change during execution, there are implicit dependencies between vector operations and points in the program where the vector length may change. These dependencies must be taken into account somehow, or else code motion passes could
     move vector operations across vector length changes, effectively changing program semantics. For example, it's nonsensical to compute a vector value `%v1` with one vector length, change the vector length, and then compute another vector `%v2` with the new
     vector length and add it to `%v1`. This makes no more sense than adding `<4 x i32>` to `<8 x i32>`, yet it could happen if an input program has a vector length change *after* these vector calculations and optimization passes are not aware of the impact of
     the vector length change on those calculations.
    
    Crucially, the vector length changes when calling and returning from functions in most calling conventions. Functions that don't specifically use a vectorcall ABI configure the vector unit for their own use when called, rather than using configuration set up
     by the caller. Therefore, caller and callee will generally have different vector lengths, and moving vector operations from the caller into the callee or vice versa tends to break programs.
    
    However, note that the precise value of the vector length doesn't really matter -- software is supposed to be *vector length agnostic*. Completely inlining a function is perfectly fine, for example. What matters is that the vector length doesn't change *during*
     vector computations, i.e., while any vector values are live (either as SSA values, or in memory!). Thus, there is no need to support and track vector length changes at instruction granularity. It's enough to coarsely enforce that the vector length remain constant
     throughout a larger code region (say, a loop nest, or a function).
    
    
    # Runtime-varying vector length in the IR
    
    This is achieved by simply declaring "by fiat" that the vector length is determined on function entry and remain constant for the rest of the function execution. Other functions and other calls to the same function may observe a different vector length, but
     within one call to a given function, the vector length is fixed. That is not precisely how the hardware works, but it is a contract the backend can uphold easily (more on this later) and it allows piggy-backing on existing IR constructs (the `token` type)
     to communicate restrictions to optimization passes. Nevertheless, some additions to IR are required: a new first class type, a new instruction, and a new operand for some existing instructions.
    
    ## IR semantics
    
    Every time a function is called, a positive integer called the *dynamic vector length* is determined in an unspecified way. The dynamic vector length can differ not only between different functions, but also between different calls to the same function. The
     exception is that functions with the `inherits_vlen` attribute get the same dynamic vector length as their caller (Note: this attribute is a straw man, target-specific calling conventions may work better for this purpose).
    
    A new instruction `vlentoken` is added, which has no operands and is of type `token`. This token represents the dynamic vector length of the function execution it is in. There can only be one such instruction per function (this is inconsequential to the operational
     semantics, but it simplifies IR passes).
    
    A new kind of type is added, the *dynamic-length vector*, written `< vlen x <element type> >`. It represents a vector with a number of elements equal to the dynamic vector length. Like fixed-length and scalable vectors, these vectors can only contain integer,
     float and pointer elements.
    
    A use of a `vlentoken` (representing a dynamic vector length) is attached to all operations that care for the dynamic vector length. That is, *every* instruction that handles dynamic-length vectors or is impacted by their length receives the respective function's
     `vlentoken` as extra operand, and operates on a number of elements equal to the corresponding dynamic vector length.
    
    `< vlen x <element type> >` is a first-class type and supports most common instructions (details below), but cannot be used as function argument or function return type unless the `inherits_vlen` attribute is applied to the callee.
    
    
    ## Rationale / "why this works"
    
    Although the vector length is a property of vector *values*, tracking the dynamic vector length at the type level would require a "separate type" for each call to any function. It's much more feasible to attach the vector length to the *operations* instead.
     This works out because SSA values are function-local (so all operation on them agree on the vector length by definition) with the exception of function arguments and return values. Consequently, dynamic-length vectors in function signatures are disallowed
     unless the `inherits_vlen` attribute ensured caller and callee have the same dynamic vector length.
    
    The `vlentoken` token ensures that all operations that start out in the same function must remain in the same function while the code is transformed (recall that tokens cannot be passed to or returned from non-intrinsic functions). That's why it is important
     that `vlentoken` is a token, not simply an integer as one might expect. In other words, `vlentoken` does not give the program access to the dynamic vector length, it communicates a restriction to the optimizer.
    
    ## More details
    
    The `< vlen x <element type> >` type is separate from the existing vector types. Instructions for fixed-length vectors (elementwise arithmetic, `insertelement`, `select` with a vector of `i1`s, etc.) are not extended to this new type, at least not in this RFC.
     It's a possible future extension, but for now, target-specific intrinsics work fine for those operations.
    
    The following operations on dynamic-length vectors *are* supported:
    
    - `phi`
    - `load` and `store`
    - `alloca` (at least of a single vector; the `alloca <ty>, <ty> <NumElements>` form ties into the open question about aggregates and GEPs below)
    - `select` (with `i1` condition)
    - Argument passing and return values (`call`, `invoke`, `ret`) for functions with `inherits_vlen`
    
    All of these instructions (including phi) have an additional operand of type `token` if and only if they operate on a vector of dynamic length. In textual IR, one appends `, vlen <the token>` to the instruction, for example:
    
        %0 = vlentoken
        %ptr = alloca <vlen x i32>, vlen %0
        %v = call <vlen x i32> @foo(), vlen %0
        store <vlen x i32> %v, <vlen x i32>* %ptr, vlen %0
    
    Open question: should GEPs and aggregates involving dynamic-length vectors work? This RFC errs on the side of simplicity and excludes them (they're non-trivial to implement and not needed for strip-mined loops) but if desired, they could be supported.
    
    There are no constants of dynamic-length-vector type except `zeroinitializer` and `undef` (resp. `poison` once that is adopted). In particular, there is no equivalent to fixed-length vector constants (`<ty elem1, ty elem2, ...>`). Dynamic-length vectors also
     cannot be stored in globals.
    
    ## Impact on optimizations
    
    The semantics imply several restrictions on optimizations, but these are mostly encoded with existing IR constructs -- chiefly, the `token` type that ties all vector operations to a `vlentoken`. For example, because token values cannot be passed to (non-intrinsic)
     functions or returned from them, no special pleading is needed to keep an outliner or partial inliner from spreading vector operations across multiple functions -- correct passes already don't do that when tokens are involved. Passes do, however, need to be
     updated in two respects.
    
    First, the new token operand needs to be respected when comparing two instructions, creating new instructions, etc. -- this is an inherent downside of adding new operands, but also rather mechanical. The rule that there is only one `vlentoken` per function
     makes this even more mechanical than usual, because all instruction within one function have the same vector length token. This means that one does not need to consider them when comparing instructions from the same function, and it's always clear which token
     should be used when creating a new instruction.
    
    Second, the very same rule of only one `vlentoken` per function must be respected during interprocedural code motion. For example, inlining can't just copy the `vlentoken` from the callee into the caller.
    
    However, note that it's valid to *merge* the caller's and callee's `vlentoken` instructions. Because the semantics state that each call to a function can get a different dynamic vector length, merging `vlentoken`s *refines* the program's behavior by picking
     the possible execution where the callee "happens to" get the same vector length as the caller in the inlined calls. So inlining can simply replace all `vlentoken` tokens in the inlined code with the `vlentoken` token of the callee. Other passes are likely
     similarly easy to update (and in the worst case, they can just bail out when seeing dynamic-length vectors).
    
    ## Impact on backends
    
    Unsurprisingly, the IR types `<vlen x <element type> >` come with associated MVTs. There's also a new SelectionDAG node `VLENTOKEN` to mirror the `vlentoken` IR instruction (and presumably `G_VLENTOKEN` in GMIR for GlobalISel).
    
    Backends other than RISC-V can legalize these MVTs and the `VLENTOKEN` node very easily, even if in practice there currently aren't many useful operations on these vectors without target-specific intrinsics. Specifically, `< vlen x <element type> >` can be
     legalized as `< n x <element type> >` or even `< scalable n x <element type> >` (the vector type for Arm SVE) for any fixed `n`. All the complications stemming from the runtime-varying vector length go away, and the `vlentoken` node can simply be dropped on
     the floor.
    
    That leaves targets with an actual runtime-varying vector length in hardware, i.e., RISCV with the V feature enabled. As stated in the introduction, this RFC does not cover the backend changes in detail, but to give you a rough idea, here's a sketch. Keep in
     mind (especially if you're familiar with V) that this is glossing over everything not directly related to the proposed IR type (particularly the "polymorphic instruction set" aspect of the register configuration).
    
    As described earlier, the vector length in RISC-V is completely determined by the vector unit configuration. Therefore, vector operations in Machine IR have an implicit use of the configuration registers. This is the moral equivalent of the `vlentoken` token
     operand, but more precise (and MIR doesn't have an equivalent of the token type anyway). To complete the picture, all operations that change the configuration are made explicit.
    
    Because only virtual registers can be live across basic block boundaries before register allocation, this may require a dummy register class with only a single physical register, or something similarly inelegant.
    
    With a way to precisely represent vector length changes in hand, the backend just needs to ensure it implements the semantics of `< vlen x <element type> >` described earlier. This is achieved by configuring the vector unit "in the prologue", and then not doing
     anything that might change the vector length inside the function. This setup is effectively in the prologue (i.e., before any user code) but not actually inserted during the "prologue/epilogue insertion" pass, which runs far too late for this purpose.
    
    For scenarios like two entirely separate vectorized loops within one function, it might be useful to drastically change the vector unit configuration in the middle of a function. This could be implemented as an optimization (e.g., a pre-RA machine function),
     but it's all hypothetical so far.