Fixed Point Arithmetic Proposal

The C extensions to support embedded processors defined in chapter 4 of ISO/IEC TR 18037 [1] defines support for fixed-point arithmetic and fixed point data types in C. Fixed-point data values are either fractional data values, or data values with an integral part and a fractional part. Typical usage of fixed-point data values and operations can be found in applications that convert analogue values to digital representations and subsequently apply some filtering algorithm. This is especially common in digital signal processing.

GNU C Compiler (GCC) already implements this extension [2]. We would like to support fixed-point arithmetic in Fuchsia [3], where it could be beneficial in components like drivers which perform signal processing. However, Fuchsia uses Clang/LLVM as its C/C++ toolchain where the fixed-point arithmetic extensions are not yet implemented.

We would like to implement support for fixed-point arithmetic in Clang. Initially we would like to modify the frontend to add support for fixed-point data types, compiler headers (i.e. stdfix.h) and lowering the fixed-point arithmetic to integer. In the future, we might also extend the backend to support fixed-point data types natively in the LLVM IR which would enable more optimizations including lowering to hardware targets that have native support for fixed-point arithmetic.

C Frontend Changes

The following high level changes would be made to Clang:

- Addition of the following fixed-point types (clause 4.1.1):

(Primary fixed-point types)

unsigned short _Fract .8 unsigned short _Accum 8.8

unsigned _Fract .16 unsigned _Accum 16.16

unsigned long _Fract .32 unsigned long _Accum 32.32

signed short _Fract s.7 signed short _Accum s8.7

signed _Fract s.15 signed _Accum s16.15

signed long _Fract s.31 signed long _Accum s32.31

</b>
<b>

(Aliased fixed-point types: these are aliases for the corresponding signed types)

short _Fract short _Accum

_Fract _Accum

long _Fract long _Accum

</b>
<b>

(Saturated fixed-point types)

_Sat unsigned short _Fract _Sat unsigned short _Accum

_Sat unsigned _Fract _Sat unsigned _Accum

_Sat unsigned long _Fract _Sat unsigned long _Accum

_Sat signed short _Fract _Sat signed short _Accum

_Sat signed _Fract _Sat signed _Accum

_Sat signed long _Fract _Sat signed long _Accum

  • The above bit formats are the recommended formats for a typical desktop processor (Annex A.3), though the integral and fractional bit lengths can be adjusted with the macros under clause 7.18a.3.

  • The standard does not explicitly require equivalent fixed-point support for the long long type (Annex A.1.1.3). We would need to decide on a minimal bit format for the corresponding long long types.

  • The underlying bits of each type are divided into padding, fractional, integral, and sign bits. Represented in Q notation [4], the minimal number of bits assigned to each type are given above. The number of integral and fractional bits can be assigned through preprocessor macros (clause 7.18a.3). Recommended bit layouts are provided in Annex A.3. Specific restrictions on any other custom layouts for these types are given in clause 6.2.6.3.

- Natural spelling of the keywords _Fract (fract), _Accum (accum), and _Sat (sat) defined in (clause 4.1.8). - Support for pragmas FX_FRACT_OVERFLOW and FX_ACCUM_OVERFLOW for controlling overflow in the absence of an explicit saturating fixed-point type (clause 4.1.3). The states of these pragmas are SAT and DEFAULT where SAT enables saturated rounding for the default _Fract and _Accum types. DEFAULT is implementation specific and will simply be a modular wraparound. - Support for conversion between signed/unsigned fixed-point types and integral or floating point types (clause 4.1.4).
  • Signed fixed-point + unsigned fixed-point = signed fixed-point

  • Fixed-point + integral = fixed-point

  • Fixed-point + floating-point = floating-point

  • Conversion from a fixed point to floating point is unspecified and implementation specific. Since our changes are to the C frontend and the underlying representation of these fixed point types are integers, conversion to a float can simply be dividing the fixed point type, as an integer, by the 2^(the number of fractional bits) as a float.

ie. fixed_as_short / ((1 << SACCUM_FBIT) * 1.0)

- Addition of the following fixed-point suffixes (clause 4.1.5):

hr: short _Fract

uhr: unsigned short _Fract

r: _Fract ur unsigned _Fract

lr: long _Fract

ulr: unsigned long _Fract

hk: short _Accum

uhk: unsigned short _Accum

k: _Accum

uk: unsigned _Accum

lk: long _Accum

ulk: unsigned long _Accum

- Support for operations involving fixed-point types (clause 4.1.6)
  • Unary (++, --, +, -, !)

  • ++ and – have their usual meaning of incrementing/decrementing the integral part

  • The 2s complement of a fixed point type is taken with + if it is negative or - if it is positive.

  • The result of logical negation (!) on a fixed point type is 0 if the the operand compares unequal to 0 and 1 if the operand compares equal to 0, with the result as an int.

  • Binary (+, -, *, /, <<, >>)

  • Addition and subtraction are done normally like with integers.

  • a + b, a - b

  • Multiplication is done normally like with integers, but the resulting value is bit shifted right by the number of fractional bits used. Casting to a larger type is necessary to account for storage of the larger resulting value

  • (short)(((int)a * (int)b) >> SACCUM_FBIT)

  • Division is done normally like with integers, but the dividend is bit shifted left by the number of fractional bits used.

  • (short)(((int)a << SACCUM_FBIT) / b)

  • << and >> are defined to be equivalent to multiplication or division by a power of 2.

  • Comparison (<, <=, >=, >, ==, !=)

  • All comparisons are done normally as if the types were integers.

  • Assignment (+=, -=, *=, /=, <<=, >>=)

  • Bitwise NOT (~) and modulo (%) are not supported for fixed-point types.

  • For conversion between different ranked/sized fixed point numbers, the smaller ranked/sized fixed point type is promoted to the higher ranked/sized type.

  • Overflow is calculated according to clause 4.1.3. If the fixed point types are saturated, then the 2 added values are temporarily stored as larger values to account for overflow and rounding to the highest or lowest possible value for that fixed point type.

- Fixed point functions (to be defined under ) (clause 4.1.7, 4.1.8)
  • mulifx, divifx, fxdivi and idivfx (where fx stands for one of the fixed point suffixes)

  • absfx

  • roundfx

  • countlsfx

  • bitsfx (and the respective integer types int_fx_t/uint_fx_t)

  • fxbits

  • strtofxfx

- Format specifiers for fixed-point arguments (clause 4.1.9):

r: signed fract types

R: unsigned fract types

k: signed accum types

K: unsigned accum types

  • Formatting to and from the appropriate decimal notation ([-]ddd.ddd) will be similar to that of formatting a floating point number.

Implementation Details

Expected changes include:

  • _Fract, _Accum, and _Sat will need to be added as tokens.

  • The lexer and parser will need to accept these tokens.

  • Type nodes will need to be created to represent _Fract, _Accum, and _Sat.

  • Underlying logic for builtin operations between fixed-point types and other types (addition, multiplication, etc.).

  • The <stdfix.h> header which will include helper functions and natural spelling for fixed-point types.

  • Formatted IO functions in libc to support the new format specifies for fixed point arguments.

All changes will also be made to Clang only. Expanding this into LLVM will be considered down the road.

[1] http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1169.pdf

[2] https://gcc.gnu.org/wiki/FixedPointArithmetic

[3] https://fuchsia.googlesource.com

[4] https://en.wikipedia.org/wiki/Q_(number_format)

Sorry about the formatting in the previous one. Here's an updated one in
plain text.

The C extensions to support embedded processors defined in chapter 4 of
ISO/IEC TR 18037 [1] defines support for fixed-point arithmetic and fixed
point data types in C. Fixed-point data values are either fractional data
values, or data values with an integral part and a fractional part. Typical
usage of fixed-point data values and operations can be found in
applications that convert analogue values to digital representations and
subsequently apply some filtering algorithm. This is especially common in
digital signal processing.

GNU C Compiler (GCC) already implements this extension [2]. We would like
to support fixed-point arithmetic in Fuchsia [3], where it could be
beneficial in components like drivers which perform signal processing.
However, Fuchsia uses Clang/LLVM as its C/C++ toolchain where the
fixed-point arithmetic extensions are not yet implemented.

We would like to implement support for fixed-point arithmetic in Clang.
Initially we would like to modify the frontend to add support for
fixed-point data types, compiler headers (i.e. stdfix.h) and lowering the
fixed-point arithmetic to integer. In the future, we might also extend the
backend to support fixed-point data types natively in the LLVM IR which
would enable more optimizations including lowering to hardware targets that
have native support for fixed-point arithmetic.

# C Frontend Changes

The following high level changes would be made to Clang:

- Addition of the following fixed-point types (clause 4.1.1):

(Primary fixed-point types)
unsigned short _Fract .8 unsigned short _Accum 8.8
unsigned _Fract .16 unsigned _Accum 16.16
unsigned long _Fract .32 unsigned long _Accum 32.32
signed short _Fract s.7 signed short _Accum s8.7
signed _Fract s.15 signed _Accum s16.15
signed long _Fract s.31 signed long _Accum s32.31

(Aliased fixed-point types: these are aliases for the corresponding signed
types)
short _Fract short _Accum
_Fract _Accum
long _Fract long _Accum

(Saturated fixed-point types)
_Sat unsigned short _Fract _Sat unsigned short _Accum
_Sat unsigned _Fract _Sat unsigned _Accum
_Sat unsigned long _Fract _Sat unsigned long _Accum
_Sat signed short _Fract _Sat signed short _Accum
_Sat signed _Fract _Sat signed _Accum
_Sat signed long _Fract _Sat signed long _Accum

   - The above bit formats are the recommended formats for a typical desktop
processor (Annex A.3), though the integral and fractional bit lengths can
be adjusted with the macros under clause 7.18a.3.

   - The standard does not explicitly require equivalent fixed-point support
for the `long long` type (Annex A.1.1.3). We would need to decide on a
minimal bit format for the corresponding `long long` types.

   - The underlying bits of each type are divided into padding, fractional,
integral, and sign bits. Represented in Q notation [4], the minimal number
of bits assigned to each type are given above. The number of integral and
fractional bits can be assigned through preprocessor macros (clause
7.18a.3). Recommended bit layouts are provided in Annex A.3. Specific
restrictions on any other custom layouts for these types are given in
clause 6.2.6.3.

- Natural spelling of the keywords _Fract (fract), _Accum (accum), and _Sat
(sat) defined in <stdfix.h> (clause 4.1.8).

- Support for pragmas FX_FRACT_OVERFLOW and FX_ACCUM_OVERFLOW for
controlling overflow in the absence of an explicit saturating fixed-point
type (clause 4.1.3). The states of these pragmas are SAT and DEFAULT where
SAT enables saturated rounding for the default _Fract and _Accum types.
DEFAULT is implementation specific and will simply be a modular wraparound.

- Support for conversion between signed/unsigned fixed-point types and
integral or floating point types (clause 4.1.4).
   - Signed fixed-point + unsigned fixed-point = signed fixed-point
   - Fixed-point + integral = fixed-point
   - Fixed-point + floating-point = floating-point
     - Conversion from a fixed point to floating point is unspecified and
implementation specific. Since our changes are to the C frontend and the
underlying representation of these fixed point types are integers,
conversion to a float can simply be dividing the fixed point type, as an
integer, by the 2^(the number of fractional bits) as a float. ie.
`fixed_as_short / ((1 << SACCUM_FBIT) * 1.0)`

- Addition of the following fixed-point suffixes (clause 4.1.5):

hr: short _Fract
uhr: unsigned short _Fract
r: _Fract ur unsigned _Fract
lr: long _Fract
ulr: unsigned long _Fract
hk: short _Accum
uhk: unsigned short _Accum
k: _Accum
uk: unsigned _Accum
lk: long _Accum
ulk: unsigned long _Accum

- Support for operations involving fixed-point types (clause 4.1.6)
   - Unary (++, --, +, -, !)
     - ++ and -- have their usual meaning of incrementing/decrementing the
integral part
     - The 2s complement of a fixed point type is taken with `+` if it is
negative or `-` if it is positive.
     - The result of logical negation (!) on a fixed point type is 0 if the
the operand compares unequal to 0 and 1 if the operand compares equal to 0,
with the result as an int.
   - Binary (+, -, *, /, <<, >>)
     - Addition and subtraction are done normally like with integers.
       - `a + b`, `a - b`
     - Multiplication is done normally like with integers, but the resulting
value is bit shifted right by the number of fractional bits used. Casting
to a larger type is necessary to account for storage of the larger
resulting value
       - `(short)(((int)a * (int)b) >> SACCUM_FBIT)`
     - Division is done normally like with integers, but the dividend is bit
shifted left by the number of fractional bits used.
       - `(short)(((int)a << SACCUM_FBIT) / b)`
     - `<<` and `>>` are defined to be equivalent to multiplication or
division by a power of 2.
   - Comparison (<, <=, >=, >, ==, !=)
     - All comparisons are done normally as if the types were integers.
   - Assignment (+=, -=, *=, /=, <<=, >>=)
   - Bitwise NOT (~) and modulo (%) are not supported for fixed-point types.
   - For conversion between different ranked/sized fixed point numbers, the
smaller ranked/sized fixed point type is promoted to the higher
ranked/sized type.
   - Overflow is calculated according to clause 4.1.3. If the fixed point
types are saturated, then the 2 added values are temporarily stored as
larger values to account for overflow and rounding to the highest or lowest
possible value for that fixed point type.

- Fixed point functions (to be defined under <stdfix.h>) (clause 4.1.7,
4.1.8)
   - mulifx, divifx, fxdivi and idivfx (where fx stands for one of the fixed
point suffixes)
   - absfx
   - roundfx
   - countlsfx
   - bitsfx (and the respective integer types int_fx_t/uint_fx_t)
   - fxbits
   - strtofxfx

- Format specifiers for fixed-point arguments (clause 4.1.9):

r: signed fract types
R: unsigned fract types
k: signed accum types
K: unsigned accum types

   - Formatting to and from the appropriate decimal notation ([-]ddd.ddd)
will be similar to that of formatting a floating point number.

# Implementation Details

Expected changes include:
- _Fract, _Accum, and _Sat will need to be added as tokens.
- The lexer and parser will need to accept these tokens.
- Type nodes will need to be created to represent _Fract, _Accum, and _Sat.
- Underlying logic for builtin operations between fixed-point types and
other types (addition, multiplication, etc.).
- The <stdfix.h> header which will include helper functions and natural
spelling for fixed-point types.
- Formatted IO functions in libc to support the new format specifies for
fixed point arguments.

All changes will also be made to Clang only. Expanding this into LLVM will
be considered down the road.

[1] http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1169.pdf
[2] https://gcc.gnu.org/wiki/FixedPointArithmetic
[3] https://fuchsia.googlesource.com
[4] https://en.wikipedia.org/wiki/Q_(number_format)

The C extensions to support embedded processors defined in chapter 4 of
ISO/IEC TR 18037 [1] defines support for fixed-point arithmetic and fixed
point data types in C.

Just curious, do you know the state of fixed-point arithmetic in C++? I
recall a talk at CPPcon some while ago, but I don't know that it has made
any headway.

All changes will also be made to Clang only. Expanding this into LLVM will
be considered down the road.

"Expanding this into LLVM [later]" implies two things to me. Might mean
more things to somebody else.

First, in the short term the front-end will emit all the scaling operations
explicitly. Does "expanding this into LLVM" include making LLVM understand
scaled types natively? That sounds like a big project.

Second, in the short term the front-end will describe everything in terms of
the same-size same-signedness integer types. I assume you will eventually
teach the debug-info metadata to describe scaled types? DWARF has supported
scaled types since v3, I don't know whether CodeView does also. Adding this
to LLVM should be relatively straightforward.

Thanks,
--paulr

> The C extensions to support embedded processors defined in chapter 4 of
> ISO/IEC TR 18037 [1] defines support for fixed-point arithmetic and

fixed

> point data types in C.

Just curious, do you know the state of fixed-point arithmetic in C++? I
recall a talk at CPPcon some while ago, but I don't know that it has made
any headway.

I believe fixed-point arithmetic currently is only standardized in ISO
N1169 (http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1169.pdf). As of
now, only GCC has implemented it (
https://gcc.gnu.org/wiki/FixedPointArithmetic), though I do not think they
have finished a full implementation of the stdfix library. There are also
lots of open source implementations for fixed point types, but none of them
built into the language except for GCC for now.

> All changes will also be made to Clang only. Expanding this into LLVM

will

> be considered down the road.

"Expanding this into LLVM [later]" implies two things to me. Might mean
more things to somebody else.

First, in the short term the front-end will emit all the scaling

operations

explicitly. Does "expanding this into LLVM" include making LLVM

understand

scaled types natively? That sounds like a big project.

Yes. Initially, we will only be making changes to clang by performing any
scaling through extra llvm instructions when compiling from C to IR.
Expanding into llvm entails adding fixed point types as llvm types
natively, but from what I've been told, this does sound like a big project
to be considered for later. Right now we're focusing on just the C frontend
and not LLVM itself.

Second, in the short term the front-end will describe everything in terms

of

the same-size same-signedness integer types. I assume you will eventually
teach the debug-info metadata to describe scaled types? DWARF has

supported

scaled types since v3, I don't know whether CodeView does also. Adding

this

to LLVM should be relatively straightforward.

We have not considered this, but will look into it. In terms of debug info,
we will record all fixed point types as ints, but we are unsure right now
about scaled types.

Thanks,
Leo

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