# Reduce mode
+There are two variants here. The first is when the destination is scalar
+and at least one of the sources is Vector. The second is more complex
+and involves map-reduction on vectors.
+
+The first defining characteristic distinguishing Scalar-dest reduce mode
+from Vector reduce mode is that Scalar-dest reduce issues VL element
+operations, whereas Vector reduce mode performs an actual map-reduce
+(tree reduction): typically `O(VL log VL)` actual computations.
+
+The second defining characteristic of scalar-dest reduce mode is that it
+is, in simplistic and shallow terms *serial and sequential in nature*,
+whereas the Vector reduce mode is definitely inherently paralleliseable.
+
+The reason why scalar-dest reduce mode is "simplistically" serial and
+sequential is that in certain circumstances (such as an `OR` operation
+or a MIN/MAX operation) it may be possible to parallelise the reduction.
+
+## Scalar result reduce mode
+
+In this mode, one register is identified as being the "accumulator".
+Scalar reduction is thus categorised by:
+
+* One of the sources is a Vector
+* the destination is a scalar
+* optionally but most usefully when one source register is also the destination
+* That the source register type is the same as the destination register
+ type identified as the "accumulator". scalar reduction on `cmp`,
+ `setb` or `isel` is not possible for example because of the mixture
+ between CRs and GPRs.
+
+Typical applications include simple operations such as `ADD r3, r10.v,
+r3` where, clearly, r3 is being used to accumulate the addition of all
+elements is the vector starting at r10.
+
+ # add RT, RA,RB but when RT==RA
+ for i in range(VL):
+ iregs[RA] += iregs[RB+i] # RT==RA
+
+However, *unless* the operation is marked as "mapreduce", SV ordinarily
+**terminates** at the first scalar operation. Only by marking the
+operation as "mapreduce" will it continue to issue multiple sub-looped
+(element) instructions in `Program Order`.
+
+Other examples include shift-mask operations where a Vector of inserts
+into a single destination register is required, as a way to construct
+a value quickly from multiple arbitrary bit-ranges and bit-offsets.
+Using the same register as both the source and destination, with Vectors
+of different offsets masks and values to be inserted has multiple
+applications including Video, cryptography and JIT compilation.
+
+Subtract and Divide are still permitted to be executed in this mode,
+although from an algorithmic perspective it is strongly discouraged.
+It would be better to use addition followed by one final subtract,
+or in the case of divide, to get better accuracy, to perform a multiply
+cascade followed by a final divide.
+
+Note that single-operand or three-operand scalar-dest reduce is perfectly
+well permitted: both still meet the qualifying characteristics that one
+source operand can also be the destination, which allows the "accumulator"
+to be identified.
+
+## Vector result reduce mode
+
1. limited to single predicated dual src operations (add RT, RA, RB).
triple source operations are prohibited (fma).
2. limited to operations that make sense. divide is excluded, as is
numbering, with a clear linear relationship and mapping existing when
SV is applied.
-## Analysis for compilers
-
-gcc and llvm automatically manage CRs: they are not explicitly accessible even at the assembly level (asm statement). This causes something of an issue even just for basic testing. A solution then is to leverage the following:
-
-* scalar instructions produce scalar CRs.
-* gcc and llvm scalar instructions produce scalar CRs.
-* vector instructions produce vector CRs
-* therefore with the exception of branches there should be a match which does not require heavy modification of gcc
-
-The basic principle being to ensure that Vector attribute tags propagate through to the CRs. For this to worrk all gcc and llvm code must act as if the numbering of CRs is kept entirely looking scalar despite the fact that it is actually vector.
-
-Thus the compiler when referring to CR0 still generates code that it thinks is scalar and thinks a scalar computation created CR0 but the same code serves double-duty and thus does not need drastic rewrites or modification.
-
-In concrete terms: when the Vector looping proceeds to increment Integer or FP register numbers linearly, `fp1 fp2 fp3...` when `Rc=1` the Vector of CRs should start at `CR1` just as they do in scalar execution but *not overwrite CR2*. Instead proceed to write to at least 8 or 16 CRs before doing so.
-
-Two ways in which this may occur: either for numbering to be linear (`CR8, CR9`) or to be expressed as sub-numbers similar to FP: `CR1.0 CR1.1 ... CR1.15 CR2.0`. Fractional numbering is more natural and intuitive. Here is a table showing progression from 0 to VL-1 when VL=18, should an Integer Vector operation writes first to `CR0`. It is the 16th element before `CR1` is overwritten:
-
- CRn.0 CR0 0 CR1 16 CR2 CR3 CR4 CR5 CR6 CR7
- CRn.1 1 17
- CRn.2 2
- ... ..
- CRn.15 15
-
-This gives an opportunity to minimise modifications to gcc and llvm for any Vectorisation up to a reasonable length of `MVL=16`.
-
## CR EXTRA mapping table and algorithm
Numbering relationships for CR fields are already complex due to being
else:
spec = EXTRA2<<1 | 0b0
if spec[2]:
- # vector constructs "BA[2:4] spec[0:1] 0 BA[0:1]"
- return ((BA >> 2)<<5) | # hi 3 bits shifted up
- (spec[0:1]<<3) | # to make room for these
+ # vector constructs "BA[2:4] spec[0:1] 00 BA[0:1]"
+ return ((BA >> 2)<<6) | # hi 3 bits shifted up
+ (spec[0:1]<<4) | # to make room for these
(BA & 0b11) # CR_bit on the end
else:
- # scalar constructs "0 spec[0:1] BA[0:4]"
+ # scalar constructs "00 spec[0:1] BA[0:4]"
return (spec[0:1] << 5) | BA
Thus, for example, to access a given bit for a CR in SV mode, the v3.0B
CR_index = 7-(BA>>2) # top 3 bits but BE
if spec[2]:
- # vector mode
- CR_index = (CR_index<<3) | (spec[0:1] << 1)
+ # vector mode, 0-124 increments of 4
+ CR_index = (CR_index<<4) | (spec[0:1] << 2)
else:
- # scalar mode
+ # scalar mode, 0-32 increments of 1
CR_index = (spec[0:1]<<3) | CR_index
# same as for v3.0/v3.1 from this point onwards
bit_index = 3-(BA & 0b11) # low 2 bits but BE
projects / libreriscv.git / blobdiff