[cfe-dev] Fixed Point Arithmetic Proposal

[Bevin Hansson via cfe-dev]

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