Roger Ferrer Ibáñez via llvm-dev
2020-Oct-16 08:02 UTC
[llvm-dev] [RFC] Code generation for RISC-V V-extension
Hi all,
(I uploaded a PDF rendered of this email just in case some of its sections
are difficult to read
https://pm.bsc.es/~rferrer/tmp/rfc-vector-code-generation.pdf )
This is a RFC on the strategy we have been developing at the Barcelona
Supercomputing Center (BSC) to generate code for the RISC-V V-extension.
We (BSC and SiFive) have prepared a very first patch showing the strategy
explained in this email, found here
- https://reviews.llvm.org/D89449
Feedback is very welcome as we see this change as a foundation on which to
build the rest of the V-extension codegen support.
## Introduction
The V-extension of RISC-V brings vector computation capabilities to the
RISC-V ecosystem. The full details of the ISA specification are found here:
https://github.com/riscv/riscv-v-spec This proposal is based on draft
version 0.9 found at https://github.com/riscv/riscv-v-spec/releases/tag/0.9.
The V-extension is rather flexible so it is difficult to summarize it in an
reasonably sized email. Please refer to the above specification for all the
details. I'll try to describe here all the features that are relevant for
code generation.
The ISA provides 32 vector registers `v0`,`v1`, ..., `v31`. The size in
bits of each vector register is an implementation-specific parameter called
`VLEN` and must be a power of two. Vector registers are partitioned (i.e.
densely packed) in elements whose size in bits is a power of two, ranging
from 8 to `ELEN`. `ELEN` is also a power of two and `ELEN`<=`VLEN`.
Due to encoding constraints, not all the operands of a vector operation are
encoded in the instructions themselves. Two CSR (control and status
registers) are used instead:
- `vl`: the number of elements being operated, called the vector length. A
vector instruction will operate the elements `0` to `vl-1`
- `vtype`: the vector type. This register encodes the element size of the
operation, called the standard element width (`sew`) and a vector grouping
mechanism called the length multiplier (`lmul`)
The length multiplier (`lmul`) can take values 1, 2, 4, 8, 1/2, 1/4, 1/8.
- When `lmul=1` the vector instructions operate on the (32) vector
registers.
- When `lmul>1` the vector instructions operate on vector groups (see
below) encoded in the instruction using the lowest numbered vector register
of the group.
- When `lmul<1` the vector instructions operate on the lowest half, quarter
or eighth of a vector register.
A vector group of size `lmul>1` is the set of consecutive vector registers
`v{lmul*i}`, `v{lmul*i+1}`, ... , `v{lmul*(i + 1) - 1}`. So
- `lmul=2` has 16 groups: `v0`, `v2`, `v4`, `v6`, …, `v24`, `v26`, `v28`,
`v30`
- `lmul=4` has 8 groups: `v0`, `v4`, `v8`, `v12`, `v16`, `v20`, `v24`, `v28`
- `lmul=8` has 4 groups: `v0`, `v8`, `v16`, `v24`
For instance, under `lmul=4`, a vector group `v4` operand includes vector
registers `v4`, `v5,` `v6` and `v7` as if they had been concatenated as a
four times larger vector register. `lmul` is useful to align the number of
elements in vector codes whose element sizes are different (say when
combining vectors of 32- and 64-bit elements) or when doing *widenings*
(zero, sign or fp extensions) or *narrowings* (truncations).
A program must ensure that both `vl` and `vtype` have the correct values
for a vector operation before executing a vector instruction. This is done
using the `vsetvli` instruction.
```
vsetvli rdest, rsrc, sew,lmul,tx,mx # We discuss tx,mx below
```
`rsrc` is the application vector length (AVL) and will be used when setting
the `vl`. `rdest` is updated with the value of `vl`. The spec allows some
latitude here but a simple functional model of what vsetvli does is the
following
```
vl ← min(rsrc, lmul*VLEN/sew)
vtype ← sew,lmul,...
```
`vsetvli` has a couple of special cases
- When `rsrc` is `x0` and `rdest` is not `x0` then `vl ← lmul*VLEN/sew`. In
other words, sets `vl` to be the maximum vector length for a given `lmul`
and `sew`. This is useful for whole-register operations.
```
vsetvli t0, x0, e32,m2,… # vl ← 2*VLEN/64
# vtype ← e32,m2,...
# t0 ← vl
```
- When both `rsrc` and `rdest` are `x0` (the hard-coded zero of RISC-V)
then `vl` is used as the AVL. This can be used to change the `vtype` when
we know the ratio `sew/lmul` will be preserved.
```
vsetvli x0, x0, e64,m4,… # changing vtype from e32,m2 to e64,m4 is OK (vl
is unchanged)
# vtype ← e64,m4,...
```
Two simple examples (register `x10` contains the AVL)
- Add two 32-bit element vectors under `lmul=1`
```
vsetvli x0, x10, e32,m1,…
vadd.vv v1, v2, v3 # v1[0:vl-1] ← v2[0:vl-1] + v3[0:vl-1]
# where v[i:j] is all v[x] where i <= x <= j
```
- Add two 64-bit element vectors under `lmul=2`
```
vsetvli x0, x10, e64,m2,…
vadd.vv v2, v4, v6 # Updates v2 and v3. Reads v4, v5 and v6, v7
# v2[0:x-1] ← v4[0:x-1] + v6[0:x-1] where x min(VLEN/64,
vl)
# v3[0:y-1] ← v5[0:y-1] + v7[0:y-1] where y = vl - x
```
Note: it is not necessary to emit a `vsetvli` instruction before every
vector instruction if the current `vl` and `vtype` are still suitable for
the intended vector operation. Removing redundant `vsetvli` instructions is
not part of this proposal.
### Masks and tails
RISC-V Vector extension supports masks in almost all of its instructions.
There are no distinguished mask registers, instead vector registers can be
used to represent masks. However an instruction whose execution is masked
can only use the `v0` register as the mask operand. Elements of the
destination register that are masked off by the mask are called _inactive
elements_ (i.e. masked-off)
A vector instruction can be executed under a `vl` setting where `vl` <
`lmul*VLEN/sew`. Elements of the destination register past the current `vl`
are called the _tail elements_.
There are two modes for the tail and inactive elements
- undisturbed, in which the element of the destination register is left
unmodified
- agnostic, in which the elements of the destination register is either
left unmodified or all its bits set to 1 (for debugging purposes). In this
mode we cannot assume anything about the bits of those elements
`tx,mx` in vsetvli above correspond to these two policies and can be
combined in 4 ways:
- `tu,mu`. Both tail and inactive are left undisturbed
- `ta,ma`. Both tail and inactive are agnostic
- `tu,ma`. Tail is left undisturbed and inactive are agnostic
- `ta,mu`. Tail is agnostic and inactive are left undisturbed.
It may be reasonable to prefer the mode that is the least defined (such as
`ta,ma`) for the intended IR operation. Some select operations, however,
can be folded using masks in instructions (that would lead us to `ta,mu`).
However, for the sake of simplicity and given the early stage of this
works, we are going to use `tu,mu` mode everywhere. Relaxing to agnostic
where possible is postponed as later work.
## Mapping to LLVM IR Types
It seems reasonable to make `VLEN` an unknown constant to the compiler.
This leads us to use scalable vector types (such as the ones used by Arm
SVE target).
However in contrast to SVE, RISC-V V-extension does not prescribe a minimal
vector size (other than `ELEN<=VLEN`). This minimal vector size impacts the
LLVM types we can use because it impacts `vscale`. We propose that LLVM
targets only `VLEN>=64`. We believe other permissible values under the
V-ext spec (such as `VLEN=8`) are not realistically useful. Also we propose
that LLVM supports only `ELEN=32` and `ELEN=64`.
These constraints allow us to define `vscale` as `VLEN/64`. This makes the
LLVM IR types stable between the two `ELEN`s considered.
| | lmul=⅛ | lmul=¼ | lmul=½ |
lmul=1 | lmul=2 | lmul=4 | lmul=8 |
| ---------------- | ------------ | -------------- | --------------- |
---------------- | ---------------- | ---------------- | ---------------- |
| i64 (ELEN=64) | N/A | N/A | N/A | <v x
1 x i64> | <v x 2 x i64> | <v x 4 x i64> | <v x 8 x
i64> |
| i32 | N/A | N/A | <v x 1 x i32> |
<v x
2 x i32> | <v x 4 x i32> | <v x 8 x i32> | <v x 16 x
i32> |
| i16 | N/A | <v x 1 x i16> | <v x 2 x i16>
| <v x
4 x i16> | <v x 8 x i16> | <v x 16 x i16> | <v x 32 x
i16> |
| i8 | <v x 1 x i8> | <v x 2 x i8> | <v x 4 x
i8> | <v x
8 x i8> | <v x 16 x i8> | <v x 32 x i8> | <v x 64 x
i8> |
| double (ELEN=64) | N/A | N/A | N/A | <v x
1 x double> | <v x 2 x double> | <v x 4 x double> | <v x 8 x
double> |
| float | N/A | N/A | <v x 1 x float> |
<v x
2 x float> | <v x 4 x float> | <v x 8 x float> | <v x 16 x
float> |
| half | N/A | <v x 1 x half> | <v x 2 x half>
| <v x
4 x half> | <v x 8 x half> | <v x 16 x half> | <v x 32 x
half> |
(Read `<v x k x ty>` as `<vscale x k x ty>`)
One downside of this design is that doesn't allow vectors of `i128` (this
is, `ELEN=128`). In that case `vscale` would have to be 1/2 under `lmul=1`.
This type (and its fp counterpart `float128`) are not that common and in
case of extreme necessity types for `lmul=2` could be used instead.
As for mask vectors, they are physically represented using a layout of
densely packed bits in a vector register. It seems reasonable to map them
to the following LLVM IR types
```
<vscale x 1 x i1>
<vscale x 2 x i1>
<vscale x 4 x i1>
<vscale x 8 x i1>
<vscale x 16 x i1>
<vscale x 32 x i1>
<vscale x 64 x i1>
```
Two types with the same ratio `sew`/`lmul` will have the same related mask
type. For instance, two different comparisons one under `sew=64`, `lmul=2`
and the other under `sew=32`, `lmul=1` will both generate a mask `<vscale x
2 x i1>`.
## Register classes
Given the vector registers and the different sizes of vector groups, we
propose to define 4 register classes.
- `VR` for vector registers (`v0`, `v1`, ..., `v31`). `lmul<=1` and mask
registers
- `VRM2` for vector groups of length 2, this is `lmul=2` (`v0m2`, `v2m2`,
..., `v30m2`)
- `VRM4` for vector groups of length 4 (`v0m4`, `v4m4`, ..., `v28m4`)
- `VRM8` for vector groups of length 8 (`v0m8`, `v8m8`, `v16m8`, `v24m8`)
So far it looks like `lmul<1` types and mask types do not benefit from
having a dedicated class, so `VR` would be used in that case.
## What LLVM IR inputs we care bout
There are three kinds of inputs we believe are important to be selected as
vector instructions of V-extension.
- LLVM IR instructions that operate on vectors (whole-register operations)
```
vadd <vscale x 2 x i32> %a, %b
```
- Vector Predication intrinsics (explicit vector length vector operations)
```
call <vscale x 2 x i32> @llvm.vp.add(..., i32 %evl)?
```
See http://www.llvm.org/docs/Proposals/VectorPredication.html
- RISC-V V-extension target-specific intrinsics
```
call <vscale x 2 x i32> @llvm.rvv.vadd.nxv2i32(...)
```
See https://github.com/riscv/rvv-intrinsic-doc
## Challenges for code generation
The actual V-extension instructions are not immediately useful for the code
generation process (= the gap between LLVM IR and the emission of the
instructions)
- Two instances of the same instruction have different semantics depending
on the precise values of `vtype` and `vl`.
- To the best of our knowledge `MachineInstrs` cannot be overloaded per
register class
- The correct values of `vtype` and `vl` must be set before executing a
vector instruction
- `MachineInstrs` may need more information than just the encoded
operands, at least during selection
Other targets also have to solve this problem of "having the right
configuration/state before executing an instruction". As far as I
understood from the documentation and comments in llvm-dev, Intel AMX (see
http://lists.llvm.org/pipermail/llvm-dev/2020-September/144848.html) also
has some configuration step before being able to use the intructions that
implement some tensor operations. Looks like our work started earlier than
Intel AMX so their approach here might be interesting to compare in case
either design/approach can be improved.
Another example of a "needs configuration/set state" target (even if
deprecated today and probably of little interest to LLVM) is the Arm VFP
extension found in some legacy Arm cores such as the one in the Raspberry
Pi 1. I'm pretty sure I'm missing other notable examples. If someone is
working on a target with a similar way of working, feel free to chime in!
## The actual proposal
(Thanks for reading up to here!)
1. Mirror all the RISC-V V-extension instructions (which are already on
upstream) that depend either on vl or vtype in pseudo instructions. One
pseudo instruction per `lmul`.
1. Example: `VADD_VV` → `PseudoVADD_VV_M1`, `PseudoVADD_VV_M2`,
`PseudoVADD_VV_M4`, `PseudoVADD_VV_M8`, `PseudoVADD_VV_MF2`,
`PseudoVADD_VV_MF4`, `PseudoVADD_VV_MF8`,
2. Extend each pseudo instructions with additional operands.
1. a merge operand that is used for undisturbed semantics (otherwise set
to `IMPLICIT_DEF`). This operand is tied to the destination. If this is an
actual value it entails `tu,mu` (see section above "Masks and tails")
2. a vector mask operand for masked instructions (set to
`RISCV::NoRegister` if unmasked)
3. a `sew` immediate operand
4. a `GPR` containing the vector length of this operation (or
`RISCV::X0` if we want to use the maximum vector length)
5. implicit uses of `vl` and `vtype` registers
4. Use the pseudo instructions in the SelectionDAG patterns.
1. Patterns would, at least, choose the right `lmul` version, set the
proper `sew` immediate.
2. Optionally set a merge operand if merge semantics is desired
5. Each pseudo instruction would also have a custom inserter
1. The custom inserter emits a `vsetvli` instruction before the
instruction. The `lmul` is derived from the pseudo instruction.
2. Now the `sew` and the `vl` operands are not useful anymore and can be
set to `-1`, `RISCV::NoRegister` respectively
The final result is that each operation is prepended with a `vsetvli` that
sets both the `sew`, `lmul` and the `vl`.
While correct, this is naive, so later passes can remove the redundant
`vsetvlis`. This is out of the scope of this RFC.
Finally, at the end of CodeGen
5. AsmPrinter emits the Pseudo Instructions as their corresponding real
RISC-V V-extension MCInst instructions
1. We can’t do that earlier because we want to correctly keep track the
liveness of registers (their register classes). This is important for
`LMUL>1`.
### Example of a pseudo-instruction
This is a slightly simplified tablegen definition of a pseudo instruction
```
let Constraints = “$rd = $merge”, Uses = [VL, VTYPE],
usesCustomInserter = 1, BaseInstr = VADD_VV in
def PseudoVADD_VV_M2 : Pseudo<(outs VRM2:$rd),
(ins VRM2:$merge, VRM2:$rs2, VRM2:$rs1, VMaskOp:$vm,
GPR:$vl, ixlenimm:$sew), []>;
```
Tablegen allows generating systematically (for all `lmul`s) the pseudo
instructions and link them to the real instruction.
`GenericTable` is used to create a table of the pseudo instructions that
contains information about the extra operands.
### Example of the codegen flow
Let’s consider a very simple case using a whole-register op (this example
uses `lmul=2`)
```
%c = add <vscale x 4 x i32> %a, %b
```
Input ISEL DAG:
```
t5: nxv4i32 = add t2, t4
```
Output ISEL DAG:
```
t5: nxv4i32 = PseudoVADD_VV_M2 IMPLICIT_DEF:nxv4i32, t2, t4,
Register:nxv4i1 $noreg, Register:i64 $x0, TargetConstant:i64<32>
```
`MachineInstrs` after `InstrEmitter` (before `CustomInserter`)
- `%3:vrm2 = IMPLICIT_DEF`
- `early-clobber %2:vrm2 = PseudoVADD_VV_M2 %3:vrm2(tied-def 0), %0:vrm2,
%1:vrm2, $noreg, $x0, 32, implicit $vl, implicit $vtype`
(If you wonder about the `early-clobber` it is needed to fulfill some
constraints between sources and destination registers under `lmul>1`)
`MachineInstrs` after `CustomInserter`
- `%3:vrm2 = IMPLICIT_DEF`
- `dead %4:gprnox0 = PseudoVSETVLI $x0, 9, implicit-def $vl, implicit-def
$vtype`
- `early-clobber %2:vrm2 = PseudoVADD_VV_M2 %3:vrm2(tied-def 0), %0:vrm2,
%1:vrm2, $noreg, $noreg, -1, implicit $vl, implicit $vtype`
Now optimization passes could remove unnecesary `PseudoVSETVLI`s (if
neither `vtype` or `vl` change) or use the special form that only sets
`vtype` (if `vl` stays the same). Again, not covered in this RFC.
Post Register Allocation:
- `dead renamable $x10 = PseudoVSETVLI $x0, 9, implicit-def $vl,
implicit-def $vtype`
- `early-clobber renamable $v2m2 = PseudoVADD_VV_M2 undef renamable
$v2m2(tied-def 0), killed renamable $v16m2, killed renamable $v18m2,
$noreg, $noreg, -1, implicit $vl, implicit $vtype`
Finally `AsmPrinter` lowers the PseudoInstructions into real MCInsts,
discarding unneeded operands.
- `<MCInst #3745 <MCOperand Reg:45> <MCOperand Reg:35>
<MCOperand Imm:9>>`
`vsetvli a0, zero, e32,m2`
- `<MCInst #3468 <MCOperand Reg:5> <MCOperand Reg:19>
<MCOperand Reg:21>
<MCOperand Reg:0>>`
`vadd.vv v2, v16, v18`
## Discussion
Some cons:
- We need to mirror all the RVV instructions into pseudo instructions (at
least 7 pseudos for each RVV instruction). MachineInstrs do not seem to be
overloadable per register class.
- Usefulness of `vl` and `sew` operands in the pseudo instructions seems
rather limited: only to communicate between `InstrEmitter` and the
`CustomInserter`.
Pros:
- We can express what we need (`vl`, `vtype`) and all what we want (merging
semantics, whole register operations, explicit vl, optimize vsetvl, etc).
## Acknowledgements
We want to acknowledge the SiFive team who has been collaborating with us.
They have provided very valuable feedback during the internal discussions
we have had while shaping this proposal.
This work has been done as part of the European Processor Initiative
project. The European Processor Initiative (EPI) (FPA: 800928) has received
funding from the European Union’s Horizon 2020 research and innovation
programme under grant agreement EPI-SGA1: 826647
Kind regards,
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20201016/287d40ef/attachment-0001.html>