'restrict' in plain English?

Discussion in 'C Programming' started by Me, Mar 6, 2006.

  1. Me

    Me Guest

    I'm trying to wrap my head around the wording but from what I think the
    standard says:

    1. it's impossible to swap a restrict pointer with another pointer,
    i.e.

    int a = 1, b = 2;
    int * restrict ap = &a;
    int * restrict bp = &b;

    int *temp = bp;
    bp = ap;
    ap = bp;

    is undefined.

    2. it doesn't support exactly overlapping memory, i.e.

    void v3add(float * restrict a, float * restrict b)
    {
    a[0] += b[0];
    a[1] += b[1];
    a[2] += b[2];
    }

    float a[] = { 1, 2, 3 };
    v3add(a, a);

    is undefined.

    3. the library changes may break (correct?) existing code, i.e.

    FILE *fopen(const char * restrict filename, const char * restrict
    mode);

    FILE *f = fopen("foo.rt", "rt");

    if the compiler transforms this to:

    static const char str[] = "foo.rt";
    FILE *f = fopen(str, str + 4);

    the code becomes undefined.

    Is any of this correct?
    Me, Mar 6, 2006
    #1
    1. Advertising

  2. Me

    Jack Klein Guest

    On 5 Mar 2006 17:30:37 -0800, "Me" <>
    wrote in comp.lang.c:

    > I'm trying to wrap my head around the wording but from what I think the
    > standard says:
    >
    > 1. it's impossible to swap a restrict pointer with another pointer,
    > i.e.
    >
    > int a = 1, b = 2;
    > int * restrict ap = &a;
    > int * restrict bp = &b;
    >
    > int *temp = bp;


    This should require a cast, I believe.

    > bp = ap;
    > ap = bp;
    >
    > is undefined.


    Why do you think this is undefined? It might be, depending on what
    you do with the pointers.

    > 2. it doesn't support exactly overlapping memory, i.e.
    >
    > void v3add(float * restrict a, float * restrict b)
    > {
    > a[0] += b[0];
    > a[1] += b[1];
    > a[2] += b[2];
    > }
    >
    > float a[] = { 1, 2, 3 };
    > v3add(a, a);


    The function itself is well defined, the call to the function is, I
    suppose, technically undefined. Although there is no problem with
    this actual use.

    > is undefined.
    >
    > 3. the library changes may break (correct?) existing code, i.e.
    >
    > FILE *fopen(const char * restrict filename, const char * restrict
    > mode);
    >
    > FILE *f = fopen("foo.rt", "rt");
    >
    > if the compiler transforms this to:
    >
    > static const char str[] = "foo.rt";
    > FILE *f = fopen(str, str + 4);
    >
    > the code becomes undefined.


    No, the code above is well-defined. In fact, it is possible that a
    compiler might generate this code itself, as merging string literals
    is allowed by the standard and some compilers do it.

    > Is any of this correct?


    The restrict qualifier only has meaning in terms of modifying an
    object. That's why there is no problem at all with your third
    example. The two strings passed to fopen() are const qualified and
    the function does not try to modify them.

    Your second example is not really undefined because even though
    modifying objects pointed to by 'a' also modifies objects pointed to
    by 'b', there is no use of the value of any object pointed to by 'b'
    after it is modified by the write through 'a'.

    Consider this version of your second example:

    void v3add(float * restrict a, float * restrict b)
    {
    a[0] += b[0]; /* a[0] = b[0] = 2 */
    a[1] += b[0]; /* a[1] = 2 + 2 = 3 */
    a[2] += b[0]; /* a[1] =
    }

    int main()
    {
    float a[] = { 1, 2, 3 };
    v3add(a, a);
    /* printf() the values of 'a' */
    return 0;
    }

    Without the 'restrict' keyword above, the compiler cannot assume that
    'a' and 'b' point do not point to the same area. Specifically, they
    can't assume that b[0] is not changed by any of the assignments
    through 'a'. With the 'restrict' keyword it can assume, and generate
    code based on that assumption. It is quite likely that the code will
    actually read b[0] only once.

    The concept of the restrict type qualifier is to inform the compiler
    that the object(s) pointed to by a particular pointer will not be
    modified other than through that pointer, or a pointer derived from
    it.

    Consider:

    const int ci = 12;

    void some_func(void)
    {
    some_global_function();
    if (ci == 12)
    {
    printf("Yep, it's still 12\n");
    }
    }

    ....and:

    void other_func(int restrict *ip)
    {
    *ip = 12;
    some_global_function();
    if (*ip == 12)
    {
    printf("Yep, it's still 12\n");
    }
    }

    In both cases above, the compiler is justified in omitting the test
    and making the printf() call unconditional.

    This is true in the first place because it depends on the value of a
    const object remaining the same.

    In the second case, this is true because you have promised the
    compiler, when you tell it its argument is restrict qualified, that
    absolutely nothing that happens in the program will modify what ip
    points to without doing so through ip.

    This allows certain optimizations that would not be possible
    otherwise, namely the compiler does not have to perform the test "if
    (*ip == 12)". You have promised the compiler that whatever happens
    during the call to "some_global_func()", the object(s) pointed to by
    ip will not be modified.

    If the object(s) pointed to by restrict qualified pointers are const,
    or merely nothing attempts to modify them during the scope of a
    restrict qualified pointer, they keyword has no meaning at all.

    It is all about telling the compiler when it can assume that the
    pointed to object(s) will not be changed without its knowledge.

    --
    Jack Klein
    Home: http://JK-Technology.Com
    FAQs for
    comp.lang.c http://c-faq.com/
    comp.lang.c++ http://www.parashift.com/c -faq-lite/
    alt.comp.lang.learn.c-c++
    http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html
    Jack Klein, Mar 6, 2006
    #2
    1. Advertising

  3. Me

    Guest

    Jack Klein wrote:
    > On 5 Mar 2006 17:30:37 -0800, "Me" <>
    > wrote in comp.lang.c:
    >
    > > I'm trying to wrap my head around the wording but from what I think the
    > > standard says:
    > >
    > > 1. it's impossible to swap a restrict pointer with another pointer,
    > > i.e.
    > >
    > > int a = 1, b = 2;
    > > int * restrict ap = &a;
    > > int * restrict bp = &b;
    > >
    > > int *temp = bp;

    >
    > This should require a cast, I believe.


    Do you also think the setting of i below requires a cast?

    const int ci = 1;
    int i = ci;

    If not, can you explain how the two examples differ
    with regard to type qualifiers?
    , Mar 6, 2006
    #3
  4. Me

    Ian Collins Guest

    wrote:
    > Jack Klein wrote:
    >
    >>On 5 Mar 2006 17:30:37 -0800, "Me" <>
    >>wrote in comp.lang.c:
    >>
    >>
    >>>I'm trying to wrap my head around the wording but from what I think the
    >>>standard says:
    >>>
    >>>1. it's impossible to swap a restrict pointer with another pointer,
    >>>i.e.
    >>>
    >>>int a = 1, b = 2;
    >>>int * restrict ap = &a;
    >>>int * restrict bp = &b;
    >>>
    >>>int *temp = bp;

    >>
    >>This should require a cast, I believe.

    >
    >
    > Do you also think the setting of i below requires a cast?
    >
    > const int ci = 1;
    > int i = ci;
    >
    > If not, can you explain how the two examples differ
    > with regard to type qualifiers?
    >

    No it's a straight assignment. Nothing you do with i can change ci.
    whereas assigning a const pointer to a non-const violates the
    restriction because you can alter the value the pointer points to.

    --
    Ian Collins.
    Ian Collins, Mar 6, 2006
    #4
  5. Me

    Guest

    Ian Collins wrote:
    > wrote:
    > > Jack Klein wrote:
    > >
    > >>On 5 Mar 2006 17:30:37 -0800, "Me" <>
    > >>wrote in comp.lang.c:
    > >>
    > >>
    > >>>I'm trying to wrap my head around the wording but from what I think the
    > >>>standard says:
    > >>>
    > >>>1. it's impossible to swap a restrict pointer with another pointer,
    > >>>i.e.
    > >>>
    > >>>int a = 1, b = 2;
    > >>>int * restrict ap = &a;
    > >>>int * restrict bp = &b;
    > >>>
    > >>>int *temp = bp;
    > >>
    > >>This should require a cast, I believe.

    > >
    > >
    > > Do you also think the setting of i below requires a cast?
    > >
    > > const int ci = 1;
    > > int i = ci;
    > >
    > > If not, can you explain how the two examples differ
    > > with regard to type qualifiers?
    > >

    > No it's a straight assignment. Nothing you do with i can change ci.
    > whereas assigning a const pointer to a non-const violates the
    > restriction because you can alter the value the pointer points to.


    Read the original example again. The type qualifier
    modifies the type of the pointer, not the type of what
    the pointer points to.
    , Mar 6, 2006
    #5
  6. Me

    Robin Haigh Guest

    "Jack Klein" <> wrote in message
    news:...
    > On 5 Mar 2006 17:30:37 -0800, "Me" <>
    > wrote in comp.lang.c:
    >
    > > I'm trying to wrap my head around the wording but from what I think the
    > > standard says:
    > >
    > > 1. [snip]

    >
    > > 2. it doesn't support exactly overlapping memory, i.e.
    > >
    > > void v3add(float * restrict a, float * restrict b)
    > > {
    > > a[0] += b[0];
    > > a[1] += b[1];
    > > a[2] += b[2];
    > > }
    > >
    > > float a[] = { 1, 2, 3 };
    > > v3add(a, a);
    > >
    > > is undefined.

    >
    > The function itself is well defined, the call to the function is, I
    > suppose, technically undefined. Although there is no problem with
    > this actual use.
    >
    > > 3. [snip]

    >
    > Your second example is not really undefined because even though
    > modifying objects pointed to by 'a' also modifies objects pointed to
    > by 'b', there is no use of the value of any object pointed to by 'b'
    > after it is modified by the write through 'a'.


    Trouble is, restrict gives the compiler unlimited licence to rearrange.
    Just because the source as written doesn't access any object after it's
    modified, even when there's aliasing, doesn't mean the compiler can't
    introduce such an access.

    Consider this reversal of your example:

    void v3add(float * restrict a, float * restrict b)
    {
    float b0;
    a[0] += b0 = b[0];
    a[1] += b0;
    a[2] += b0;
    }

    The compiler, relying on restrict, might decide to eliminate b0 by accessing
    b[0] 3 times (well I didn't say it was a good compiler). Now, v3add(a, a)
    breaks even though nothing is accessed after it's modified in the source as
    written.

    It seems the OP is right, aliasing restricted pointers is absolutely
    dangerous. We can't anticipate all possible bright ideas that the compiler
    might have and decide that the aliasing will survive all of them. If we
    want the code compiled with the semantics as written, we have to avoid
    restrict and stick to documenting the restrictions on overlaps.

    --
    RSH
    Robin Haigh, Mar 6, 2006
    #6
  7. Me

    Ian Collins Guest

    wrote:
    > Ian Collins wrote:
    >
    >> wrote:
    >>
    >>>Jack Klein wrote:
    >>>
    >>>
    >>>>On 5 Mar 2006 17:30:37 -0800, "Me" <>
    >>>>wrote in comp.lang.c:
    >>>>
    >>>>
    >>>>
    >>>>>I'm trying to wrap my head around the wording but from what I think the
    >>>>>standard says:
    >>>>>
    >>>>>1. it's impossible to swap a restrict pointer with another pointer,
    >>>>>i.e.
    >>>>>
    >>>>>int a = 1, b = 2;
    >>>>>int * restrict ap = &a;
    >>>>>int * restrict bp = &b;
    >>>>>
    >>>>>int *temp = bp;
    >>>>
    >>>>This should require a cast, I believe.
    >>>
    >>>
    >>>Do you also think the setting of i below requires a cast?
    >>>
    >>> const int ci = 1;
    >>> int i = ci;
    >>>
    >>>If not, can you explain how the two examples differ
    >>>with regard to type qualifiers?
    >>>

    >>
    >>No it's a straight assignment. Nothing you do with i can change ci.
    >>whereas assigning a const pointer to a non-const violates the
    >>restriction because you can alter the value the pointer points to.

    >
    >
    > Read the original example again. The type qualifier
    > modifies the type of the pointer, not the type of what
    > the pointer points to.
    >

    Your are correct, but this doesn't invalidate the first part of the answer.

    My understanding is the expression 'int *temp = bp;' is valid because
    temp is a pointer based on bp. Please correct me if I'm wrong. I don't
    see where a cast would be required.


    --
    Ian Collins.
    Ian Collins, Mar 6, 2006
    #7
  8. Me

    Guest

    Ian Collins wrote:
    > wrote:
    > > Ian Collins wrote:
    > >
    > >> wrote:
    > >>
    > >>>Jack Klein wrote:
    > >>>
    > >>>
    > >>>>On 5 Mar 2006 17:30:37 -0800, "Me" <>
    > >>>>wrote in comp.lang.c:
    > >>>>
    > >>>>
    > >>>>
    > >>>>>I'm trying to wrap my head around the wording but from what I think the
    > >>>>>standard says:
    > >>>>>
    > >>>>>1. it's impossible to swap a restrict pointer with another pointer,
    > >>>>>i.e.
    > >>>>>
    > >>>>>int a = 1, b = 2;
    > >>>>>int * restrict ap = &a;
    > >>>>>int * restrict bp = &b;
    > >>>>>
    > >>>>>int *temp = bp;
    > >>>>
    > >>>>This should require a cast, I believe.
    > >>>
    > >>>
    > >>>Do you also think the setting of i below requires a cast?
    > >>>
    > >>> const int ci = 1;
    > >>> int i = ci;
    > >>>
    > >>>If not, can you explain how the two examples differ
    > >>>with regard to type qualifiers?
    > >>>
    > >>
    > >>No it's a straight assignment. Nothing you do with i can change ci.
    > >>whereas assigning a const pointer to a non-const violates the
    > >>restriction because you can alter the value the pointer points to.

    > >
    > >
    > > Read the original example again. The type qualifier
    > > modifies the type of the pointer, not the type of what
    > > the pointer points to.
    > >

    > Your are correct, but this doesn't invalidate the first part of the answer.
    >
    > My understanding is the expression 'int *temp = bp;' is valid because
    > temp is a pointer based on bp. Please correct me if I'm wrong. I don't
    > see where a cast would be required.


    That's the point I was making. 'int *temp = bp;' does not
    require a cast.
    , Mar 6, 2006
    #8
  9. Me

    S.Tobias Guest

    Jack Klein <> wrote:
    > On 5 Mar 2006 17:30:37 -0800, "Me" <>
    > wrote in comp.lang.c:


    >> FILE *fopen(const char * restrict filename, const char * restrict
    >> mode);
    >>
    >> FILE *f = fopen("foo.rt", "rt");
    >>
    >> if the compiler transforms this to:
    >>
    >> static const char str[] = "foo.rt";
    >> FILE *f = fopen(str, str + 4);
    >>
    >> the code becomes undefined.

    >
    > No, the code above is well-defined. In fact, it is possible that a
    > compiler might generate this code itself, as merging string literals
    > is allowed by the standard and some compilers do it.
    >

    So what is the point in declaring parameters as restrict pointers
    to const data?

    Since the data may be const, the function presumably does not try to
    modify it, therefore `restrict' seems to take effect neither in the
    function definition (if there is any) nor as a requirement for the caller.

    --
    Stan Tobias
    mailx `echo LID | sed s/[[:upper:]]//g`
    S.Tobias, Mar 6, 2006
    #9
  10. In article <>,
    "S.Tobias" <> wrote:

    > Jack Klein <> wrote:
    > > On 5 Mar 2006 17:30:37 -0800, "Me" <>
    > > wrote in comp.lang.c:

    >
    > >> FILE *fopen(const char * restrict filename, const char * restrict
    > >> mode);
    > >>
    > >> FILE *f = fopen("foo.rt", "rt");
    > >>
    > >> if the compiler transforms this to:
    > >>
    > >> static const char str[] = "foo.rt";
    > >> FILE *f = fopen(str, str + 4);
    > >>
    > >> the code becomes undefined.

    > >
    > > No, the code above is well-defined. In fact, it is possible that a
    > > compiler might generate this code itself, as merging string literals
    > > is allowed by the standard and some compilers do it.
    > >

    > So what is the point in declaring parameters as restrict pointers
    > to const data?
    >
    > Since the data may be const, the function presumably does not try to
    > modify it, therefore `restrict' seems to take effect neither in the
    > function definition (if there is any) nor as a requirement for the caller.


    Just because you have a const pointer pointing to the data doesn't mean
    it is const. All it means that you cannot modify the data through this
    pointer without a cast, but it can be modified by other means.

    Example:

    static int x;
    int f (const int* p)
    {
    if (*p == 0) ++x;
    if (*p == 0) ++x;
    return *p;
    }

    An optimising compiler might be tempted to produce code that doesn't
    read *p three times, but instead translates it as if I had written:

    static int x;
    int f (const int* p)
    {
    int tmp = *p;
    if (tmp == 0) x += 2;
    return tmp;
    }

    But this would be wrong, because I could call this as

    int y = f (&x);

    If x happens to be zero before the call, then it must be incremented
    only once and a value of 1 must be returned, so the compiler is forced
    to produce slower code. If you write

    int f (const int* restrict p)

    then it is guaranteed by the programmer that nothing will modify *p
    while the function is running. The programmer guarantees that he/she
    doesn't pass &x when x is 0.
    Christian Bau, Mar 6, 2006
    #10
  11. Me

    Me Guest

    Jack Klein wrote:
    > On 5 Mar 2006 17:30:37 -0800, "Me" <>
    > wrote in comp.lang.c:
    >
    > > I'm trying to wrap my head around the wording but from what I think the
    > > standard says:
    > >
    > > 1. it's impossible to swap a restrict pointer with another pointer,
    > > i.e.
    > >
    > > int a = 1, b = 2;
    > > int * restrict ap = &a;
    > > int * restrict bp = &b;
    > >
    > > int *temp = bp;

    >
    > This should require a cast, I believe.
    >
    > > bp = ap;
    > > ap = bp;
    > >
    > > is undefined.

    >
    > Why do you think this is undefined?


    Namely because I've spent a few hours trying to understand wtf 6.7.3.1
    says (and it's only half a page long!) and I still have no clue.

    6.7.3.1/11 has an example that looks like swapping is undefined (if you
    ignore the mistake they made of doing an uninitialized assignment)
    because it looks like a simple assignment from one restrict pointer to
    another with no other use at all is undefined and if you generalize
    this example:

    int * restrict a = &foo;
    int * restrict b = &boo;

    memmove(&a, &b, sizeof(a));

    and:

    void memswap(void *a, void *b, size_t s)
    {
    unsigned char *ap = a;
    unsigned char *bp = b;
    while (s--) {
    unsigned char temp = *ap;
    *ap++ = *bp;
    *bp++ = temp;
    }
    }

    memswap(&a, &b, sizeof(a));

    would also be undefined which seems extremely unsettling to me.

    > It might be, depending on what
    > you do with the pointers.


    How about this use:

    int a, b;
    int * restrict ap = &a;
    int * restrict bp = &b;

    *ap = 1;
    *bp = 2;

    int *temp = bp;
    bp = ap;
    ap = temp;

    *ap = 3;
    *bp = 4;

    I have some vague idea of what 'restrict' means, namely all that all
    reads from a restricted pointer in a scope should assume nobody else
    wrote to it. But from the wording and the mostly examples given it
    looks even more restricted (hah) than that in some cases. Though my
    vague idea seems too unusable because:

    int buf[4] = { 1, 2, 3, 4 };
    int * restrict a = buf;
    int val = a[0];
    memmove(buf, buf[1], 2);
    int val2 = a[1];

    If my idea is true then the compiler can move the a[1] read above the
    memmove.
    Me, Mar 6, 2006
    #11
  12. Me

    Jack Klein Guest

    On 5 Mar 2006 21:55:29 -0800, wrote in comp.lang.c:

    >
    > Jack Klein wrote:
    > > On 5 Mar 2006 17:30:37 -0800, "Me" <>
    > > wrote in comp.lang.c:
    > >
    > > > I'm trying to wrap my head around the wording but from what I think the
    > > > standard says:
    > > >
    > > > 1. it's impossible to swap a restrict pointer with another pointer,
    > > > i.e.
    > > >
    > > > int a = 1, b = 2;
    > > > int * restrict ap = &a;
    > > > int * restrict bp = &b;
    > > >
    > > > int *temp = bp;

    > >
    > > This should require a cast, I believe.

    >
    > Do you also think the setting of i below requires a cast?
    >
    > const int ci = 1;
    > int i = ci;
    >
    > If not, can you explain how the two examples differ
    > with regard to type qualifiers?


    You are correct on this point, I was not.

    --
    Jack Klein
    Home: http://JK-Technology.Com
    FAQs for
    comp.lang.c http://c-faq.com/
    comp.lang.c++ http://www.parashift.com/c -faq-lite/
    alt.comp.lang.learn.c-c++
    http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html
    Jack Klein, Mar 7, 2006
    #12
  13. Me

    Chris Torek Guest

    In article <>
    Me <> wrote:
    >Namely because I've spent a few hours trying to understand wtf 6.7.3.1
    >says (and it's only half a page long!) and I still have no clue.


    The definition of "restrict" in my C99 draft is complicated,
    and I have avoided studying it in detail in case it is different
    from that in the actual standard.

    >I have some vague idea of what 'restrict' means, namely all that all
    >reads from a restricted pointer in a scope should assume nobody else
    >wrote to it.


    More or less. The goal is certainly clear enough: it is meant to
    give optimizing compilers a lot of latitude to make assumptions
    about aliasing. In particular, aliases (if any) should be "locally
    visible".

    In the absence of the "restrict" qualifier, a pointer P of type
    "pointer to T" could point to *any* object of type T, so after
    *any* write to *any* "object of type T", the object at *P is no
    longer knowable. (This means that a write to *P cannot be deferred,
    and a later read-back of *P must occur. This also holds for writes
    to objects with character type, due to the ability to use an
    "unsigned char *" to take objects apart into bytes, and in at least
    some cases to objects held in unions.)

    Given a restrict-qualified pointer R, however, the compiler can
    track uses of R and *R and "know" when *R might or might not change,
    without having to analyze the entire program. Simply looking at
    those parts that use R and/or *R alone should suffice.

    Unfortunately, describing the desired properties in a form general
    enough to be useful to compiler-writers, but specific enough to be
    useful to programmers, is hard. :)
    --
    In-Real-Life: Chris Torek, Wind River Systems
    Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: forget about it http://web.torek.net/torek/index.html
    Reading email is like searching for food in the garbage, thanks to spammers.
    Chris Torek, Mar 7, 2006
    #13
    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. =?Utf-8?B?UmFlZCBTYXdhbGhh?=

    English/English DLL

    =?Utf-8?B?UmFlZCBTYXdhbGhh?=, Oct 15, 2005, in forum: ASP .Net
    Replies:
    2
    Views:
    1,674
    =?Utf-8?B?UmFlZCBTYXdhbGhh?=
    Oct 16, 2005
  2. IchBin
    Replies:
    1
    Views:
    774
  3. =?Utf-8?B?Q2hhcmxlc0E=?=

    plain english article on how asp.net works with http?

    =?Utf-8?B?Q2hhcmxlc0E=?=, Mar 16, 2007, in forum: ASP .Net
    Replies:
    5
    Views:
    377
    =?Utf-8?B?Q2hhcmxlc0E=?=
    Mar 17, 2007
  4. luke
    Replies:
    4
    Views:
    115
    Gene Tani
    Jul 7, 2005
  5. Varun Goel

    Plain english to condition??

    Varun Goel, May 7, 2008, in forum: Ruby
    Replies:
    1
    Views:
    106
    Daniel Finnie
    May 7, 2008
Loading...

Share This Page