Rules for using the restrict keyword in C?

Question

I'm trying to understand when and when not to use the restrict keyword in C and in what situations it provides a tangible benefit.

After reading, "Demystifying The Restrict Keyword", ( which provides some rules of thumb on usage ), I get the impression that when a function is passed pointers, it has to account for the possibility that the data pointed to might overlap (alias) with any other arguments being passed into the function. Given a function:

foo(int *a, int *b, int *c, int n) {
    for (int i = 0; i<n; ++i) {
        b[i] = b[i] + c[i];
        a[i] = a[i] + b[i] * c[i];
    } 
}

the compiler has to reload c in the second expression, because maybe b and c point to the same location. It also has to wait for b to be stored before it can load a for the same reason. It then has to wait for a to be stored and must reload b and c at the beginning of the next loop. If you call the function like this:

int a[N];
foo(a, a, a, N);

then you can see why the compiler has to do this. Using restrict effectively tells the compiler that you will never do this, so that it can drop the redundant load of c and load a before b is stored.

In a different SO post, Nils Pipenbrinck, provides a working example of this scenario demonstrating the performance benefit.

So far I've gathered that it's a good idea to use restrict on pointers you pass into functions which won't be inlined. Apparently if the code is inlined the compiler can figure out that the pointers don't overlap.

Now here's where things start getting fuzzy for me.

In Ulrich Drepper's paper, "What every programmer should know about memory" he makes the statement that, "unless restrict is used, all pointer accesses are potential sources of aliasing," and he gives a specific code example of a submatrix matrix multiply where he uses restrict.

However, when I compile his example code either with or without restrict I get identical binaries in both cases. I'm using gcc version 4.2.4 (Ubuntu 4.2.4-1ubuntu4)

The thing I can't figure out in the following code is whether it needs to be rewritten to make more extensive use of restrict, or if the alias analysis in GCC is just so good that it's able to figure out that none of the arguments alias each other. For purely educational purposes, how can I make using or not using restrict matter in this code - and why?

For restrict compiled with:

gcc -DCLS=$(getconf LEVEL1_DCACHE_LINESIZE) -DUSE_RESTRICT -Wextra -std=c99 -O3 matrixMul.c -o matrixMul

Just remove -DUSE_RESTRICT to not use restrict.

#include <stdlib.h>
#include <stdio.h>
#include <emmintrin.h>

#ifdef USE_RESTRICT
#else
#define restrict
#endif

#define N 1000
double _res[N][N] __attribute__ ((aligned (64)));
double _mul1[N][N] __attribute__ ((aligned (64)))
    = { [0 ... (N-1)] 
    = { [0 ... (N-1)] = 1.1f }};
double _mul2[N][N] __attribute__ ((aligned (64)))
    = { [0 ... (N-1)] 
    = { [0 ... (N-1)] = 2.2f }};

#define SM (CLS / sizeof (double))

void mm(double (* restrict res)[N], double (* restrict mul1)[N], 
        double (* restrict mul2)[N]) __attribute__ ((noinline));

void mm(double (* restrict res)[N], double (* restrict mul1)[N], 
        double (* restrict mul2)[N])
{
 int i, i2, j, j2, k, k2; 
    double *restrict rres; 
    double *restrict rmul1; 
    double *restrict rmul2; 

    for (i = 0; i < N; i += SM)
        for (j = 0; j < N; j += SM)
            for (k = 0; k < N; k += SM)
                for (i2 = 0, rres = &res[i][j],
                    rmul1 = &mul1[i][k]; i2 < SM;
                    ++i2, rres += N, rmul1 += N)
                    for (k2 = 0, rmul2 = &mul2[k][j];
                        k2 < SM; ++k2, rmul2 += N)
                        for (j2 = 0; j2 < SM; ++j2)
                          rres[j2] += rmul1[k2] * rmul2[j2];
}

int main (void)
{

    mm(_res, _mul1, _mul2);

 return 0;
}

Answer 1

Also, GCC 4.0.0-4.4 has a regression bug that causes the restrict keyword to be ignored. This bug was reported as fixed in 4.5 (I lost the bug number though).