**Fixed-Point Arithmetic Support**

- The goal of this project is to add fixed-point arithmetic support to GCC 4.x.

Digital Signal Processors have traditionally supported fixed-point arithmetic in hardware. But more recently, many DSP-enhanced RISC processors are starting to support fixed-point data types as part of their native instruction set. When the precision requirements of the application can be met with fixed-point arithmetic, then this is preferred since it can be smaller and more efficient than floating-point hardware. DSP algorithms often represent the data samples and the coefficients used in the computation as fractional numbers (between -1 and +1) to avoid magnitude growth of a multiplication product. Fractional data type, where there are zero integer bits, is a subset of the more general fixed-point data type.

The current project proposes the addition of the entire Chapter 4 of the Embedded-C spec (http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1169.pdf).

This introduces two new data types: "_Fract" and "_Accum", which can be signed or unsigned with widths including "short", "", "long", and "long long". A new type specifier "_Sat" is used to specify saturating data types. Three new pragmas, FX_FULL_PRECISION, FX_FRACT_OVERFLOW, FX_ACCUM_OVERFLOW, are created to control rounding and saturating behavior.

Unary (++, --, +, -, !), binary (+, -, *, /, <<, >>, +=, -=, *=, /=, <<=, >>=), and comparison (<, <=, >=, >, ==, !=) operators are applied to "_Fract" and "_Accum" data types.

NOTE: special behaviors involving the fixed-point arithmetic are that when mixing integer data with fixed-point data or mixing two different fixed-point data types for binary operators, the compiler should not convert one data type to another data type (ex. from integer to fixed-point) before calculations. The intention is to preserve the precision to yield a useful result.

**Personnel**

- Chao-ying Fu (MIPS)
- Other contributors are welcome and invited to join this project.

**Delivery Date**

- We are currently targeting late 2006 or early 2007, depending on the number of contributors.

**Benefits**

- GCC will have the capability to handle fixed-point arithmetic natively.

For example, if we want to add two Q31 values and saturate the result to the maximum or the minimum, without the fixed-point arithmetic supports, the C code will be like this.

{{{int sat_add1 (int a, int b) {

- long long temp; int sum; temp = (long long) a + (long long) b;
if (((temp & 0x100000000LL)>>1) != (temp & 0x80000000))

- {
if (temp & 0x100000000LL)

sum = 0x7fffffff;

sum = 0x80000000;

- {
sum = (int)temp;

- {

} }}}

Or a simpler way from http://www.cse.lehigh.edu/~caar/papers/hicss.ps .

#define MIN_32 0x80000000 #define MAX_32 0x7fffffff int sat_add1 (int a, int b) { int c; c = a + b; if (((a ^ b) & MIN_32) == 0) { if ((c ^ a) & MIN_32) c = (a < 0) ? MIN_32 : MAX_32; } return c; }

For MIPS DSP ASE which has an instruction to add fractional words with saturation, the above example can be re-written by using an intrinsic as follows.

int sat_add2 (int a, int b) { return __builtin_mips_addq_s_w (a, b); }

However, the intrinsic version of "sat_add2" has some drawbacks. First, the "int" type is used as the "Q31" fractional data type. The compiler may not perform type checking to detect errors. Second, programmers need to memorize intrinsics to utilize. For people who are not familiar with the intrinsics, the C code like "sat_add2" is hard to understand.

Therefore, having the fixed-point arithmetic supports in the compiler, the saturation add example can be written by using the "_Sat _Fract" data type and the "+" operator as follows.

_Sat _Fract sat_add3 (_Sat _Fract a, _Sat _Fract b) { return a + b; }

The fixed-point version of "sat_add3" is pretty obvious and easy to understand.

Another example by using the fixed-point arithmetic is shown as follows. Two arrays of Q31 data are multiplied with saturation and each temporary result is accumulated to a final sum.

_Accum mul_sum (_Sat _Fract *a, _Sat _Fract *b, int length) { int i; _Accum accumulator = 0; for (i = 0; i < length; i++) accumulator += (_Accum)(a[i] * b[i]); return accumulator; }

Without the fixed-point arithmetic supports, programmers need to write explicit C code to perform fractional multiplication (which requires an extra left shift after integer multiplication) and detect the saturation.

**Dependencies**

- None.

**Modifications Required**

- The first phase focuses on the scalar version of the fixed-point data type.

1. Add new machine modes for fixed-point data types. Four classes of machine modes are created:

FRACT_MODE UFRACT_MODE ACCUM_MODE UACCUM_MODE

The decision is based on: a. _Fract has no integer data bits, but _Accum does; b. the signed and unsigned fixed-point data types may have different numbers of data bits. Having separate machine modes makes it easy to generate different instructions and to convert data types based on the current GCC framework. (The status is DONE.)

2. Add new data structures to handle fixed-point data. In "tree.def", we add "FIXED_POINT_TYPE" for fixed-point data types and "FIXED_CST" for fixed-point constants. For "tree_type", we add a saturating flag "saturating_flag". In "rtl.def", we add "const_fixed" for fixed-point constants. A new data structure "fixed_value" is created to store _Fract and _Accum data, which specifies the machine mode and the data bits up to 128 bits. (The status is DONE.)

3. Change the C frontend to accept "_Fract" and "_Accum" and "_Sat". The support data types are:

short _Fract _Fract long _Fract long long _Fract unsigned short _Fract unsigned _Fract unsigned long _Fract unsigned long long _Fract _Sat short _Fract _Sat _Fract _Sat long _Fract _Sat long long _Fract _Sat unsigned short _Fract _Sat unsigned _Fract _Sat unsigned long _Fract _Sat unsigned long long _Fract short _Accum _Accum long _Accum long long _Accum unsigned short _Accum unsigned _Accum unsigned long _Accum unsigned long long _Accum _Sat short _Accum _Sat _Accum _Sat long _Accum _Sat long long _Accum _Sat unsigned short _Accum _Sat unsigned _Accum _Sat unsigned long _Accum _Sat unsigned long long _Accum

(The status is DONE.)

4. Support saturating and non-saturating fixed-point operators using library calls. (The generation of library calls and the library itself is DONE.)

5. Support type conversions. A new tree code "FIXED_CONVERT_EXPR" and four new rtl operators "fixed_all", "sat_fixed_all", "fixed_uint", and "sat_fixed_uint" are created to deal with conversions of all types. (The generation of library calls and the library itself is DONE.)

6. Support fixed-point constants. The compiler frontend needs to parse fixed-point constant suffixes as follows.

hr r lr llr uhr ur ulr ullr hk k lk llk uhk uk ulk ullk

(The parsing of constants and the output of constants are DONE.)

7. Support constant folding of fixed-point values. (The status is DONE.)

8. Support pragmas to control rounding and saturating. (The status is NOT YET implemented.)

9. Support fixed-point operators using real instructions in the backends (ex, MIPS, Blackfin). (The MIPS backend has added several fixed-point operators.)

10. The Embedded-C spec adds many new functions to support fixed-point data types. (The status is NOT YET implemented.)

- The second phase expands to the vector version.

11. Add new vector machine modes. (The status is DONE.)

12. Support vector instructions. (The status is DONE.)

So far, the following files are modified or added.

1. Under gcc/gcc =>

stmt.c function.c except.c dojump.c calls.c tree-vect-generic.c tree-nested.c tree-mudflap.c builtin-types.def c-pretty-print.c config.in configure configure.ac fold-const.c tree-inline.c tree-pretty-print.c expmed.c c-pragma.c expr.c mklibgcc.in optabs.c dwarf2.h dwarf2out.c config.gcc defaults.h c-common.c c-common.h c-decl.c c-parser.c genmodes.c machmode.def mode-classes.def stor-layout.c targhooks.c tree.c tree.h tree.def c-format.h c-tree.h genopinit.c emit-rtl.c rtl.h rtl.c varasm.c output.h target.h final.c target-def.h fixed-value.h fixed-value.c c-typeck.c c-convert.c treestruct.def Makefile.in gimplify.c tree-gimple.c gengenrtl.c gengtype.c c-lex.c

2. Under gcc/libcpp/ =>

expr.c include/cpplib.h

3. Under gcc/config/ =>

fixed-bit.c fixed-bit.h

**Current Status (4/18/2007)**

1. We have implemented Chapter 4 of the Embedded-C spec (n1169.pdf), except the pragma and the stdfix library. We can write a fixed-point program and GCC should be able to compile it correctly.

2. The emulation library is included. So, if a target doesn’t have any instruction patterns, it is still ok to compile and run the fixed-point program. The target just needs to define the sizes of fixed-point types (in “mips.h”) and enable the fixed-point modes by TARGET_SCALAR_MODE_SUPPORTED_P (in “mips.c”). To change the number of integral and fractional bits of fixed-point modes, use ADJUST_IBIT and AJDUST_FIBT (in “mips-modes.def”). To configure GCC, use “—enable-fixed-point”.

3. SIMD variables of fixed-point types are supported. GCC can generate instructions from operators on SIMD fixed-point variables.

**Future Work**

1. Finish the stdfix library. (Pragmas may not be added.)

2. Fine-tuning and optimizations can be added. Right now the expansion of operators just directly generates RTL instructions or calls library functions.

3. Bigger tests are needed to exercise more portions of GCC.