Correct understanding of C99's restrict?

[Adam Warner]

Hi all,

Is my understanding of the commented code below correct?


#include <stdint.h>
#include <stdio.h>

typedef struct {
uint64_t a, b, c, d, e, f;
} state_t;

__attribute__ ((noinline)) void hello_world() {
printf("Hello, World!\n");
}

void fn(state_t *restrict state) {
//the state pointer is the sole means of access to the state_t object
uint64_t a=state->a, b=state->b, c=state->c,
d=state->d, e=state->e, f=state->f;

//the sole means of access to the state object is NOT being passed as an
//argument to the function below. This is a promise to the compiler that
//hello_world() will not be accessing 'state'
hello_world();

//state has not changed. All the assignments should optimise to no-ops
state->a=a; state->b=b; state->c=c; state->d=d; state->e=e; state->f=f;
}

int main() {
return 0;
}


Regards,
Adam

PS: GCC insists upon generating all the loads from and stores to the state
structure:
$ gcc-4.5 -std=gnu99 -O3 restrict.c && objdump -d -m i386:x86-64:intel a.out
....
0000000000400500 <fn>:
400500: 48 89 5c 24 d0 mov QWORD PTR [rsp-0x30],rbx
400505: 48 89 6c 24 d8 mov QWORD PTR [rsp-0x28],rbp
40050a: 31 c0 xor eax,eax
40050c: 4c 89 64 24 e0 mov QWORD PTR [rsp-0x20],r12
400511: 4c 89 6c 24 e8 mov QWORD PTR [rsp-0x18],r13
400516: 48 89 fb mov rbx,rdi
400519: 4c 89 74 24 f0 mov QWORD PTR [rsp-0x10],r14
40051e: 4c 89 7c 24 f8 mov QWORD PTR [rsp-0x8],r15
400523: 48 83 ec 48 sub rsp,0x48
400527: 48 8b 17 mov rdx,QWORD PTR [rdi]
40052a: 4c 8b 7f 08 mov r15,QWORD PTR [rdi+0x8]
40052e: 4c 8b 77 10 mov r14,QWORD PTR [rdi+0x10]
400532: 4c 8b 6f 18 mov r13,QWORD PTR [rdi+0x18]
400536: 4c 8b 67 20 mov r12,QWORD PTR [rdi+0x20]
40053a: 48 8b 6f 28 mov rbp,QWORD PTR [rdi+0x28]
40053e: 48 89 54 24 08 mov QWORD PTR [rsp+0x8],rdx
400543: e8 a8 ff ff ff call 4004f0 <hello_world>
400548: 48 8b 54 24 08 mov rdx,QWORD PTR [rsp+0x8]
40054d: 4c 89 7b 08 mov QWORD PTR [rbx+0x8],r15
400551: 4c 89 73 10 mov QWORD PTR [rbx+0x10],r14
400555: 4c 89 6b 18 mov QWORD PTR [rbx+0x18],r13
400559: 4c 89 63 20 mov QWORD PTR [rbx+0x20],r12
40055d: 48 89 6b 28 mov QWORD PTR [rbx+0x28],rbp
400561: 48 89 13 mov QWORD PTR [rbx],rdx
400564: 48 8b 6c 24 20 mov rbp,QWORD PTR [rsp+0x20]
400569: 48 8b 5c 24 18 mov rbx,QWORD PTR [rsp+0x18]
40056e: 4c 8b 64 24 28 mov r12,QWORD PTR [rsp+0x28]
400573: 4c 8b 6c 24 30 mov r13,QWORD PTR [rsp+0x30]
400578: 4c 8b 74 24 38 mov r14,QWORD PTR [rsp+0x38]
40057d: 4c 8b 7c 24 40 mov r15,QWORD PTR [rsp+0x40]
400582: 48 83 c4 48 add rsp,0x48
400586: c3 ret
....

 

[Ben Bacarisse]

Is my understanding of the commented code below correct?

I think not, though I admit that I am not an expert on restrict.

#include <stdint.h>
#include <stdio.h>

typedef struct {
uint64_t a, b, c, d, e, f;
} state_t;

__attribute__ ((noinline)) void hello_world() {
printf("Hello, World!\n");
}

void fn(state_t *restrict state) {

As I understand it, restrict has no useful meaning when there is only
one restricted pointer in scope. It is a promise that two or more
pointers do not ever permit access to the same object.

//the state pointer is the sole means of access to the state_t object
uint64_t a=state->a, b=state->b, c=state->c,
d=state->d, e=state->e, f=state->f;

//the sole means of access to the state object is NOT being passed as an
//argument to the function below. This is a promise to the compiler that
//hello_world() will not be accessing 'state'
hello_world();

In this case the compiler could deduce that fact by looking at the
function, but it can't deduce it form the absence of a pointer argument
(of any sort, restricted or not).

//state has not changed. All the assignments should optimise to no-ops
state->a=a; state->b=b; state->c=c; state->d=d; state->e=e; state->f=f;
}

<snip>

 

[Ben Bacarisse]

On Jun 5, 2:11 pm, Adam Warner <[email protected]> wrote:

You are correct, the loads and stores could be optimised away.

The data in *state is both accessed and modified using an lvalue based
on the restrict pointer "state". Since the pointer "state" is not
passed to hello_world, that function has no means to access or modify
the data in *state using an lvalue based on state, and the compiler
can easily know that.

So far I agree but my agreement does not yet depend on the meaning of
restrict. It has no means to modify *state not because the pointer is not
passed but because it does not do anything with any objects of that
type. In other words, the restricted nature of the pointer does not
seem to come into play yet.

And hello_world is not _allowed_ to either
access or modify the data in *state by any other means (that's the
rules of restrict pointers).

Can you help me see how you arrive at this? I can't see why hello_world
could not modify *state via some other means (another pointer or an
direct reference to the structure). I know it does not, but I can't see
how not passing state allows the compiler to deduce that it does not do
so in general. Lets pick an example where the called function does
modify something of the right type. I think you are saying that this:

int x = 0;

void f(void) { x = 42; }

int g(int *restrict ip) {
int local = *ip;
f();
return *ip;
}

int main(void) { return g(&x); }

is "wrong" (undefined?) because not passing ip to g lets the compiler
assume something about what it can access (specifically that g can't
access what ip points to).

Therefore, the compiler could quite
easily deduce that the call to hello_world will not modify any of the
data in *state, and both reading and writing back the data is
pointless. The whole of the function fn () can be completely legally
optimised to a call to hello_world and nothing else.

I agree in the case given, but I would say the same if the pointer were
not restrict qualified. An example where it *might* access an object of
type state_t might be more revealing.

<snip>

 

[Ben Bacarisse]

That's the essence of what "restrict" does. If you have an object P
that is a restrict pointer, like state in this case, then the rules
are:

1.If an object is modified through an lvalue whose address is based on
P, and also accessed or modified through an lvalue whose address is
_not_ based on P, then behaviour is undefined.

Within the execution of the block associated with the restricted
pointer. This is the bit I misunderstood. I had a picture of this
applying while the execution was within the scope of the declaration
but:

"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 [...]"

i.e. it includes called functions that can't see the declaration.

I'll have to adjust my picture. Thanks.

<snip>

 

[Adam Warner]

You are correct, the loads and stores could be optimised away.

Thanks for the confirmation.

The data in *state is both accessed and modified using an lvalue based
on the restrict pointer "state". Since the pointer "state" is not passed
to hello_world, that function has no means to access or modify the data
in *state using an lvalue based on state, and the compiler can easily
know that. And hello_world is not _allowed_ to either access or modify
the data in *state by any other means (that's the rules of restrict
pointers). Therefore, the compiler could quite easily deduce that the
call to hello_world will not modify any of the data in *state, and both
reading and writing back the data is pointless. The whole of the
function fn () can be completely legally optimised to a call to
hello_world and nothing else.

You might check what happens if you remove the call to hello_world.
Quite possible that the compiler doesn't optimise that kind of code at
all, since it is a bit unusual to read six members of a struct and then
writing them back unchanged.

With the call to hello_world() commented out GCC optimises fn() to the
opcode 'repz ret' (gcc-4.5; Linux-AMD64 ABI).

Regards,
Adam

 

[Ben Bacarisse]

That's my understanding also.

Do you accept Christian Bau's explanation? It fits with my newly minted
reading of standard. The key part being that restrict applies during a
period of execution that includes part of the code where no restricted
pointers are in scope. I.e. that it is not tied to scope so much as
lifetime.

I'd love to be right, but I fear we are both wrong!

<snip>

 

[Nobody]

As I understand it, restrict has no useful meaning when there is only
one restricted pointer in scope. It is a promise that two or more
pointers do not ever permit access to the same object.

That's not my understanding. My understanding (which may or may not be
correct) is that the array referenced by the "restrict"ed pointer doesn't
overlap *anything*. Not just the array(s) referenced by other "restrict"ed
pointer(s), but also global variables and arrays referenced by
non-"restrict"ed pointers.

 

[Peter Nilsson]

As I understand it, restrict has no useful meaning when
there is only one restricted pointer in scope.

Restrict has a meaning for each pointer it relates to, 6.7.3p7:

"An object that is accessed through a restrict-qualified
pointer has a special association with that pointer. This
association, defined in 6.7.3.1 below, requires that all
accesses to that object use, directly or indirectly, the
value of that particular pointer."

Consider...

restrict char *r;
char *s;
char *t;

This allows s and t to overlap, but not with r. Whatever r
points to can only be accessed through r.

Consider...

int printf(const char * restrict format, ...);

The restrict imposes a requirement that the format string
is independant of any arguments passed to it.

So following is undefined in C99...

char format[] = "format string: \"%s\"\n";
printf(format, format);

 

[Ben Bacarisse]

Restrict has a meaning for each pointer it relates to, 6.7.3p7:

Yes, thanks, I get that now

Consider...

int printf(const char * restrict format, ...);

The restrict imposes a requirement that the format string
is independant of any arguments passed to it.

This means that memcpy could be prototyped

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

restrict-qualifying both pointers is, presumably, for symmetry only.

<snip>

 

[lawrence.jones]

Consider...

int printf(const char * restrict format, ...);

The restrict imposes a requirement that the format string
is independant of any arguments passed to it.

So following is undefined in C99...

char format[] = "format string: \"%s\"\n";
printf(format, format);

Actually, it's not -- the short description of restrict in 6.7.3
overreaches, as the details in 6.7.3.1 make clear. It's allowable to
access an object through both a restricted pointer and some other
mechanism, as long as the object isn't modified. Since format is never
modified in your example, the behavior is well-defined (as most people
would expect).