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