Is the C11 formal definition of restrict consistent with implementation?

Question

In trying to answer a recent question (Passing restrict qualified pointers to functions?), I could not find how the C11 standard is consistent with practice.

I'm not trying to call out the standard or anything, most things that look inconsistent I just am not understanding right, but my question is best posed as an argument against the definition used in the standard, so here it is.

It seems to be commonly accepted that a function can take a restrict qualified pointer and both work on it and have its own function calls work on it. For example,

// set C to componentwise sum and D to componentwise difference

void dif_sum(float* restrict C, float* restrict D, size_t n)
{
     size_t i = 0;
     while(i<n) C[i] = C[i] - D[i],
                D[i] += C[i] + D[i],
                ++i;
}



// set A to componentwise sum of squares of A and B
// set B to componentwise product of A and B

void prod_squdif(float* restrict A, float* restrict B, size_t n)
{
     size_t i = 0;
     float x;
     dif_sum(A,B,n);
     while(i<n) x = ( (A[i]*=A[i]) - B[i]*B[i] )/2,
                A[i] -= x,
                B[i++] = x/2;
}

What seems to be the common understanding is that restrict pointers need to reference independent space within their declaring block. So, prod_sqdif is valid because nothing lexically within its defining block accesses the arrays identified by A or B other than those pointers.

To demonstrate my concern with the standard, here is the standard formal definition of restrict (according to the committee draft, if you have the final version and it is different, let me know!):

6.7.3.1 Formal definition of restrict

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

2 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).

3 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. Note that ‘‘based’’ is defined only for expressions with pointer types.

4 During each execution of B, let L be any lvalue that has &L based on P. If L is used to access the value of the object X that it designates, and X is also modified (by any means), then the following requirements apply: T shall not be const-qualified. Every other lvalue used to access the value of X shall also have its address based on P. Every access that modifies X shall be considered also to modify P, for the purposes of this subclause. 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 these requirements are not met, then the behavior is undefined.

5 Here an execution of B means that portion of the execution of the program that would correspond to the lifetime of an object with scalar type and automatic storage duration associated with B.

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

[Examples not included because they are not formally significant.]

Identifying execution of B with expressions lexically contained therein might be seen as supported by the following excerpt from 6.2.4, item 6:

"...Entering an enclosed block or calling a function suspends, but does not end, execution of the current block..."

However, part 5 of the formal definition of restrict explicitly defines the block B to correspond to the lifetime of an object with automatic storage declared in B (in my example, B is the body of prod_squdif). This clearly overrides any definition of the execution of a block found elsewhere in the standard. The following excerpt from the standard defines lifetime of an object.

6.2.4 Storage durations of objects, item 2

The lifetime of an object is the portion of program execution during which storage is guaranteed to be reserved for it. An object exists, has a constant address, and retains its last-stored value throughout its lifetime. 34) If an object is referred to outside of its lifetime, the behavior is undefined. The value of a pointer becomes indeterminate when the object it points to (or just past) reaches the end of its lifetime.

Then the execution of dif_sum is clearly included in the execution of B. I don't think there is any question there. But then the lvalues in dif_sum that read and modify elements of A and B (via C and D) are clearly not based on A and B (they follow sequence points where A and B could have been repointed to copies of their content without changing the locations identified by the lvalues). This is undefined behavior. Note that what lvalues or sequence points are discussed in item 4 is not restricted; as it is stated, there is no reason to restrict lvalues and sequence points to those lexically corresponding to the block B, and so lvalues and sequence points within a function call play just like they do in the body of the calling function.

On the other hand, the generally accepted use of restrict seems implied by the fact that the formal definition explicitly allows C and D to be assigned the values of A and B. This suggests that some meaningful access to A and B through C and D is allowed. However, as argued above, such access is undefined for any element modified through either the outer or inner function call, and at least read by the inner call. This seems contrary to the apparent intent of allowing the assignment in the first place.

Of course, intent has no formal place in the standard, but it does seem suggestive that the common interpretation of restrict, rather than what seems actually defined, is what is intended.

In summary, interpreting the execution of B as the execution of each statement during the lifetime of B's automatic storage, then function calls can't work with the contents of restrict pointers passed to them.

It seems unavoidable to me that there should be some exception stating reads and writes within functions or sub blocks are not considered, but that at most one assignment within such a sub block (and other sub blocks, recursively) may be based on any particular restrict pointer in the outer block.

I have really gone over the standard, both today and yesterday. I really can't see how the formal definition of restrict could possibly be consistent with the way it seems to be understood and implemented.

EDIT: As has been pointed out, violating the restrict contract results in undefined behavior. My question is not about what happens when the contract is violated. My question can be restated as follows:

How can the formal definition of restrict be consistent with access to array elements through function calls? Does such access, within a calling function, not constitute access not based on the restrict pointer passed to the function?

I am looking for an answer based in the standard, as I agree that restrict pointers should be able to be passed through function calls. It just seems that this is not the consequence of the formal definition in the standard.

EDIT

I think the main problem with communicating my question is related to the definition of "based on". I will try to present my question a little differently here.

The following is an informal tracking of a particular call to prod_squdif. This is not intended as C code, it is just an informal description of the execution of the function's block.

Note that this execution includes the execution of the called function, per item 5 of the formal definition of restrict: "Here an execution of B means that portion of the execution of the program that would correspond to the lifetime of an object with scalar type and automatic storage duration associated with B."

// 1. prod_squdif is called
prod_squdif( (float[1]){2}, (float[1]){1}, 1 )

// 2. dif_sum is called
dif_sum(A,B,n)   // assigns C=A and D=B

// 3. while condition is evaluated
0<1   // true

// 4. 1st assignment expression
C[0] = C[0] - D[0]   // C[0] == 0

// 5. 2nd assignment expression
D[0] += C[0] + D[0]   // D[0] == 1

// 6. increment
++i // i == 1

// 7. test
1<1   // false

// return to calling function

// 8. test
0<1   // true

// 9. 1st assignment expression
x = ( (A[0]*=A[0]) - B[1]*B[1] )/2   // x == -.5

// 10. 2nd assignment expression
A[0] -= -.5   // A[0] == .5

// 11. 3rd assignment expression
B[i++/*evaluates to 0*/] = -.5/2   // B[0] == -.25

// 12. test
1<1   // false

// prod_squdif returns

So, the test for the restrict contract is given by item 4 in the formal definition of restrict: "During each execution of B, let L be any lvalue that has &L based on P. If L is used to access the value of the object X that it designates, and X is also modified (by any means), then the following requirements apply: ... Every other lvalue used to access the value of X shall also have its address based on P..."

Let L be the lvalue on the left of the portion of the execution marked '4' above (C[0]). Is &L based on A? I.e., is C based on A?

See item 3 of the formal definition of restrict: "...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...".

Take as a sequence point the end of item 3 above. (At this sequence point) modifying A to point to a coppy of the array object into which it formerly pointed would NOT change the value of C.

Thus C is not based on A. So A[0] is modified by an lvalue not based on A. Since it is also read by an lvalue that is based on A (item 10), this is undefined behavior.

My question is: Is it correct to therefore conclude that my example invokes undefined behavior and thus the formal definition of restrict is not consistent with common implementation?

Answer 1

Suppose we have a function with nested blocks like this:

void foo()
{
  T *restrict A = getTptr();
  {
    T *restrict B = A;
    {
      #if hypothetical
      A = copyT(A);
      #endif
      useTptr(B + 1);
    }
  }
}

It would seem that, at the point where useTptr(B + 1) is called, the hypothetical change to A would no longer affect the value of B + 1. However, a different sequence point can be found, such that a change to A does affect the value of B + 1:

void foo()
{
  T *restrict A = getTptr();
  #if hypothetical
  A = copyT(A);
  #endif    
  {
    T *restrict B = A;
    {
      useTptr(B + 1);
    }
  }
}

and C11 draft standard n1570 6.7.3.1 Formal definition of restrict only demands that there be some such sequence point, not that all sequence points exhibit this behavior.

Answer 2

I'm really not sure exactly what your question is.

It sounds like you're asking:

Q: Gee, will "restrict" still apply if I violate the "restrict" contract? Like in the "remove_zeroes()" example?

The answer, of course, is "No - it won't".

Here are two links that might clarify the discussion. Please update your post with (a) more explicit question(s):

• Realistic usage of the C99 'restrict' keyword?

• Is it legal to assign a restricted pointer to another pointer, and use the second pointer to modify the value?

• https://en.wikipedia.org/wiki/Restrict