3.2.6 Aliasing and Parallelization

ISO C aliasing can often prevent loops from getting parallelized. Aliasing occurs when there are two possible references to the same memory location. Consider the following example:

Example 3-19  Loop With Two References to the Same Memory Location

void copy(float a[], float b[], int n) {
    int i;
    for (i=0; i < n; i++) {
            a[i] = b[i]; /* S1 */
    }
}

Because variables a and b are parameters, it is possible that a and b might be pointing to overlapping regions of memory, for example, if copy were called as follows:

copy (x[10], x[11], 20);

In the called routine, two successive iterations of the copy loop might be reading and writing the same element of the array x. However, if the routine copy were called as follows, there is no possibility of overlap in any of the 20 iterations of the loop:

copy (x[10], x[40], 20);

The compiler cannot analyze this situation correctly without information about how the routine is called. However, the Oracle Solaris Studio C compiler does provide a keyword extension to standard ISO C to convey this kind of aliasing information. See Restricted Pointers for more information.

3.2.6.1 Array and Pointer References

Part of the aliasing problem is that the C language can define array referencing and definition through pointer arithmetic. In order for the compiler to effectively parallelize loops automatically, all data that is laid out as an array must be referenced using C array reference syntax and not pointers. If pointer syntax is used, the compiler cannot determine the relationship of the data between different iterations of a loop. Thus, the compiler will be conservative and not parallelize the loop.

3.2.6.2 Restricted Pointers

In order for a compiler to effectively perform parallel execution of a loop, it needs to determine whether certain lvalues designate distinct regions of storage. Aliases are lvalues whose regions of storage are not distinct. Determining whether two pointers to objects are aliases is a difficult and time consuming process because it could require analysis of the entire program. Consider function vsq() in the following example:

Example 3-20  Loop With Two Pointers

void vsq(int n, double * a, double * b) {
    int i;
    for (i=0; i<n; i++) {
            b[i] = a[i] * a[i];
    }
}

The compiler can parallelize the execution of the different iterations of the loops if it has determined that pointers a and b access different objects. If there is an overlap in objects accessed through pointers a and b then it would be unsafe for the compiler to execute the loops in parallel. At compile time, the compiler cannot determine whether the objects accessed by a and b overlap by simply analyzing the function vsq(). The compiler might need to analyze the whole program to get this information.

Restricted pointers are used to specify pointers that designate distinct objects so that the compiler can perform pointer alias analysis. The following example shows function vsq() in which function parameters are declared as restricted pointers:

void vsq(int n, double * restrict a, double * restrict b)

Pointers a and b are declared as restricted pointers, so the compiler knows that a and b point to distinct regions of storage. With this alias information, the compiler is able to parallelize the loop.

The keyword restrict is a type-qualifier, like volatile, and it shall only qualify pointer types. There are situations in which you may not want to change the source code. You can specify that pointer-valued function-parameters be treated as restricted pointers by using the following command line option:

-xrestrict=[func1,…,funcn]

If a function list is specified, then pointer parameters in the specified functions are treated as restricted; otherwise, all pointer parameters in the entire C file are treated as restricted. For example, -xrestrict=vsq, qualifies the pointers a and b given in the first example of the function vsq() with the keyword restrict.

It is critical that you use restrict correctly. If pointers qualified as restricted pointers point to objects which are not distinct, the compiler can incorrectly parallelize loops resulting in undefined behavior. For example, assume that pointers a and b of function vsq() point to objects which overlap, such that b[i] and a[i+1] are the same object. If a and b are not declared as restricted pointers the loops will be executed serially. If a and b are incorrectly qualified as restricted pointers the compiler may parallelize the execution of the loops, which is not safe, because b[i+1] should only be computed after b[i] is computed.