United States    
COMPAQ STORE | PRODUCTS |
SERVICES | SUPPORT | CONTACT US | SEARCH
Compaq C

Compaq C
Language Reference Manual


Previous Contents Index

3.7.4.1.3 Overlapping Objects

The restriction in the description of memcpy in the Standard prohibits copying between overlapping objects. An object is a region of data storage, and except for bit-fields, objects are composed of contiguous sequences of one or more bytes, the number, order, and encoding of which are either explicitly specified or implementation-defined.

Consider the following example:


/* memcpy between rows of a matrix */ 
 
void f1(void) { 
        extern char a[2][N]; 
        memcpy(a[1], a[0], N); 
} 

In this example:

Now consider the following example:


/* memcpy between halves of an array */ 
 
void f2(void) { 
        extern char b[2*N]; 
        memcpy(b+N, b, N); 
} 

In this example:

The length of an object is determined by various methods:

3.7.4.1.4 Restricted Pointer Prototype for memcpy

If an aliasing restriction like the one for memcpy could be expressed in a function definition, then it would be available to a compiler to facilitate effective pointer alias analysis. The __restrict type qualifier accomplishes this by specifying in the declaration of a pointer that the pointer provides exclusive initial access to the object to which it points, as though the pointer were initialized with a call to malloc .

The following prototype for memcpy both expresses the desired restriction and is compatible with the current prototype:


void *memcpy(void * __restrict s1, const void * __restrict s2, size_t n); 

3.7.4.2 Formal Definition of the __restrict Type Qualifier

The following definition of restricted pointers supports expression of aliasing restrictions in as many paradigms as possible. This is helpful in converting existing programs to use restricted pointers, and allows more freedom of style in new programs.

This definition, therefore, allows restricted pointers to be:

Definition

A pointer is designated as a restricted pointer by specifying the __restrict type qualifier on its declaration.

The formal definition of a restricted pointer as proposed for inclusion in the revised ISO C Standard follows:

Let D be a declaration of an ordinary identifier that provides a means of designating an object P as a restrict-qualified pointer.

If D appears inside a block and does not have storage-class extern, let B denote the block. If D appears in the list of parameter declarations of a function definition, let B denote the associated block. Otherwise, let B denote the block of main (or the block of whatever function is called at program startup, in a freestanding environment).

In what follows, a pointer expression E is said to be based on object P if (at some sequence point in the execution of B prior to the evaluation of E) modifying P to point to a copy of the array object into which it formerly pointed would change the value of E. (In other words, E depends on the value of P itself rather than on the value of an object referenced indirectly through P. For example, if identifier p has type (int ** restrict) , then the pointer expressions p and p+1 are based on the restricted pointer object designated by p , but the pointer expressions *p and p[1] are not.)

During each execution of B, let O be the array object that is determined dynamically by all references through pointer expressions based on P. All references to values of O shall be through pointer expressions based on P. Furthermore, if P is assigned the value of a pointer expression E that is based on another restricted pointer object P2, associated with block B2, then either the execution of B2 shall begin before the execution of B, or the execution of B2 shall end prior to the assignment. If this requirement is not met, then the behavior is undefined.

Here an execution of B means that portion of the execution of the program during which storage is guaranteed to be reserved for an instance of an object that is associated with B and has automatic storage duration. A reference to a value means either an access to or a modification of the value. During an execution of B, attention is confined to those references that are actually evaluated (this excludes references that appear in unevaluated expressions, and also excludes references that are "available," in the sense of employing visible identifiers, but do not actually appear in the text of B).

A translator is free to ignore any or all aliasing implications of uses of restrict.

3.7.4.3 Examples

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:

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.


Previous Next Contents Index
  

1.800.AT.COMPAQ

privacy and legal statement