[cfe-dev] Fixed Point Arithmetic Proposal
Bevin Hansson via cfe-dev
cfe-dev at lists.llvm.org
Mon May 21 08:01:34 PDT 2018
Hello Leonard,
In our downstream Clang and LLVM ports, we have implemented support for DSP-C
(http://www.ace.nl/sites/default/files/paper-dsp-c.pdf), a precursor to the
Embedded-C Technical Report. We have added all of the required support to
Clang for lexing, parsing, evaluating and emitting IR for the fixed-point types
given in the specification, as well as new intrinsics to LLVM to facilitate
more efficient/simpler code emission on the target level.
The changes we have made to Clang include:
* New builtin types for the individual fixed-point types
* Configurable sizes and alignments for the types in ASTContext/TargetInfo
* Adding appropriate tokens to the lexer and parser
* Handling the behavior of the types (conversion, etc) in Sema
* Constant evaluation of operations and conversions
* Format specifier checking
* Emitting IR/intrinsics for the operations in CodeGen
The changes we have made to LLVM include:
* Intrinsics for the more complicated operations (see below for a list)
* Rudimentary optimizations (constant folding) for the intrinsics
The fixed-point types are simply scaled integers, so no additions to LLVM's
type system have been made.
We have wanted to upstream these changes, but as the implementation is for
a defunct specification rather than a real TR, and given lackluster reception
for fixed-point support from upstream, we have never really managed to get it
going. We are definitely interested in sharing patches if there is interest.
In DSP-C, the new type specifiers are prefixed with a double underscore
instead of a single underscore + capital, and the _Fract type is named
differently:
* _Fract -> __fixed
* _Accum -> __accum
* _Sat -> __sat
However, there are a number of non-cosmetic differences between the
specifications, as well as between our implementation of the standard
and your suggested implementation that could lead to problems in
normalizing the two.
* The semantics for converting between fixed-point (and fixed-point types and
integer) types differ in rather non-trivial ways. One obvious example
is given in Embedded-C 4.1.4:
fract f = 0.25r;
int i = 3;
f = f * i;
In Embedded-C, this is meant to evaluate to 0.75, but in DSP-C it is a
compilation error. There are no usual arithmetic conversions between
__fixed and int, as either conversion will result in precision loss of
either operand.
The rule given by Embedded-C for usual arithmetic conversion for
fixed-point types in 4.1.4 is:
"the result of the operation is calculated using the values of the
two operands, with their full precision"
This rule is rather difficult to implement generally and efficiently, both
as regular integer operations and natively in hardware. Multiplying a
'long long' with a 'long _Fract' would require the operation to be done in
the equivalent of a Q64.31, which, if implemented as a scaled integer
operation would require an integer type of at least 64+31*2=126 bits.
* In our implementation, the MSB of the unsigned types is a padding bit and
is always zero, similar to the specifications given in Embedded-C 4.1.1.
This means that the value representation of our signed and unsigned types
is normalized (both Q15 for _Fract and unsigned _Fract) allowing for
simpler type conversion and more efficient code emission; if the signed
and unsigned variants of the types have the same scaling, hardware
instructions for operations on signed types can be reused for the unsigned
types. The downside is obviously an unused bit, but this is a price
worth paying.
This is one of the big differences between our implementations, as our
implementation is hardcoded to assume that the scale of the signed and
unsigned variants is the same and that the MSB of the unsigned types
is padding and should/will be cleared after all unsigned operations.
* In order to facilitate efficient code emission for hardware with fixed-
point support, we have added generic intrinsics to LLVM for certain
operations. These are:
* signed multiplication
* signed saturating multiplication
* signed division
* unsigned division
* signed saturating division
* unsigned saturating division
* saturation
* saturating addition
* saturating subtraction
* floating-point to fixed-point conversion
* (saturated left shifts are also included, but due to legacy reasons
these are done with target-specific intrinsics. this is easily
amended.)
Other operations are emitted as pure IR (e.g. non-saturating fixed-point
conversion) or by a combination of these intrinsics and IR (e.g.
unsigned multiplication).
We have written an LLVM pass that converts these intrinsics into pure
IR for architectures that do not support them.
Getting proper fixed-point support of some form in upstream Clang and LLVM
would be very beneficial for us, and we would be happy to cooperate in
order to make it happen. If you have any questions about our patches or
implementation, don't hesitate to ask!
Regards,
Bevin
More information about the cfe-dev
mailing list