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 Branch Conditional operations, `bc`, `bctar` etc. test a Condition Register.
  10 When doing so, 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 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, 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 * Branch takes place only if **all** CR tests succeed
  29   (including those where the predicate is masked out
  30    and the corresponding CR Field is considered to be
  31    set to `SNZ`)
  32
  33 In Vertical-First Mode, the `ALL` bit should
  34 not be used.  If set, behaviour is `UNDEFINED`.
  35 (*The reason is that Vertical-First hints may permit
  36 multiple elements up to hint length to be executed
  37 in parallel, however the number is entirely up to
  38 implementors.  Attempting to test an arbitrary
  39 indeterminate number of Conditional tests is impossible
  40 to define, and efforts to enforce such defined behaviour
  41 interfere with Vertical-First mode parallel behaviour.*)
  42
  43 `svstep` mode is only meaningful in Vertical-First Mode.
  44 The CR Field selected by `BI` is updated based on
  45 incrementing srcstep and dststep, and performing the
  46 same tests as [[sv/svstep]], following which the Branch
  47 Conditional instruction proceeds as normal (reading
  48 and testing the CR bit just updated, if the relevant
  49 `BO` bit is set).  Note that the SVSTATE fields
  50 are still updated, and the CR field still updated,
  51 even if the `BO` bits do not require CR testing.
  52
  53 Predication in both INT and CR modes may be applied to
  54 `sv.bc` and other SVP64 Branch Conditional operations,
  55 exactly as they may be applied to other SVP64 operations.
  56 When `sz` is zero, any masked-out Branch-element operations
  57 are masked-out (not executed), exactly like all other SVP64
  58 operations.
  59
  60 However when `sz` is non-zero, this normally requests insertion
  61 of a zero in place of the input data, when the relevant predicate
  62 mask bit is zero.  This would mean that a zero is inserted in
  63 place of `CR[BI+32]` for testing against `BO`, which may not
  64 be desirable in all circumstances.  Therefore, an extra field
  65 is provided `SNZ`, which, if set, will insert a **one** in
  66 place of a masked-out element instead of a zero.
  67
  68 (*Note: Both options are provided because it is useful to
  69 deliberately cause the Branch-Conditional Vector testing
  70 to fail at a specific point, controlled by the Predicate
  71 mask. This is particularly useful in `VLSET` mode, which
  72 will truncate SVSTATE.VL at the point of the first failed
  73 test.*)
  74
  75 SVP64 RM `MODE` for Branch Conditional:
  76
  77 | 0-1 |  2  |  3   4  |  description              |
  78 | --- | --- |---------|-------------------------- |
  79 | 00  | SNZ |  ALL sz | normal mode                      |
  80 | 01  | VLI |  ALL sz | VLSET mode                      |
  81 | 10  | SNZ |  ALL sz | svstep mode                      |
  82 | 11  | VLI |  ALL sz | svstep VLSET mode                      |
  83
  84 Fields:
  85
  86 * **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.
  87 * **ALL** when set, all branch conditional tests must pass in order for
  88 the branch to succeed.
  89 * **VLI** In VLSET mode, VL is set equal (truncated) to the first branch
  90 which succeeds.  If VLI (Vector Length Inclusive) is clear, VL is truncated
  91 to *exclude* the current element, otherwise it is included. SVSTATE.MVL is not changed.
  92
  93 svstep mode will run an increment of SVSTATE srcstep and dststep
  94 (which is still useful in Horizontal First Mode).  Unlike `svstep.` however
  95 which updates only CR0 with the testing of REMAP loop progress,
  96 the CR Field is taken from the branch `BI` field, and updated
  97 prior to proceeding to each element branch conditional testing.
  98
  99 Note that, interestingly, due to the useful side-effects of `VLSET` mode
 100 and `svstep` mode it is actually useful to use Branch Conditional even
 101 to perform no actual branch operation, i.e to point to the instruction
 102 after the branch.
 103 In particular, svstep mode is still useful for Horizontal-First Mode
 104 particularly in combination with REMAP. All "loop end" conditions
 105 will be tested on a per-element basis and placed into a Vector of
 106 CRs starting from the point specified by the Branch `BI` field.
 107 This Vector of CR Fields may then be subsequently used as a Predicate
 108 Mask, and, furthermore, if VLSET mode was requested, VL will have
 109 been set to the length of one of the loop endpoints, again as specified
 110 by the bit from the Branch `BI` field.
 111
 112 Available options to combine:
 113
 114 * `BO` to select whether the CR bit being tested is zero or nonzero
 115 * `R30` and `~R30` and other predicate mask options including CR and
 116   inverted CR bit testing
 117 * `sz` and `SNZ` to insert either zeros or ones in place of masked-out
 118   predicate bits
 119 * `ALL` or `ANY` behaviour corresponding to `AND` of all tests and
 120   `OR` of all tests, respectively.
 121
 122 Pseudocode for Horizontal-First Mode:
 123
 124 ```
 125    if BO[0]:
 126        cond_ok = 1
 127    else
 128        cond_ok = not SVRMmode.ALL
 129        for srcstep in range(VL):
 130            new_srcstep, CRbits = SVSTATE_NEXT(srcstep)
 131            # select predicate bit or zero/one
 132            if predicate[srcstep]:
 133                # get SVP64 extended CR field 0..127
 134                SVCRf = SVP64EXTRA(BI>>2)
 135                CR{SVCRf+srcstep} = CRbits
 136                testbit = CRbits[BI & 0b11]
 137                # testbit = CR[BI+32+srcstep*4]
 138            else if not SVRMmode.sz:
 139                continue
 140            else
 141                testbit = SVRMmode.SNZ
 142            # actual element test here
 143            el_cond_ok <- ¬(testbit ^ BO[1])
 144            # merge in the test
 145            if SVRMmode.ALL:
 146                cond_ok &= el_cond_ok
 147            else
 148                cond_ok |= el_cond_ok
 149            # test for VL to be set (and exit)
 150            if ~el_cond_ok and VLSET
 151                if SVRMmode.VLI
 152                    SVSTATE.VL = srcstep+1
 153                else
 154                    SVSTATE.VL = srcstep
 155                break
 156            # early exit?
 157            if SVRMmode.ALL:
 158                if ~el_cond_ok:
 159                    break
 160            else
 161                if el_cond_ok:
 162                    break
 163 ```
 164
 165 Pseudocode for Vertical-First Mode:
 166
 167 ```
 168    new_srcstep, CRbits = SVSTATE_NEXT(srcstep)
 169    if BO[0]:
 170        cond_ok = 1
 171    else
 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            CR{SVCRf+srcstep} = CRbits
 177            testbit = CRbits[BI & 0b11]
 178        else if not SVRMmode.sz:
 179            SVSTATE.srcstep = new_srcstep
 180            exit # no branch testing
 181        else
 182            testbit = SVRMmode.SNZ
 183        # actual element test here
 184        cond_ok <- ¬(testbit ^ BO[1])
 185        # test for VL to be set (and exit)
 186        if ~cond_ok and VLSET
 187            if SVRMmode.VLI
 188                SVSTATE.VL = new_srcstep+1
 189            else
 190                SVSTATE.VL = new_srcstep
 191     SVSTATE.srcstep = new_srcstep
 192 ```