openpower/sv/branches.mdwn

   1 # SVP64 Branch Conditional behaviour
   2
   3 Links
   4
   5 * <https://bugs.libre-soc.org/show_bug.cgi?id=664>
   6 * <http://lists.libre-soc.org/pipermail/libre-soc-dev/2021-August/003416.html>
   7 * [[openpower/isa/branch]]
   8
   9 Scalar 3.0B Branch Conditional operations, `bc`, `bctar` etc. test a Condition Register.
  10 When doing so in a Vector Context, it is quite reasonable and logical to test a *Vector* of
  11 CR Fields. In 3D Shader binaries, which are inherently parallelised
  12 and predicated, testing all or some results and branching based on
  13 multiple tests is extremely common.
  14 Therefore, `sv.bc` and other Vector-aware Branch Conditional instructions are worth
  15 including.
  16
  17 The `BI` field of Branch Conditional operations is five bits,
  18 in scalar v3.0B this would select one bit of the 32 bit CR.
  19 In SVP64 there are 16 32 bit CRs, containing 128 4-bit CR Fields.
  20 Therefore, the 2 LSBs of `BI` select the bit from the CR Field, and the
  21 top 3 bits are extended to either scalar or vector and to
  22 select CR Fields 0..127 as specified
  23 in SVP64 [[sv/svp64/appendix]]
  24
  25 When considering an "array" of branches, there are two useful modes:
  26
  27 * Branch takes place on the first CR test to succeed
  28   (a Great Big OR of all condition tests)
  29 * Branch takes place only if **all** CR tests succeed:
  30   a Great Big AND of all condition tests
  31   (including those where the predicate is masked out
  32    and the corresponding CR Field is considered to be
  33    set to `SNZ`)
  34
  35 In SVP64 Horizontal-First Mode, the first failure
  36 in ALL mode (Great Big AND) results in early exit: no more updates to
  37 CTR occur (if requested); no branch occurs. Likewise
  38 for non-ALL mode (Great Big Or) on first success early
  39 exit also occurs, however this time with the Branch proceeding.
  40 In both cases the testing of the Vector of CRs should be
  41 done in linear sequential order (or in REMAP re-sequenced order):
  42 such that tests beyond the exit point are *not* carried out.
  43
  44 In Vertical-First Mode, the `ALL` bit should
  45 not be used.  If set, behaviour is `UNDEFINED`.
  46 (*The reason is that Vertical-First hints may permit
  47 multiple elements up to hint length to be executed
  48 in parallel, however the number is entirely up to
  49 implementors.  Attempting to test an arbitrary
  50 indeterminate number of Conditional tests is impossible
  51 to define, and efforts to enforce such defined behaviour
  52 interfere with Vertical-First mode parallel
  53 opportunistic behaviour.*)
  54
  55 In `svstep` mode,
  56 the whole CR Field, part of which is
  57 selected by `BI` (top 3 bits) is updated based on
  58 incrementing srcstep and dststep, and performing the
  59 same tests as [[sv/svstep]], following which the Branch
  60 Conditional instruction proceeds as normal (reading
  61 and testing the CR bit just updated, if the relevant
  62 `BO` bit is set).  Note that the SVSTATE fields
  63 are still updated, and the CR field still updated,
  64 even if the `BO` bits do not require CR testing.
  65
  66 Predication in both INT and CR modes may be applied to
  67 `sv.bc` and other SVP64 Branch Conditional operations,
  68 exactly as they may be applied to other SVP64 operations.
  69 When `sz` is zero, any masked-out Branch-element operations
  70 are not executed, exactly like all other SVP64
  71 operations.
  72
  73 However when `sz` is non-zero, this normally requests insertion
  74 of a zero in place of the input data, when the relevant predicate
  75 mask bit is zero.  This would mean that a zero is inserted in
  76 place of `CR[BI+32]` for testing against `BO`, which may not
  77 be desirable in all circumstances.  Therefore, an extra field
  78 is provided `SNZ`, which, if set, will insert a **one** in
  79 place of a masked-out element instead of a zero.
  80
  81 (*Note: Both options are provided because it is useful to
  82 deliberately cause the Branch-Conditional Vector testing
  83 to fail at a specific point, controlled by the Predicate
  84 mask. This is particularly useful in `VLSET` mode, which
  85 will truncate SVSTATE.VL at the point of the first failed
  86 test.*)
  87
  88 SVP64 RM `MODE` for Branch Conditional:
  89
  90 | 0-1 |  2  |  3   4  |  description              |
  91 | --- | --- |---------|-------------------------- |
  92 | 00  | SNZ |  ALL sz | normal mode                      |
  93 | 01  | VLI |  ALL sz | VLSET mode                      |
  94 | 10  | SNZ |  ALL sz | svstep mode                      |
  95 | 11  | VLI |  ALL sz | svstep VLSET mode, in Horizontal-First        |
  96 | 11  | VLI |  SNZ sz | svstep VLSET mode, in Vertical-First    |
  97
  98 Fields:
  99
 100 * **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.
 101 * **ALL** when set, all branch conditional tests must pass in order for
 102 the branch to succeed.
 103 * **VLI** In VLSET mode, VL is set equal (truncated) to the first branch
 104 which succeeds.  If VLI (Vector Length Inclusive) is clear, VL is truncated
 105 to *exclude* the current element, otherwise it is included. SVSTATE.MVL is not changed.
 106
 107 svstep mode will run an increment of SVSTATE srcstep and dststep
 108 (which is still useful in Horizontal First Mode).  Unlike `svstep.` however
 109 which updates only CR0 with the testing of REMAP loop progress,
 110 the CR Field is taken from the branch `BI` field, and updated
 111 prior to proceeding to each element branch conditional testing.
 112
 113 Note that, interestingly, due to the useful side-effects of `VLSET` mode
 114 and `svstep` mode it is actually useful to use Branch Conditional even
 115 to perform no actual branch operation, i.e to point to the instruction
 116 after the branch.
 117
 118 In particular, svstep mode is still useful for Horizontal-First Mode
 119 particularly in combination with REMAP. All "loop end" conditions
 120 will be tested on a per-element basis and placed into a Vector of
 121 CRs starting from the point specified by the Branch `BI` field.
 122 This Vector of CR Fields may then be subsequently used as a Predicate
 123 Mask, and, furthermore, if VLSET mode was requested, VL will have
 124 been set to the length of one of the loop endpoints, again as specified
 125 by the bit from the Branch `BI` field.
 126
 127 Also, the unconditional bit `BO[0]` is still relevant when Predication
 128 is applied to the Branch because in `ALL` mode all nonmasked bits have
 129 to be tested. Even when svstep mode or VLSET mode are not used, CTR
 130 may still be decremented by the total number of nonmasked elements.
 131 In short, Vectorised Branch becomes an extremely powerful tool.
 132
 133 Available options to combine:
 134
 135 * `BO[0]` to make an unconditional branch would seem irrelevant if
 136   it were not for predication and for side-effects.
 137 * `BO[1]` to select whether the CR bit being tested is zero or nonzero
 138 * `R30` and `~R30` and other predicate mask options including CR and
 139   inverted CR bit testing
 140 * `sz` and `SNZ` to insert either zeros or ones in place of masked-out
 141   predicate bits
 142 * `ALL` or `ANY` behaviour corresponding to `AND` of all tests and
 143   `OR` of all tests, respectively.
 144
 145 Pseudocode for Horizontal-First Mode:
 146
 147 ```
 148
 149     cond_ok = not SVRMmode.ALL
 150     for srcstep in range(VL):
 151         new_srcstep, CRbits = SVSTATE_NEXT(srcstep)
 152         # select predicate bit or zero/one
 153         if predicate[srcstep]:
 154             # get SVP64 extended CR field 0..127
 155             SVCRf = SVP64EXTRA(BI>>2)
 156             CR{SVCRf+srcstep} = CRbits
 157             testbit = CRbits[BI & 0b11]
 158             # testbit = CR[BI+32+srcstep*4]
 159         else if not SVRMmode.sz:
 160             continue
 161         else
 162             testbit = SVRMmode.SNZ
 163         # actual element test here
 164         el_cond_ok <- BO[0] | ¬(testbit ^ BO[1])
 165         # merge in the test
 166         if SVRMmode.ALL:
 167             cond_ok &= el_cond_ok
 168         else
 169             cond_ok |= el_cond_ok
 170         # test for VL to be set (and exit)
 171         if ~el_cond_ok and VLSET
 172             if SVRMmode.VLI
 173                 SVSTATE.VL = srcstep+1
 174             else
 175                 SVSTATE.VL = srcstep
 176             break
 177         # early exit?
 178         if SVRMmode.ALL:
 179             if ~el_cond_ok:
 180                 break
 181         else
 182             if el_cond_ok:
 183                 break
 184 ```
 185
 186 Pseudocode for Vertical-First Mode:
 187
 188 ```
 189     new_srcstep, CRbits = SVSTATE_NEXT(srcstep)
 190     # select predicate bit or zero/one
 191     if predicate[srcstep]:
 192         # get SVP64 extended CR field 0..127
 193         SVCRf = SVP64EXTRA(BI>>2)
 194         CR{SVCRf+srcstep} = CRbits
 195         testbit = CRbits[BI & 0b11]
 196     else if not SVRMmode.sz:
 197         SVSTATE.srcstep = new_srcstep
 198         exit # no branch testing
 199     else
 200         testbit = SVRMmode.SNZ
 201     # actual element test here
 202     cond_ok <- BO[0] | ¬(testbit ^ BO[1])
 203     # test for VL to be set (and exit)
 204     if ~cond_ok and VLSET
 205         if SVRMmode.VLI
 206             SVSTATE.VL = new_srcstep+1
 207         else
 208             SVSTATE.VL = new_srcstep
 209     SVSTATE.srcstep = new_srcstep
 210 ```