Fixed-Point Arithmetic Support

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

Delivery Date

Benefits

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) {

} }}}

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

Modifications Required

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.)

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.

None: FixedPointArithmetic (last edited 2008-01-10 19:39:00 by localhost)