The formal definition of the __restrict type qualifier can be difficult to grasp, but simplified explanations tend to be less accurate and complete. The essence of the definition is that the __restrict type qualifier is an assertion by the programmer that whenever a memory access is made through a restricted pointer, the only aliases the compiler need consider are other accesses made through the same pointer.

Much of the complexity is in defining exactly what is meant for an access to be made through a pointer (the based-on rules), and specifying how a restricted pointer can be assigned the value of another restricted pointer, while limiting the aliasing potential to occur only at block boundaries. Examples can be the best way to understand restricted pointers.

The following examples show the use of restricted pointers in various contexts.

3.7.4.3.1 File Scope Restricted Pointers

A file scope restricted pointer is subject to very strong restrictions. It should point into a single array object for the duration of the program. That array object must not be referenced both through the restricted pointer and through either its declared name (if it has one) or another restricted pointer.

Because of these restrictions, references through the pointer can be optimized as effectively as references to a static array through its declared name. File scope restricted pointers are therefore useful in providing access to dynamically allocated global arrays.

In the following example, a compiler can deduce from the __restrict type qualifiers that there is no potential aliasing among the names a , b , and c :

/* File Scope Restricted Pointer */ float * __restrict a, * __restrict b; float c[100]; int init(int n) { float * t = malloc(2*n*sizeof(float)); a = t; /* a refers to 1st half. */ b = t + n; /* b refers to 2nd half. */ }

Notice how the single block of allocated storage is subdivided into two unique arrays in the function init .

3.7.4.3.2 Function Parameters

Restricted pointers are also very useful as pointer parameters of a function. Consider the following example:

/* Restricted pointer function parameters */ float x[100]; float *c; void f3(int n, float * __restrict a, float * const b) { int i; for ( i=0; i<n; i++ ) a[i] = b[i] + c[i]; } void g3(void) { float d[100], e[100]; c = x; f3(100, d, e); /* Behavior defined. */ f3( 50, d, d+50); /* Behavior defined. */ f3( 99, d+1, d); /* Behavior undefined. */ c = d; f3( 99, d+1, e); /* Behavior undefined. */ f3( 99, e, d+1); /* Behavior defined. */ }

In the function f3 , it is possible for a compiler to infer that there is no aliasing of modified objects, and so to optimize the loop aggressively. Upon entry to f3 , the restricted pointer a must provide exclusive access to its associated array. In particular, within f3 neither b nor c may point into the array associated with a , because neither is assigned a pointer value based on a . For b , this is evident from the const qualifier in its declaration, but for c , an inspection of the body of f3 is required.

Two of the calls shown in g3 result in aliasing that is inconsistent with the __restrict qualifier, and their behavior is undefined. Note that it is permitted for c to point into the array associated with b . Note also that, for these purposes, the "array" associated with a particular pointer means only that portion of an array object that is actually referenced through that pointer.

3.7.4.3.3 Block Scope

A block-scope restricted pointer makes an aliasing assertion that is limited to its block. This is more natural than allowing the assertion to have function scope. It allows local assertions that apply only to key loops, for example. It also allows equivalent assertions to be made when inlining a function by converting it into a macro.

In the following example, the original restricted-pointer parameter is represented by a block-scope restricted pointer:

/* Macro version of f3 */ float x[100]; float *c; #define f3(N, A, B) \ { int n = (N); \ float * __restrict a = (A); \ float * const b = (B); \ int i; \ for ( i=0; i<n; i++ ) \ a[i] = b[i] + c[i]; \ }

3.7.4.3.4 Members of Structures

A restricted-pointer member of a structure makes an aliasing assertion. The scope of that assertion is the scope of the ordinary identifier used to access the structure.

Therefore, although the structure type is declared at file scope in the following example, the assertions made by the declarations of the parameters of f4 have block (of the function) scope.

/* Restricted pointers as members of a structure */ struct t { /* Restricted pointers assert that */ int n; /* members point to disjoint storage. */ float * __restrict p; float * __restrict q; }; void f4(struct t r, struct t s) { /* r.p, r.q, s.p, s.q should all point to */ /* disjoint storage during each execution of f4. */ /* ... */ }

3.7.4.3.5 Type Definitions

A __restrict qualifier in a typedef makes an aliasing assertion when the typedef name is used in the declaration of an ordinary identifier that provides access to an object. As with members of structures, the scope of the latter identifier, not the scope of the typedef name, determines the scope of the aliasing assertion.

3.7.4.3.6 Expressions Based on Restricted Pointers

Consider the following example:

/* Pointer expressions based on p */ #include <stdlib.h> #include <string.h> struct t { int * q; int i; } a[2] = { /* ... */ }; void f5(struct t * __restrict p, int c) { struct t * q; int n; if(c) { struct t * r; r = malloc(2*sizeof(*p)); memcpy(r, p, 2*sizeof(*p)); p = r; } q = p; n = (int)p; /* - - - - - - - - - - - - - - - - - - - - - - - Pointer expressions Pointer expressions based on p: not based on p: ------------------- ------------------- p p-&gt;q p+1 p[1].q &amp;p[1] &amp;p &amp;p[1].i q q-&gt;p ++q (char *)p (char *)(p-&gt;i) (struct t *)n ((struct t *)n)->q - - - - - - - - - - - - - - - - - - - - - - - - */ } main() { f5(a, 0); f5(a, 1); }

In this example, the restricted pointer parameter p is potentially adjusted to point into a copy of its original array of two structures. By definition, a subsequent pointer expression is said to be based on p if and only if its value is changed by this adjustment.

In the comment:

• The values of the pointer expressions in the first column are changed by this adjustment, and so those expressions are based on p .
• The values of the pointer expressions in the second column are not changed by the adjustment, and so those expressions are not based on p .

This can be verified by adding appropriate print statements for the expressions and comparing the values produced by the two calls of f5 in main .

Notice that the definition of "based on" applies to expressions that rely on implementation-defined behavior. This is illustrated in the example, which assumes that the casts (int) followed by (struct t *) give the original value.

3.7.4.3.7 Assignments Between Restricted Pointers

Consider one restricted pointer "newer" than another if the block with which the first is associated begins execution after the block associated with the second. Then the formal definition allows a newer restricted pointer to be assigned a value based on an older restricted pointer. This allows, for example, a function with a restricted-pointer parameter to be called with an argument that is a restricted pointer.

Conversely, an older restricted pointer can be assigned a value based on a newer restricted pointer only after execution of the block associated with the newer restricted pointer has ended. This allows, for example, a function to return the value of a restricted pointer that is local to the function, and the return value then to be assigned to another restricted pointer.

The behavior of a program is undefined if it contains an assignment between two restricted pointers that does not fall into one of these two categories. Some examples follow:

/* Assignments between restricted pointers */ int * __restrict p1, * __restrict p2; void f6(int * __restrict q1, * __restrict q2) { q1 = p1; /* Valid behavior */ p1 = p2; /* Behavior undefined */ p1 = q1; /* Behavior undefined */ q1 = q2; /* Behavior undefined */ { int * __restrict r1, * __restrict r2; ... r1 = p1; /* Valid behavior */ r1 = q1; /* Valid behavior */ r1 = r2; /* Behavior undefined */ q1 = r1; /* Behavior undefined */ p1 = r1; /* Behavior undefined */ ... } }

3.7.4.3.8 Assignments to Unrestricted Pointers

The value of a restricted pointer can be assigned to an unrestricted pointer, as in the following example:

/* Assignments to unrestricted pointers */ void f7(int n, float * __restrict r, float * __restrict s) { float * p = r, * q = s; while(n->0) *p++ = *q++; }

The Compaq C compiler tracks pointer values and optimizes the loop as effectively as if the restricted pointers r and s were used directly, because in this case it is easy to determine that p is based on r , and q is based on s .

More complicated ways of combining restricted and unrestricted pointers are unlikely to be effective because they are too difficult for a compiler to analyze. As a programmer concerned about performance, you must adapt your style to the capabilities of the compiler. A conservative approach would be to avoid using both restricted and unrestricted pointers in the same function.

3.7.4.3.9 Ineffective Uses of Type Qualifiers

Except where specifically noted in the formal definition, the __restrict qualifier behaves in the same way as const and volatile .

In particular, it is not a constraint violation for a function return type or the type-name in a cast to be qualified, but the qualifier has no effect because function call expressions and cast expressions are not lvalues.

Thus, the presence of the __restrict qualifier in the declaration of f8 in the following example makes no assertion about aliasing in functions that call f8 :

/* Qualified function return type and casts */ float * __restrict f8(void) /* No assertion about aliasing. */ { extern int i, *p, *q, *r; r = (int * __restrict)q; /* No assertion about aliasing. */ for(i=0; i<100; i++) *(int * __restrict)p++ = r[i]; /* No assertion */ /* about aliasing. */ return p; }

Similarly, the two casts make no assertion about aliasing of the references through the pointers p and r .

3.7.4.3.10 Constraint Violations

It is a constraint violation to restrict-qualify an object type that is not a pointer type, or to restrict-qualify a pointer to a function:

/*__restrict cannot qualify non-pointer object types: */ int __restrict x; /* Constraint violation */ int __restrict *p; /* Constraint violation */ /* __restrict cannot qualify pointers to functions: */ float (* __restrict f9)(void); /* Constraint violation */

3.8 Type Definition

The keyword typedef is used to define a type synonym. In such a definition, the identifiers name types instead of objects. One such use is to define an abbreviated name for a lengthy or confusing type definition.

A type definition does not create a new basic data type; it creates an alias for a basic or derived type. For example, the following code helps explain the data types of objects used later in the program:

typedef float *floatp, (*float_func_p)();

The type floatp is now "pointer to a float value" type, and the type float_func_p is "pointer to a function returning float ".

A type definition can be used anywhere the full type name is normally used (you can, of course, use the normal type name). Type definitions share the same name space as variables, and defined types are fully compatible with their equivalent types. Types defined as qualified types inherit their type qualifications.

Type definitions can also be built from other type definitions. For example:

typedef char byte; typedef byte ten_bytes[10];

Type definition can apply to variables or functions. It is illegal to mix type definitions with other type specifiers. For example:

typedef int *int_p; typedef unsigned int *uint_p; unsigned int_p x; /* Invalid */ uint_p y; /* Valid */

Type definitions can also be used to declare function types. However, the type definition cannot be used in the function's definition. The function's return type can be specified using a type definition. For example:

typedef unsigned *uint_p; /* uint_p has type "pointer to unsigned int" */ uint_p xp; typedef uint_p func(void); /* func has type "function returning pointer to */ /* unsigned int */ func f; func b; func f(void) /* Invalid -- this declaration specifies a */ /* function returning a function type, which */ { /* is not allowed */ return xp; } uint_p b(void) /* Legal -- this function returns a value of { /* type uint_p. */ return xp; }

The following example shows that a function definition cannot be inherited from a typedef name:

typedef int func(int x); func f; func f /* Valid definition of f with type func */ { return 3; } /* Invalid, because the function's type is not inherited */

Changing the previous example to a valid form results in the following:

typedef int func(int x); func f; int f(int x) /* Valid definition of f with type func */ { return 3; } /* Legal, because the function's type is specified */

You can include prototype information, including parameter names, in the typedef name. You can also redefine typedef names in inner scopes, following the scope rules explained in Section 2.3.

Declarations are used to introduce the identifiers used in a program and to specify their important attributes, such as type, storage class, and identifier name. A declaration that also causes storage to be reserved for an object or that includes the body of a function, is called a definition.

Section 4.1 covers general declaration syntax rules, Section 4.2 discusses initialization, and Section 4.3 describes external declarations.

The following kinds of identifiers can be declared. See the associated section for information on specific declaration and initialization syntax. Functions are discussed in Chapter 5.

• Simple objects ( Section 4.4)
• Enumeration constants ( Section 4.5)
• Pointers ( Section 4.6)
• Arrays ( Section 4.7)
• Structure and union members ( Section 4.8)
• Tags ( Section 4.10)

The general syntax of a declaration is as follows:

declaration:

declaration-specifiers init-declarator-listopt;

declaration-specifiers:

storage-class-specifier declaration-specifiersopt type-specifier declaration-specifiersopt type-qualifier declaration-specifiersopt

init-declarator-list:

init-declarator init_declarator-list , init-declarator

init-declarator:

declarator declarator = initializer

Note the following items about the general syntax of a declaration:

• The storage-class-specifier, type-qualifier, and type-specifier can be listed in any order. All are optional, but, except for function declarations, at least one such specifier or qualifier must be present. Placing the storage-class-specifier anywhere but at the beginning of the declaration is an obsolete style.
• Storage-class keywords are auto , static , extern , and register .
• Type qualifiers are const and volatile .
• The declarator is the name of the object or function being declared. A declarator can be as simple as a single identifier, or can be a complex construction declaring an array, structure, pointer, union, or function (such as *x , tree() , and treebar[10] ).
  A full declarator is a declarator that is not part of another declarator. The end of a full declarator is a sequence point. If the nested sequence of declarators in a full declarator contains a variable-length array type, the type specified by the full declarator is said to be variably modified.
• Initializers are optional and provide the initial value of an object. Initializers can be a single value or a brace-enclosed list of values, depending on the type of object being declared.
• A declaration determines the beginning of an identifier's scope.
• An identifier's linkage is determined by the declaration's placement and its specified storage class.

Consider the following example:

volatile static int data = 10;

This declaration shows a qualified type (a data type with a type qualifier---in this case, int qualified by volatile ), a storage class ( static ), a declarator ( data ), and an initializer ( 10 ). This declaration is also a definition, because storage is reserved for the data object data .

The previous example is simple to interpret, but complex declarations are more difficult. See your platform-specific Compaq C documentation for more information about interpreting C declarations.

The following semantic rules apply to declarations:

• Empty declarations are illegal; declarations must contain at least one declarator, or specify a structure tag, union tag, or the members of an enumeration.
• Each declarator declares one identifier. There is no limit to the number of declarators in a declaration.
• At most, one storage-class specifier can be used in each object declaration. If none is provided, the auto storage class is assigned to objects declared inside a function definition, and the extern class is assigned to objects declared outside of a function definition.
• The only allowable (and optional) storage class for declaration of a function with block scope is extern .
• If no type-specifier is present, the default is signed int .
• A declarator is usable only over a certain range of the program, determined by the declarator's scope. The duration of its storage allocation is dependent on its storage class. See Section 2.3 for more information on scope and Section 2.10 for more information on storage classes.
• The usefulness of an identifier can be limited by its visibility, which can be hidden in some parts of the program. See Section 2.4 for more information on visibility.
• All declarations in the same scope that refer to the same object or function must have compatible types.
• If an object has no linkage, there can be no more than one declaration of the object with the same scope and in the same name space. Objects without linkage must have their type completed by the end of the declaration, or by the final initializer (if it has one). Section 2.8 describes linkage.

Storage Allocation

Storage is allocated to a data object in the following circumstances:

• If the object has no linkage, storage is allocated upon declaration of the object. If a block scope object with auto or register storage class is declared, storage is deallocated at the end of the block.
• If the object has internal linkage, storage is allocated upon the first definition of the object.
• If the object has external linkage, storage is allocated upon initialization of the object, which must occur only once for each object. If an object has only a tentative definition (see Section 2.9), the compiler acts as though there were a file scope definition of the object with an initializer of zero. Section 2.8 describes linkage in detail.