tags:

views:

88

answers:

2

Suppose I have large array which I calculate an index into and pass to a second function. As a simple example, something like:

void foo(float* array, float c, unsigned int n)
{
    for (unsigned int i = 0; i < n; ++i)
        array[i] *= c;
}

void bar(float* restrict array, float* restrict array2, unsigned int m, unsigned int n)
{
    for (unsigned int i = 0; i < m; ++i)
        foo(&array[i * n], array2[i], n);
}

Is this breaking the rules for restrict in bar() where you pass the address of part of the array to foo(), even if you never really use the alias for a part of the array within bar()?

A: 

No, restrict means that array can't alias anything, so you can pass stuff to bar without breaking the rules

Spudd86
I think this question calls for a citation from the standard and not casual explanations along the lines of "restrict means...". C99 aliasing rules are too complicated to rely on casual explanations like that.
R..
the rules for restrict are pretty simple, it can't be reachable through anything but the restrict pointer.
Spudd86
+3  A: 

(All citations refer to N1256, which is C99 plus technical corrigenda (TC3).)

The formal definition of restrict is given in §6.7.3.1. I quote the most important subclause below. P is a restrict-qualified pointer to type T whose scope is a block B. A pointer expression E is said to be based on P if it depends on the value of P itself, not the value that P points to.

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.


Let's look at what the rules have to say about accesses to parts of bar's array in foo. We start with array, a restrict-qualified pointer declared in the parameter list of bar. For clarity, I will alpha-convert the parameters of foo:

void foo(float* b, float c, unsigned int n) { /*modify b[i]*/ }

The storage pointed to by array is also modified through b. That's ok with the second bullet point as &array[i*n] is equivalent to array+(i*n) (see §6.5.3.2).

If b was restrict-qualified, then we would have to check the fourth bullet point with P​←b, B​←foo, P2​←array, B2​←bar. Since B is nested inside B2 (functions behave as if inlined here, see §6.7.3.1.11), the first condition is met. There is also one instanciation of the third bullet point (the access to b[i] in foo) which is not a problem.

However b is not restrict-qualified. According to §6.3.2.3.2, “For any qualifier q, a pointer to a non-q-qualified type may be converted to a pointer to the q-qualified version of the type; the values stored in the original and converted pointers shall compare equal”. Therefore the conversion from array+(i*n) to b is well-defined and has the obvious meaning, so the program's behavior is defined. Furthermore, since b is not restrict-qualified, it doesn't need to obey any linearity condition. For example, the following foo is legal in combination with bar:

void qux(float *v, float *w) {
    v[0] += w[0];
}
void foo(float* b, float c, unsigned int n)
{
    qux(b,b);
}

ADDED: To address your specific concern “in bar() where you pass the address of part of the array to foo()”, this is a non-issue: restrict applies to the pointer, not the array, and you can perform arithmetic on it (bullet point 2).

Gilles
I can't tell if you're saying it's right or wrong, but props for deploying the standard completely.
Matt Joiner
@Matt: The code is correct (in part because the restrict rules aren't doing much here, and in part because you can convert away the restrict qualifier in the subscope delimited by `foo`).
Gilles