(no commit message)

[libreriscv.git] / openpower / sv / branches.mdwn

# SVP64 Branch Conditional behaviour

**DRAFT STATUS**

Please note: SVP64 Branch instructions should be
considered completely separate and distinct from
standard scalar OpenPOWER-approved v3.0B branches.
**v3.0B branches are in no way impacted, altered,
changed or modified in any way, shape or form by
the SVP64 Vectorised Variants**.

Links

* <https://bugs.libre-soc.org/show_bug.cgi?id=664>
* <http://lists.libre-soc.org/pipermail/libre-soc-dev/2021-August/003416.html>
* [[openpower/isa/branch]]

Scalar 3.0B Branch Conditional operations, `bc`, `bctar` etc. test a
Condition Register.  When doing so in a Vector Context, it is quite
reasonable and logical to test and Branch on a *Vector* of CR Fields
which have just been calculated from a *Vector* of results. In 3D Shader
binaries, which are inherently parallelised and predicated, testing all or
some results and branching based on multiple tests is extremely common,
and a fundamental part of Shader Compilers.  Therefore, `sv.bc` and
other Vector-aware Branch Conditional instructions are a high priority
for 3D GPUs.

The `BI` field of Branch Conditional operations is five bits, in scalar
v3.0B this would select one bit of the 32 bit CR.  In SVP64 there are
16 32 bit CRs, containing 128 4-bit CR Fields.  Therefore, the 2 LSBs of
`BI` select the bit from the CR Field (EQ LT GT SO), and the top 3 bits
are extended to either scalar or vector and to select CR Fields 0..127
as specified in SVP64 [[sv/svp64/appendix]]

When considering an "array" of branches, there are four useful modes:
AND, OR, NAND and NOR of all Conditions.
NAND and NOR may be synthesised by
inverting `BO[2]` which just leaves two modes:

* Branch takes place on the first CR test to succeed
  (a Great Big OR of all condition tests)
* Branch takes place only if **all** CR tests succeed:
  a Great Big AND of all condition tests
  (including those where the predicate is masked out
   and the corresponding CR Field is considered to be
   set to `SNZ`)

In SVP64 Horizontal-First Mode, the first failure in ALL mode (Great Big
AND) results in early exit: no more updates to CTR occur (if requested);
no branch occurs, and LR is not updated (if requested). Likewise for
non-ALL mode (Great Big Or) on first success early exit also occurs,
however this time with the Branch proceeding.  In both cases the testing
of the Vector of CRs should be done in linear sequential order (or in
REMAP re-sequenced order): such that tests that are sequentially beyond
the exit point are *not* carried out. (*Note: it is standard practice in
Programming languages to exit early from conditional tests, however
a little unusual to consider in an ISA that is designed for Parallel
Vector Processing. The reason is to have strictly-defined guaranteed
behaviour*)

In Vertical-First Mode, the `ALL` bit should not be used.  If set,
behaviour is `UNDEFINED`.  (*The reason is that Vertical-First hints may
permit multiple elements up to hint length to be executed in parallel,
however the number is entirely up to implementors.  Attempting to test
an arbitrary indeterminate number of Conditional tests is impossible
to define, and efforts to enforce such defined behaviour interfere with
Vertical-First mode parallel opportunistic behaviour.*)

In `svstep` mode, srcstep and dststep are incremented, and then
tested exactly as in  [[sv/svstep]]. When Rc=1 the test results
are wtitten into the whole CR Field (the exact same one
about to be tested by the Branch Condition). Following the svstep
update, the
Branch Conditional instruction proceeds as normal (reading and testing
the CR bit just updated, if the relevant `BO` bit is set).  Note that
the SVSTATE srcstep and dststep fields are still updated
and the CR field still updated, even if `BO[0]` is set.

Predication in both INT and CR modes may be applied to `sv.bc` and other
SVP64 Branch Conditional operations, exactly as they may be applied to
other SVP64 operations.  When `sz` is zero, any masked-out Branch-element
operations are not executed, exactly like all other SVP64 operations.

However when `sz` is non-zero, this normally requests insertion of a zero
in place of the input data, when the relevant predicate mask bit is zero.
This would mean that a zero is inserted in place of `CR[BI+32]` for
testing against `BO`, which may not be desirable in all circumstances.
Therefore, an extra field is provided `SNZ`, which, if set, will insert
a **one** in place of a masked-out element instead of a zero.

(*Note: Both options are provided because it is useful to deliberately
cause the Branch-Conditional Vector testing to fail at a specific point,
controlled by the Predicate mask. This is particularly useful in `VLSET`
mode, which will truncate SVSTATE.VL at the point of the first failed
test.*)

SVP64 RM `MODE` (includes `ELWIDTH` and `ELWIDTH_SRC` bits) for Branch Conditional:

| 4 | 5 | 6 | 7 | 19 | 20 |  21 | 22   23 |  description        |
| - | - | - | - | -- | -- | --- |---------|-------------------- |
|ALL|LRu| / | / | 0  | 0  | /   |  SNZ sz | normal mode         |
|ALL|LRu| / |VSb| 0  | 1  | VLI |  SNZ sz | VLSET mode          |
|ALL|LRu|BRc| / | 1  | 0  | /   |  SNZ sz | svstep mode         |
|ALL|LRu|BRc|VSb| 1  | 1  | VLI |  SNZ sz | svstep+VLSET mode   |

Fields:

* **sz**  if predication is enabled will put 4 copies of `SNZ` in place of
  the src CR Field when the predicate bit is zero.  otherwise the element
  is ignored or skipped, depending on context.
* **ALL** when set, all branch conditional tests must pass in order for
  the branch to succeed.
* **VLI** Identical to Data-dependent Fail-First mode.
  In VLSET mode, VL is set equal (truncated) to the first point
  where, assuming Conditions are tested sequentially, the  branch succeeds
  *or fails* depending if VSb is set.
  If VLI (Vector Length Inclusive) is clear,
  VL is truncated to *exclude* the current element, otherwise it is
  included. SVSTATE.MVL is not changed: only VL.
* **LRu**: Link Register Update. When set, Link Register will
  only be updated if the Branch Condition succeeds. This avoids
  destruction of LR during loops.
* **BRc** Branch variant of Rc. Instructs svstep testing to overwrite
  the CR Field about to be tested
* **VSb** is most relevant for Vertical-First VLSET Mode. After testing,
  if VSb is set, VL is truncated if the branch succeeds.  If VSb is clear,
  VL is truncated if the branch did **not** take place.

svstep mode will run an increment of SVSTATE srcstep and dststep
(which is still useful in Horizontal First Mode).  Unlike `svstep.`
however which updates only CR0 with the testing of REMAP loop progress,
the CR Field is taken from the branch `BI` field, and, if `BRc`
is set, updated prior to
proceeding to each element branch conditional testing.
* This implies that the prior contents of the CR Vector are ignored*
when `BRc` is set.

Note that, interestingly, due to the useful side-effects of `VLSET` mode
and `svstep` mode it is actually useful to use Branch Conditional even
to perform no actual branch operation, i.e to point to the instruction
after the branch.

`VLSET` mode with Vertical-First is particularly unusual. Vertical-First
is used for explicit looping, where the looping is to terminate if
the end of the Vector, VL, is reached. If however that loop is terminated
early because VL is truncated, VLSET with Vertical-First becomes
meaningless.  Therefore, the option to decide whether truncation should
occur if the branch succeeds *or* if the branch condition fails allows
for flexibility required.

In particular, svstep mode is still useful for Horizontal-First Mode
particularly in combination with REMAP. All "loop end" conditions
will be tested on a per-element basis and placed into a Vector of CRs
starting from the point specified by the Branch `BI` field.  This Vector
of CR Fields may then be subsequently used as a Predicate Mask, and,
furthermore, if VLSET mode was requested, VL will have been set to the
length of one of the loop endpoints, again as specified by the bit from
the Branch `BI` field.

Also, the unconditional bit `BO[0]` is still relevant when Predication
is applied to the Branch because in `ALL` mode all nonmasked bits have
to be tested. Even when svstep mode or VLSET mode are not used, CTR
may still be decremented by the total number of nonmasked elements.
In short, Vectorised Branch becomes an extremely powerful tool.

Available options to combine:

* `BO[0]` to make an unconditional branch would seem irrelevant if
  it were not for predication and for side-effects.
* `BO[1]` to select whether the CR bit being tested is zero or nonzero
* `R30` and `~R30` and other predicate mask options including CR and
  inverted CR bit testing
* `sz` and `SNZ` to insert either zeros or ones in place of masked-out
  predicate bits
* `ALL` or `ANY` behaviour corresponding to `AND` of all tests and
  `OR` of all tests, respectively.

In addition to the above, it is necessary to select whether, in `svstep`
mode, the Vector CR Field is to be overwritten or not: in some cases
it is useful to know but in others all that is needed is the branch itself.

Pseudocode for Horizontal-First Mode:

```
cond_ok = not SVRMmode.ALL
for srcstep in range(VL):
    # select predicate bit or zero/one
    if predicate[srcstep]:
        # get SVP64 extended CR field 0..127
        SVCRf = SVP64EXTRA(BI>>2)
        if svstep_mode then
            new_srcstep, CRbits = SVSTATE_NEXT(srcstep)
            if BRc = 1 then # CR Vectorised overwritr
                CR{SVCRf+srcstep} = CRbits
        else
            CRbits = CR{SVCRf}
        testbit = CRbits[BI & 0b11]
        # testbit = CR[BI+32+srcstep*4]
    else if not SVRMmode.sz:
        continue
    else
        testbit = SVRMmode.SNZ
    # actual element test here
    el_cond_ok <- BO[0] | ¬(testbit ^ BO[1])
    # merge in the test
    if SVRMmode.ALL:
        cond_ok &= el_cond_ok
    else
        cond_ok |= el_cond_ok
    # test for VL to be set (and exit)
    if VLSET and VSb = el_cond_ok then
        if SVRMmode.VLI
            SVSTATE.VL = srcstep+1
        else
            SVSTATE.VL = srcstep
        break
    # early exit?
    if SVRMmode.ALL:
        if ~el_cond_ok:
            break
    else
        if el_cond_ok:
            break
    if svstep_mode then
        SVSTATE.srcstep = new_srcstep
```

Pseudocode for Vertical-First Mode:

```
# get SVP64 extended CR field 0..127
SVCRf = SVP64EXTRA(BI>>2)
if svstep_mode then
    new_srcstep, CRbits = SVSTATE_NEXT(srcstep)
else
    CRbits = CR{SVCRf}
# select predicate bit or zero/one
if predicate[srcstep]:
    if BRc = 1 then # CR0 vectorised
        CR{SVCRf+srcstep} = CRbits
    testbit = CRbits[BI & 0b11]
else if not SVRMmode.sz:
    SVSTATE.srcstep = new_srcstep
    exit # no branch testing
else
    testbit = SVRMmode.SNZ
# actual element test here
cond_ok <- BO[0] | ¬(testbit ^ BO[1])
# test for VL to be set (and exit)
if VLSET and cond_ok = VSb then
    if SVRMmode.VLI
        SVSTATE.VL = new_srcstep+1
    else
        SVSTATE.VL = new_srcstep
if svstep_mode then
    SVSTATE.srcstep = new_srcstep
```

# Example Shader code

```
while(a > 2) {
    if(b < 5)
        f();
    else
        g();
    h();
}
```

which compiles to something like:

```
vec<i32> a, b;
// ...
pred loop_pred = a > 2;
while(loop_pred.any()) {
    pred if_pred = loop_pred & (b < 5);
    if(if_pred.any()) {
        f(if_pred);
    }
label1:
    pred else_pred = loop_pred & ~if_pred;
    if(else_pred.any()) {
        g(else_pred);
    }
    h(loop_pred);
}
```

which will end up as:

```
   sv.cmpi CR60.v a.v, 2      # vector compare a into CR60 vector
   sv.crweird r30, CR60.GT # transfer GT vector to r30
while_loop:
   sv.cmpi CR80.v, b.v, 5     # vector compare b into CR64 Vector
   sv.bc/m=r30/~ALL/sz CR80.v.LT skip_f # skip when none
   # only calculate loop_pred & pred_b because needed in f()
   sv.crand CR80.v.SO, CR60.v.GT, CR80.V.LT # if = loop & pred_b
   f(CR80.v.SO)
skip_f:
   # illustrate inversion of pred_b. invert r30, test ALL
   # rather than SOME, but masked-out zero test would FAIL,
   # therefore masked-out instead is tested against 1 not 0
   sv.bc/m=~r30/ALL/SNZ CR80.v.LT skip_g
   # else = loop & ~pred_b, need this because used in g()
   sv.crternari(A&~B) CR80.v.SO, CR60.v.GT, CR80.V.LT
   g(CR80.v.SO)
skip_g:
   # conditionally call h(r30) if any loop pred set
   sv.bclr/m=r30/~ALL/sz BO[1]=1 h()
   sv.bc/m=r30/~ALL/sz BO[1]=1 while_loop
```