add SHAPE / REMAP area to VBLOCK2

[libreriscv.git] / simple_v_extension / vblock_format.mdwn

[[!tag standards]]

# Simple-V (Parallelism Extension Proposal) Vector Block Format

* Copyright (C) 2017, 2018, 2019 Luke Kenneth Casson Leighton
* Status: DRAFTv0.7.1
* Last edited: 2 sep 2019

[[!toc ]]

# Vector Block Format <a name="vliw-format"></a>

This is a way to give Vector and Predication Context to a group of
standard scalar RISC-V instructions, in a highly compact form. Program Execution Order is still preserved (unlike VLIW), just with "context" that would otherwise require much longer instructions.

The format is:

* the standard RISC-V 80 to 192 bit encoding sequence, with bits
  defining the options to follow within the block
* An optional VL Block (16-bit)
* Optional predicate entries (8/16-bit blocks: see Predicate Table, above)
* Optional register entries (8/16-bit blocks: see Register Table, above)
* finally some 16/32/48 bit standard RV or SVPrefix opcodes follow.

Thus, the variable-length format from Section 1.5 of the RISC-V ISA is used
as follows:

[[!inline raw="yes" pages="simple_v_extension/vblock_format_table" ]]

Note: The VL Block format is similar to that used in [[sv_prefix_proposal]].

* Mode 0b00: set VL to the immediate, truncated to not exceed
  MVL. Register rd is also set to the same value, if not x0.
* Mode 0b01: follow [[specification/sv.setvl]] rules, with RVC
  style registers in the range x8-x15 for rs1 and rd.
* Mode 0b10: set both MVL and VL to the immediate. Register rd is also
  set if not x0.
* Mode 0b11: reserved. All fields must be zero.

Mode 0b01 will typically be used to start vectorised loops, where
the VBLOCK instruction effectively embeds an optional "SETSUBVL, SETVL"
sequence (in compact form).

Modes 0b00 and 0b10 will typically not be used so much for loops as they
will be for one-off instructions such as saving the entire register file
to the stack with a single one-off Vectorised and predicated LD/ST,
or as a way to save or restore registers in a function call with a
single instruction.

Unlike in RVV, VL is set (within the limits of MVL) to exactly the value
requested, specifically so that LD/ST-MULTI style behaviour can be done
in a single instruction.

# VBLOCK Prefix

The purpose of the VBLOCK Prefix is to specify the context in which a
block of RV Scalar instructions are "vectorised" and/or predicated.

As there are not very many bits available without going into a prefix
format longer than 16 bits, some abbreviations are used. Two bits are
dedicated to specifying whether the Register and Predicate formats are
16 or 8 bit.

Also, the number of entries in each table is specified with an unusual
encoding, on the basis that if registers are to be Vectorised, it is
highly likely that they will be predicated as well.

The VL Block is optional and also only 16 bits: this because an RVC
opcode is limited by comparison.

The format is explained as follows:

* Bit 7 specifies if the register prefix block format is the full 16 bit format
  (1) or the compact less expressive format (0).
* 8 bit format predicate numbering is implicit and begins from x9. Thus
  it is critical to put blocks in the correct order as required.
* Bit 8 specifies if the predicate block format is 16 bit (1) or 8 bit
  (0).
* Bit 15 specifies if the VL Block is present. If set to 1, the VL Block
  immediately follows the VBLOCK instruction Prefix
* Bits 10 and 11 define how many RegCam entries (0,1,2,4 if bit 7 is 1,
  otherwise 0,2,4,8) follow the (optional) VL Block.
* Bit 9 define how many PredCam entries follow the (optional) RegCam block.
  If pplen is 1, it is equal to rplen. Otherwise, half rplen, rounded up.
* If the exact number of entries are not required, PredCam and RegCam
  entries may be set to all zero to indicate "unused" (no effect).
* Bits 14 to 12 (IL) define the actual length of the instruction: total
  number of bits is 80 + 16 times IL.  Standard RV32, RVC and also
  SVPrefix (P32C/P48/64-\*-Type) instructions fit into this space, after the
  (optional) VL / RegCam / PredCam entries
* In any RVC or 32 Bit opcode, any registers within the VBLOCK-prefixed
  format *MUST* have the RegCam and PredCam entries applied to the
  operation (and the Vectorisation loop activated)
* P48 and P64 opcodes do **not** take their Register or predication
  context from the VBLOCK tables: they do however have VL or SUBVL
  applied (overridden when VLtyp or svlen are set).
* At the end of the VBLOCK Group, the RegCam and PredCam entries
  *no longer apply*.  VL, MAXVL and SUBVL on the other hand remain at
  the values set by the last instruction (whether a CSRRW or the VL
  Block header).
* Although an inefficient use of resources, it is fine to set the MAXVL,
  VL and SUBVL CSRs with standard CSRRW instructions, within a VBLOCK.

All this would greatly reduce the amount of space utilised by Vectorised
instructions, given that 64-bit CSRRW requires 3, even 4 32-bit opcodes:
the CSR itself, a LI, and the setting up of the value into the RS
register of the CSR, which, again, requires a LI / LUI to get the 32
bit data into the CSR.  To get 64-bit data into the register in order
to put it into the CSR(s), LOAD operations from memory are needed!

Given that each 64-bit CSR can hold only 4x PredCAM entries (or 4 RegCAM
entries), that's potentially 6 to eight 32-bit instructions, just to
establish the Vector State!

Not only that: even CSRRW on VL and MAXVL requires 64-bits (even more
bits if VL needs to be set to greater than 32).  Bear in mind that in SV,
both MAXVL and VL need to be set.

By contrast, the VBLOCK prefix is only 16 bits, the VL/MAX/SubVL block is
only 16 bits, and as long as not too many predicates and register vector
qualifiers are specified, several 32-bit and 16-bit opcodes can fit into
the format. If the full flexibility of the 16 bit block formats are not
needed, more space is saved by using the 8 bit formats.

In this light, embedding the VL/MAXVL, PredCam and RegCam CSR entries
into a VBLOCK format makes a lot of sense.

Bear in mind the warning in an earlier section that use of VLtyp or svlen
in a P48 or P64 opcode within a VBLOCK Group will result in corruption
(use) of the STATE CSR, as the STATE CSR is shared with SVPrefix. To
avoid this situation, the STATE CSR may be copied into a temp register
and restored afterwards.

# Register Table Format

The register table format is covered in the main [[specification]],
included here for convenience:

[[!inline raw="yes" pages="simple_v_extension/reg_table_format" ]]

# Predicate Table Format

The predicate table format is covered in the main [[specification]],
included here for convenience:

[[!inline raw="yes" pages="simple_v_extension/pred_table_format" ]]

# Swizzle Table Format<a name="swizzle_format"></a>

The swizzle table format is included here for convenience:

[[!inline raw="yes" pages="simple_v_extension/swizzle_table_format" ]]

Swizzle blocks are only accessible using the "VBLOCK2" format.

# REMAP Area Format<a name="remap_format"></a>

The REMAP area is divided into two areas:

* Register-to-SHAPE.  This defines which registers have which shapes.
  Each entry is 8-bits in length.
* SHAPE Table entries.  These are 32-bits in length and are aligned
  to (start on) a 16 bit boundary.

REMAP Table Entries:

| 7:5      | 4:0    |
| -------- | ------ |
| shapeidx | regnum |

When both shapeidx and regnum are zero, this indicates the end of the
REMAP Register-to-SHAPE section.  The REMAP Table section size is then
aligned to a 16-bit boundary.  32-bit SHAPE Table Entries then fill the
remainder of the REMAP area, and are indexed in order by shapeidx.

In this way, multiple registers may share the same "shape" characteristics.

# SHAPE Table Format<a name="shape_format"></a>

The shape table format is included here for convenience:

[[!inline raw="yes" pages="simple_v_extension/shape_table_format" ]]

See [[simple_v_extension/remap]] for full details on how SHAPE applies,
including pseudo-code.

REMAP Shape blocks are only accessible using the "VBLOCK2" format.

# CSRs:

The CSRs needed, in addition to those from the main [[specification]] are:

* pcvblk
* mepcvblk
* sepcvblk
* uepcvblk
* hepcvblk

To greatly simplify implementations, which would otherwise require a
way to track (cache) VBLOCK instructions, it is required to treat the
VBLOCK group as a separate sub-program with its own separate PC. The
sub-pc advances separately whilst the main PC remains "frozen", pointing
at the beginning of the VBLOCK instruction (not to be confused with how
VL works, which is exactly the same principle, except it is VStart in
the STATE CSR that increments).

This has implications, namely that a new set of CSRs identical to (x)epc
(mepc, srpc, hepc and uepc) must be created and managed and respected
as being a sub extension of the (x)epc set of CSRs.  Thus, (x)epcvblk CSRs
must be context switched and saved / restored in traps.

The srcoffs and destoffs indices in the STATE CSR may be similarly
regarded as another sub-execution context, giving in effect two sets of
nested sub-levels of the RISCV Program Counter (actually, three including
SUBVL and ssvoffs).

# PCVBLK CSR Format

Using PCVBLK to store the progression of decoding and subsequent execution
of opcodes in a VBLOCK allows a simple single issue design to only need to
fetch 32 or 64 bits from the instruction cache on any given clock cycle.

*(This approach also alleviates one of the main concerns with the VBLOCK
Format: unlike a VLIW engine, a FSM no longer requires full buffering
of the entire VBLOCK opcode in order to begin execution. Future versions
may therefore potentially lift the 192 bit limit).*

To support this option (where more complex implementations may skip some
of these phases), VBLOCK contains partial decode state, that allows a
trap to occur even part-way through decode, in order to reduce latency.

The format is as follows:

| 31:30  | 29    | 28:26 | 25:24 | 23:22 | 21   | 20:5    | 4:0   |
|--------|-------|-------|-------|-------|------|---------|-------|
| status | vlset | 16xil | pplen | rplen | mode | vblock2 | opptr |
| 2      | 1     | 3     | 2     | 2     | 1    | 16      | 5     |

* status is the key field that effectively exposes the inner FSM (Finite
  State Machine) directly.
* status = 0b00 indicates that the processor is not in "VBLOCK Mode". It
  is instead in standard RV Scalar opcode execution mode. The processor
  will leave this mode only after it encounters the beginning of a valid
  VBLOCK opcode.
* status=0b01 indicates that vlset, 16xil, pplen, rplen and mode have
  all been copied directly from the VBLOCK so that they do not need to be
  read again from the instruction stream, and that VBLOCK2 has also been
  read and stored,  if 16xil was equal to 0b111.
* status=0b10 indicates that the VL Block has been read from the instruction
  stream and actioned.  (This means that a SETVL instruction has been
  created and executed).  It also indicates that reading of the
  Predicate, Register and Swizzle Blocks are now being read.
* status=0b11 indicates that the Predicate and Register Blocks have been
  read from the instruction stream (and put into internal Vector Context)
  Simpler implementations are permitted to reset status back to 0b10 and
  re-read the data after return from a trap that happened to occur in the
  middle of a VBLOCK. They are not however permitted to destroy opptr in
  the process, and after re-reading the Predicate and Register Blocks must
  resume execution pointed to by opptr.
* opptr points to where instructions begin in the VBLOCK. 0 indicates
  the start of the opcodes
  (not the start of the VBLOCK),
  and is in multiples of 16 bits (2 bytes).
  This is the equivalent of a Program Counter, for VBLOCKs.
* at the end of a VBLOCK, when the last instruction executes (assuming it
  does not change opptr to earlier in the block), status is reset to 0b00
  to indicate exit from the VBLOCK FSM, and the current Vector Predicate
  and Register Context destroyed (Note: the STATE CSR is **not** altered
  purely by exit from a VBLOCK Context).

During the transition from status=0b00 to status=0b01, it is assumed
that the instruction stream is being read at a mininum of 32 bits at
a time.  Therefore it is reasonable to expect that VBLOCK2 would be
successfully read simultaneously with the initial VBLOCK header.
For this reason there is no separate state in the FSM for updating
of the vblock2 field in PCVBLK.

When the transition from status=0b01 to status=0b10 occurs, actioning the
VL Block state *actually* and literally **must** be as if a SETVL instruction
had occurred.  This can result in updating of the VL and MVL CSRs (and
the VL destination register target).  Note, below, that this means that
a context-switch may save/restore VL and MVL (and the integer register file),
where the remaining tables have no such opportunity.

When status=0b10, and before status=0b11, there is no external indicator
as to how far the hardware has got in the process of reading the
Predicate, Register, and Swizzle Blocks.  Implementations are free to use
any internal means to track progress, however given that if a trap occurs
the read process will need to be restarted (in simpler implementations),
there is no point having external indicators of progress.  By complete
contrast, given that a SETVL actually writes to VL (and MVL), the VL
Block state *has* been actioned and thus would be successfully restored
by a context-switch.

When status=0b11, opptr may be written to using CSRRWI. Doing so will
cause execution to jump within the block, exactly as if PC had been set
in normal RISC-V execution. Writing a value outside of the range of the
instruction block will cause an illegal instruction exception. Writing
a value (any value) when status is not 0b11 likewise causes an illegal
instruction exception. To be clear: CSRRWI PCVBLK does **not** have the same
behaviour as CSRRW PCVBLK.

In privileged modes, obviously the above rules do not apply to the completely
separate (x)ePCVBLK CSRs because these are (inactive) *copies* of state,
not the actual active PCVBLK. Writing to PCVBLK during a trap however,
clearly the rules must apply.

If PCVBLK is written to with CSRRW, the same rules apply, however the
entire register in rs1 is treated as the new opptr.

Note that the value returned in the register rd is the *full* PCVBLK,
not just the opptr part.

# Limitations on instructions

As the pcvblk CSR is relative to the beginning of the VBLOCK, branch
and jump opcodes MUST NOT be used to point to a location inside a block:
only at the beginning of an opcode (including another VBLOCK, including
the current one). However, setting the PCVBLK CSR is permitted, to
unconditionally jump to any opcode within a block.

Also: calling subroutines is likewise not permitted, because PCVBLK
context cannot be atomically reestablished on return from the function.

ECALL, on the other hand, which will cause a trap that saves and restores
the full state, is permitted.

Prohibited instructions will cause an illegal instruction trap. If at
that point, software is capable of then working out how to emulate a
branch or function call successfully, by manipulating (x)ePCVBLK and
other state, it is not prohibited from doing so.

To reiterate: a normal jump, normal conditional branch and a normal
function call may only be taken by letting the VBLOCK group finish,
returning to "normal" standard RV mode, and then using standard RVC,
32 bit or P48/64-\*-type opcodes.

The exception to this rule is if the branch or jump within the VBLOCK is back to the start of the same VBLOCK. If this is used, the VBLOCK is, clearly, to be re-executed, including any optional VL blocks and any predication, register table context etc.

Given however that the tables are already established, it is only the VL block that needs to be re-run.  The other tables may be left as-is.

# Links

* <https://groups.google.com/d/msg/comp.arch/yIFmee-Cx-c/jRcf0evSAAAJ>
* <http://lists.libre-riscv.org/pipermail/libre-riscv-dev/2019-June/001824.html>
* <http://lists.libre-riscv.org/pipermail/libre-riscv-dev/2019-June/001880.html>

# Open Questions:

* Is it necessary to stick to the RISC-V 1.5 format?  Why not go with
  using the 15th bit to allow 80 + 16\*0bnnnn bits?  Perhaps to be sane,
  limit to 256 bits (16 times 0-11).
* Could a "hint" be used to set which operations are parallel and which
  are sequential?
* Could a new sub-instruction opcode format be used, one that does not
  conform precisely to RISC-V rules, but *unpacks* to RISC-V opcodes?
  no need for byte or bit-alignment
* Could a hardware compression algorithm be deployed?  Quite likely,
  because of the sub-execution context (sub-VBLOCK PC)