Beware integer promotion in ANSI C: GraphBLAS is different

The integer promotion rules of ANSI C do not apply to GraphBLAS semirings, and must be avoided when implementing GraphBLAS.  This also has an effect on the results you get in a user application that relies on GraphBLAS.  Don't expect GraphBLAS to act like ANSI C in all cases, since it does not do integer promotion like ANSI C does.

For example, in GraphBLAS, the GrB_PLUS_UINT8 operator has the form TxT->T, where the type T is uint8_t. However, in ANSI C, the type of the result is unsigned int (uint32_t), not uint8_t. That is:

uint8_t x, y ;
// sizeof (x) is 1
// sizeof (x+y) is 4

As a result, the ANSI C built-in operator "+" has the form uint8 x uint8 -> unsigned int. This can be problematic when constructing generated code for a UINT8 semiring. For example consider the MIN_PLUS_UINT8 semiring. Suppose MIN(x,y) is #define'd as:

#define MIN(x,y) (x) < (y) ? (x) : (y)

You might be tempted to consider the fused multiply-add operator as:

uint8_t z, x, y ;
z = MIN (z, x+y) ;

but this generates the wrong result. The value of x+y can exceed UINT8_MAX (which is 255), and then the comparison with z is wrong. What is required for GraphBLAS is the following:

z = MIN (z, (uint8_t) (x+y))

This hasn't caused a bug in any posted version of SuiteSparse:GraphBLAS, because I didn't generate code this way. What I have so far is a temporary variable to compute the multiply-add:

uint8_t t = x + y ;
z = MIN (z, t) ;

In this case, ANSI C and GraphBLAS agree on the result of the computation. I ran across this error when trying to use fused-multiply-add statements in my generated code. That works fine for integer types of 32 bits or more, and for floating-point types. It fails for 8 and 16 bit integers, since the integer promotion disables the implicit mod(t,int_max). It works for booleans (even though sizeof (a || b) is 4, if a and b are bool!), because the int result of a boolean expression is 0 or 1, and the implicit mod has no effect.

I caught this error because of my extensive MATLAB tests, where I have all of GraphBLAS implemented in MATLAB, to check the results of my computations in ANSI C.  The MATLAB expression follows the GraphBLAS API Specification exactly, in Test/GB_spec_mxm.

Implementors beware...

Leave a Reply

Your email address will not be published. Required fields are marked *