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