[cfe-dev] Fixed Point Arithmetic Proposal

Tue Apr 24 11:05:28 PDT 2018

*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 ChangesThe
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.8unsigned _Fract .16
unsigned _Accum 16.16unsigned long _Fract .32 unsigned long _Accum
32.32signed short _Fract s.7 signed short _Accum s8.7signed _Fract s.15
signed _Accum s16.15signed 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 _Accumlong _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 _Fracthk: short _Accum uhk: unsigned short _Accum k: _Accum
uk: unsigned _Accumlk: long _Accumulk: 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 typesR: unsigned fract typesk: signed accum
typesK: 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
<http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1169.pdf>[2]
https://gcc.gnu.org/wiki/FixedPointArithmetic
<https://gcc.gnu.org/wiki/FixedPointArithmetic>[3]
https://fuchsia.googlesource.com <https://fuchsia.googlesource.com>[4]
https://en.wikipedia.org/wiki/Q_(number_format)
<https://en.wikipedia.org/wiki/Q_(number_format)>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20180424/74452b00/attachment.html>