What does 'restrict' mean?

[Me]

It gives the compiler no information whether it _does_ overlap, but it
does tell it that it may _assume_ there is no overlap, and hang the
consequences if the programmer bunged the job.

It only can make that assumption based on uses of the expressions. It
can't make it as is.

Not OK, and not OK, except for the quibble that your function body is
empty (and the declaration incomplete).

It is okay (minus my botched unnamed function parameters) otherwise you
have to deny that 6.7.3.1/10 is okay.

To quote the Standard:

# 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)

I don't see how this sentence is relevant.

Note: in the execution _of the block associated with the declaration_.
Not anywhere previously; in the block itself. You cannot use a
restricted pointer if it corresponds to another restricted pointer,

Yes you can. The meat and potatoes of restrict is 6.7.3.1/4. Nothing in
the first part of that paragraph applies with my example above, just
the second part.

_except_ in cases like this:

int * func(int * restrict ptr)
{
int * restrict ptr2 = ptr;
return ptr;
}

That's because the second restricted pointer was based on the first,
_inside_ the block which the restricted declaration belongs to.

Actually this example (which is exactly like 6.7.3.1/11) is the one
that's undefined. With 6.7.3.1/2, func is equivalent to:

int *arg = whatever, *ret;
{
int * restrict ptr = arg;
int * restrict ptr2 = ptr;
ret = ptr;
}

With 6.7.3.1/4:

- ptr is P2 associated with block B2
- ptr2 is P associated with block B

And neither the requirements of B and B2 is met in the rest of
6.7.3.1/4. To make this defined, you have to lose at least 1 restrict
qualifier.

Even though http://www.lysator.liu.se/c/restrict.html is slightly
outdated (the two main ways are that the current standard has extra
magic associated with restricted pointers to const T and also it has
better wording when dealing with lvalues and the object it accesses),
the examples are very good. The specific section you should look at is
3.8. Notice how the assignment goes from a restricted pointer to a
regular pointer. The whole reason there are fancy pants semantics in
the standard dealing with assignments is so a compiler can track how a
restricted pointer P can propigate to regular pointer expressions. This
is extremely important in C because you lose the restrict qualifier by
doing &*p or something similar (3.6 on lysator has further trivial but
common examples).

 

[Me]

I think you are wrong there -- restrict does not say straight
out "does not overlap" but it says the compiler may assume that
the pointers are used like this. I expect a compiler to utilise
this information as if a full alias analysis said "these pointers
never point to overlapping objects". These are the steps I performed
but for the omission of making sure that no null pointers are
involved.

The standard doesn't even mention null when dealing with restrict. How
did you arrive at these semantics (with quotes from the standard of
course)? You're also going to have to explain the semantics of restrict
where a pointer to end+1 of an object that just happens to compare
equal to the pointer of the beginning of another object.

I understand that there are no guarantees for restrict but that
there is a permission to act as if there were such guarantees --
which is quite enough for a compiler.

I think you're confused because you're hung up on the word "overlap".
The formalism took me a really long time to finally understand but to
make it simple: with the restrict keyword, the standard allows for
exact overlap or completely disjoint subobject access. In your MemFoo
example, it would be like exact overlap so the standard can't eliminate
the if statement as is.

Although I'd consider it bad style, this is correct use of the restrict
keyword:

void f(int *restrict begin, const int *restrict end)
{
while (begin != end)
*begin++ = 0;
}

Because the standard doesn't care if two restrict pointers point to the
same object. It just cares about what happens when you dereference a
restricted pointer (or propigations it tracked from an expression
involving a restrict pointer, see 3.6's "pointer expressions based on
p" table on http://www.lysator.liu.se/c/restrict.html for further
examples).

You can think of the restrict keyword as a request to the compiler to
track propigations of that pointer defined as restrict, which is why
these are correct:

/* similar to exact overlapping case */
int * restrict p = whatever;
int * restrict q = whatever;

/* the compiler has to deal with this anyway when tracking pointer
expressions, so this falls out naturally */
int * restrict p = whatever;
int *a = p;
int *b = p;

But this is undefined (because it's like a double request to keep track
of pointers):

int * restrict p = whatever;
int * restrict b = p;

Or else the formalism of restrict would be *way* more difficult to
specify without any real benefit (and hence further loss of
optimization opportunities).

Here is something subtle that you may have missed as well:

int * restrict p = whatever;
&*p;
p;

The type of &*p is (int *), this is equivalent to the example int *a =
p above. The type of p is (int * restrict) but the restrict is ignored
on this specific pointer expression so it is also like int *a = p
above. Now connect the dots with 3.9 on that lysator page that says
that restrict on casts and return values are ignored and you'll see why
the int *a = p example is so important (and the one the standard
actually cares about) but not the int * restrict b = p one.