Correct understanding of C99's restrict?

Discussion in 'C Programming' started by Adam Warner, Jun 5, 2010.

  1. Adam Warner

    Adam Warner Guest

    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
    ....
    Adam Warner, Jun 5, 2010
    #1
    1. Advertising

  2. Adam Warner <> writes:

    > 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.
    Ben Bacarisse, Jun 5, 2010
    #2
    1. Advertising

  3. "christian.bau" <> writes:

    > On Jun 5, 2:11 pm, Adam Warner <> wrote:

    <snip>
    >> 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;
    >>
    >> }

    <snip>
    > 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.
    Ben Bacarisse, Jun 5, 2010
    #3
  4. "christian.bau" <> writes:

    > On Jun 5, 4:04 pm, Ben Bacarisse <> wrote:
    >
    >> 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:

    >
    > 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>
    --
    Ben.
    Ben Bacarisse, Jun 5, 2010
    #4
  5. Adam Warner

    Adam Warner Guest

    On Sat, 05 Jun 2010 06:50:36 -0700, christian.bau wrote:

    >> PS: GCC insists upon generating all the loads from and stores to the
    >> state structure:

    >
    > 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
    Adam Warner, Jun 5, 2010
    #5
  6. pete <> writes:

    > Ben Bacarisse wrote:
    >
    >> 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 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>
    --
    Ben.
    Ben Bacarisse, Jun 6, 2010
    #6
  7. Adam Warner

    Nobody Guest

    On Sat, 05 Jun 2010 14:40:05 +0100, Ben Bacarisse wrote:

    > 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.
    Nobody, Jun 6, 2010
    #7
  8. Ben Bacarisse <> wrote:
    > 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);

    --
    Peter
    Peter Nilsson, Jun 7, 2010
    #8
  9. Peter Nilsson <> writes:

    > Ben Bacarisse <> wrote:
    >> 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:


    Yes, thanks, I get that now :)

    <snip>
    > 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>
    --
    Ben.
    Ben Bacarisse, Jun 7, 2010
    #9
  10. Adam Warner

    Guest

    Peter Nilsson <> wrote:
    > 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).
    --
    Larry Jones

    My life needs a rewind/erase button. -- Calvin
    , Jun 7, 2010
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. tweak

    restrict keyword from ISO C99?

    tweak, Jun 19, 2004, in forum: C Programming
    Replies:
    7
    Views:
    5,200
    Dan Pop
    Jun 21, 2004
  2. C99 Restrict

    , Apr 20, 2005, in forum: C Programming
    Replies:
    1
    Views:
    524
    Christian Bau
    Apr 21, 2005
  3. Replies:
    3
    Views:
    3,654
    Chris Torek
    Feb 20, 2006
  4. Replies:
    6
    Views:
    367
    Army1987
    Sep 24, 2007
  5. Sune

    C99 restrict and function parameters?

    Sune, Feb 15, 2008, in forum: C Programming
    Replies:
    2
    Views:
    272
Loading...

Share This Page