1 # SVP64 Branch Conditional behaviour
5 Please note: SVP64 Branch instructions should be
6 considered completely separate and distinct from
7 standard scalar OpenPOWER-approved v3.0B branches.
8 **v3.0B branches are in no way impacted, altered,
9 changed or modified in any way, shape or form by
10 the SVP64 Vectorised Variants**.
14 * <https://bugs.libre-soc.org/show_bug.cgi?id=664>
15 * <http://lists.libre-soc.org/pipermail/libre-soc-dev/2021-August/003416.html>
16 * [[openpower/isa/branch]]
18 Scalar 3.0B Branch Conditional operations, `bc`, `bctar` etc. test a
19 Condition Register. However for parallel processing it is simply impossible
20 to perform multiple independent branches: the Program Counter simply
21 cannot branch to multiple destinations based on multiple conditions.
22 The best that can be done is
23 to test multiple Conditions and make a decision of a *single* branch,
24 based on analysis of a *Vector* of CR Fields
25 which have just been calculated from a *Vector* of results. In 3D Shader
26 binaries, which are inherently parallelised and predicated, testing all or
27 some results and branching based on multiple tests is extremely common,
28 and a fundamental part of Shader Compilers. Therefore, `sv.bc` and
29 other Vector-aware Branch Conditional instructions are a high priority
32 The `BI` field of Branch Conditional operations is five bits, in scalar
33 v3.0B this would select one bit of the 32 bit CR. In SVP64 there are
34 16 32 bit CRs, containing 128 4-bit CR Fields. Therefore, the 2 LSBs of
35 `BI` select the bit from the CR Field (EQ LT GT SO), and the top 3 bits
36 are extended to either scalar or vector and to select CR Fields 0..127
37 as specified in SVP64 [[sv/svp64/appendix]].
39 When considering an "array" of branch-tests, there are four useful modes:
40 AND, OR, NAND and NOR of all Conditions.
41 NAND and NOR may be synthesised by
42 inverting `BO[2]` which just leaves two modes:
44 * Branch takes place on the first CR test to succeed
45 (a Great Big OR of all condition tests)
46 * Branch takes place only if **all** CR tests succeed:
47 a Great Big AND of all condition tests
48 (including those where the predicate is masked out
49 and the corresponding CR Field is considered to be
52 When the CR Fields selected by SVP64 Augmented `BI` is marked as scalar,
53 then as usual the loop ends at the first element tested, after taking
54 predication into consideration. Thus, as usual, when `sz` is zero, srcstep
55 skips forward to the first non-zero predicated element, and only that
56 one element is tested.
58 In SVP64 Horizontal-First Mode, the first failure in ALL mode (Great Big
59 AND) results in early exit: no more updates to CTR occur (if requested);
60 no branch occurs, and LR is not updated (if requested). Likewise for
61 non-ALL mode (Great Big Or) on first success early exit also occurs,
62 however this time with the Branch proceeding. In both cases the testing
63 of the Vector of CRs should be done in linear sequential order (or in
64 REMAP re-sequenced order): such that tests that are sequentially beyond
65 the exit point are *not* carried out. (*Note: it is standard practice in
66 Programming languages to exit early from conditional tests, however
67 a little unusual to consider in an ISA that is designed for Parallel
68 Vector Processing. The reason is to have strictly-defined guaranteed
71 In Vertical-First Mode, the `ALL` bit still applies, but to the elements
72 that are executed up to the Hint length, in parallel batches. See
73 [[sv/setvl]] for the definition of Vertical-First Hint.
75 Predication in both INT and CR modes may be applied to `sv.bc` and other
76 SVP64 Branch Conditional operations, exactly as they may be applied to
77 other SVP64 operations. When `sz` is zero, any masked-out Branch-element
78 operations are not included in condition testing, exactly like all other
79 SVP64 operations. This *includes* side-effects such as decrementing of
80 CTR, which is also skipped on masked-out CR Field elements, when `sz`
83 However when `sz` is non-zero, this normally requests insertion of a zero
84 in place of the input data, when the relevant predicate mask bit is zero.
85 This would mean that a zero is inserted in place of `CR[BI+32]` for
86 testing against `BO`, which may not be desirable in all circumstances.
87 Therefore, an extra field is provided `SNZ`, which, if set, will insert
88 a **one** in place of a masked-out element, instead of a zero.
90 (*Note: Both options are provided because it is useful to deliberately
91 cause the Branch-Conditional Vector testing to fail at a specific point,
92 controlled by the Predicate mask. This is particularly useful in `VLSET`
93 mode, which will truncate SVSTATE.VL at the point of the first failed
96 SVP64 RM `MODE` (includes `ELWIDTH` and `ELWIDTH_SRC` bits) for Branch
99 | 4 | 5 | 6 | 7 | 19 | 20 | 21 | 22 23 | description |
100 | - | - | - | - | -- | -- | --- |---------|-------------------- |
101 |ALL|LRu| / | / | 0 | 0 | / | SNZ sz | normal mode |
102 |ALL|LRu| / |VSb| 0 | 1 | VLI | SNZ sz | VLSET mode |
103 |ALL|LRu|CVh| / | 1 | 0 | / | SNZ sz | CTR mode |
104 |ALL|LRu|CVh|VSb| 1 | 1 | VLI | SNZ sz | CTR+VLSET mode |
108 * **sz** if predication is enabled will put 4 copies of `SNZ` in place of
109 the src CR Field when the predicate bit is zero. otherwise the element
110 is ignored or skipped, depending on context.
111 * **ALL** when set, all branch conditional tests must pass in order for
112 the branch to succeed. When clear, it is the first sequentially
113 encountered successful test that causes the branch to succeed.
114 * **VLI** VLSET is identical to Data-dependent Fail-First mode.
115 In VLSET mode, VL is set equal (truncated) to the first point
116 where, assuming Conditions are tested sequentially, the branch succeeds
117 *or fails* depending if VSb is set.
118 If VLI (Vector Length Inclusive) is clear,
119 VL is truncated to *exclude* the current element, otherwise it is
120 included. SVSTATE.MVL is not changed: only VL.
121 * **LRu**: Link Register Update. When set, Link Register will
122 only be updated if the Branch Condition succeeds. This avoids
123 destruction of LR during loops (particularly Vertical-First
125 * **VSb** is most relevant for Vertical-First VLSET Mode. After testing,
126 if VSb is set, VL is truncated if the branch succeeds. If VSb is clear,
127 VL is truncated if the branch did **not** take place.
129 CTR mode will subtract VL (or VLHint) from CTR rather than just decrement
130 CTR by one. Just as when v3.0B Branch-Conditional saves at
131 least one instruction on tight inner loops through auto-decrementation
132 of CTR, likewise it is also possible to save instruction count for
133 SVP64 loops in both Vertical-First and Horizontal-First Mode.
135 Note that, interestingly, due to the useful side-effects of `VLSET` mode
136 it is actually useful to use Branch Conditional even
137 to perform no actual branch operation, i.e to point to the instruction
139 If VLSET mode was requested with REMAP, VL will have been set to the
140 length of one of the loop endpoints, as specified by the bit from
141 the Branch `BI` field.
143 Also, the unconditional bit `BO[0]` is still relevant when Predication
144 is applied to the Branch because in `ALL` mode all nonmasked bits have
145 to be tested. Even when svstep mode or VLSET mode are not used, CTR
146 may still be decremented by the total number of nonmasked elements.
147 In short, Vectorised Branch becomes an extremely powerful tool.
149 `VLSET` mode with Vertical-First is particularly unusual. Vertical-First
150 is used for explicit looping, where the looping is to terminate if the end
151 of the Vector, VL, is reached. If however that loop is terminated early
152 because VL is truncated, VLSET with Vertical-First becomes meaningless.
153 Therefore, the option to decide whether truncation should occur if the
154 branch succeeds *or* if the branch condition fails allows for flexibility
157 `VLSET` mode with Horizontal-First when `VSb` is clear is still
158 useful, because it can be used to truncate VL to the first predicated
159 (non-masked-out) element.
161 Available options to combine:
163 * `BO[0]` to make an unconditional branch would seem irrelevant if
164 it were not for predication and for side-effects.
165 * `BO[1]` to select whether the CR bit being tested is zero or nonzero
166 * `R30` and `~R30` and other predicate mask options including CR and
167 inverted CR bit testing
168 * `sz` and `SNZ` to insert either zeros or ones in place of masked-out
170 * `ALL` or `ANY` behaviour corresponding to `AND` of all tests and
171 `OR` of all tests, respectively.
173 In addition to the above, it is necessary to select whether, in `svstep`
174 mode, the Vector CR Field is to be overwritten or not: in some cases it
175 is useful to know but in others all that is needed is the branch itself.
177 Pseudocode for Horizontal-First Mode:
180 cond_ok = not SVRMmode.ALL
181 for srcstep in range(VL):
182 # select predicate bit or zero/one
183 if predicate[srcstep]:
184 # get SVP64 extended CR field 0..127
185 SVCRf = SVP64EXTRA(BI>>2)
187 testbit = CRbits[BI & 0b11]
188 # testbit = CR[BI+32+srcstep*4]
189 else if not SVRMmode.sz:
192 testbit = SVRMmode.SNZ
193 # actual element test here
194 el_cond_ok <- BO[0] | ¬(testbit ^ BO[1])
197 cond_ok &= el_cond_ok
199 cond_ok |= el_cond_ok
200 # test for VL to be set (and exit)
201 if VLSET and VSb = el_cond_ok then
203 SVSTATE.VL = srcstep+1
218 Pseudocode for Vertical-First Mode:
221 # get SVP64 extended CR field 0..127
222 SVCRf = SVP64EXTRA(BI>>2)
224 # select predicate bit or zero/one
225 if predicate[srcstep]:
226 if BRc = 1 then # CR0 vectorised
227 CR{SVCRf+srcstep} = CRbits
228 testbit = CRbits[BI & 0b11]
229 else if not SVRMmode.sz:
230 SVSTATE.srcstep = new_srcstep
231 exit # no branch testing
233 testbit = SVRMmode.SNZ
234 # actual element test here
235 cond_ok <- BO[0] | ¬(testbit ^ BO[1])
236 # test for VL to be set (and exit)
237 if VLSET and cond_ok = VSb then
239 SVSTATE.VL = new_srcstep+1
241 SVSTATE.VL = new_srcstep
244 v3.0B branch pseudocode including LRu
247 if (mode_is_64bit) then M <- 0
249 if ¬BO[2] then CTR <- CTR - 1
250 ctr_ok <- BO[2] | ((CTR[M:63] != 0) ^ BO[3])
251 cond_ok <- BO[0] | ¬(CR[BI+32] ^ BO[1])
252 lr_ok <- SVRMmode.LRu
253 if ctr_ok & cond_ok then
254 if AA then NIA <-iea EXTS(BD || 0b00)
255 else NIA <-iea CIA + EXTS(BD || 0b00)
257 if LK & lr_ok then LR <-iea CIA + 4
260 # Example Shader code
272 which compiles to something like:
277 pred loop_pred = a > 2;
278 while(loop_pred.any()) {
279 pred if_pred = loop_pred & (b < 5);
284 pred else_pred = loop_pred & ~if_pred;
285 if(else_pred.any()) {
292 which will end up as:
295 sv.cmpi CR60.v a.v, 2 # vector compare a into CR60 vector
296 sv.crweird r30, CR60.GT # transfer GT vector to r30
298 sv.cmpi CR80.v, b.v, 5 # vector compare b into CR64 Vector
299 sv.bc/m=r30/~ALL/sz CR80.v.LT skip_f # skip when none
300 # only calculate loop_pred & pred_b because needed in f()
301 sv.crand CR80.v.SO, CR60.v.GT, CR80.V.LT # if = loop & pred_b
304 # illustrate inversion of pred_b. invert r30, test ALL
305 # rather than SOME, but masked-out zero test would FAIL,
306 # therefore masked-out instead is tested against 1 not 0
307 sv.bc/m=~r30/ALL/SNZ CR80.v.LT skip_g
308 # else = loop & ~pred_b, need this because used in g()
309 sv.crternari(A&~B) CR80.v.SO, CR60.v.GT, CR80.V.LT
312 # conditionally call h(r30) if any loop pred set
313 sv.bclr/m=r30/~ALL/sz BO[1]=1 h()
314 sv.bc/m=r30/~ALL/sz BO[1]=1 while_loop