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