'restrict' in plain English?

[Me]

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?

[Jack Klein]

On 5 Mar 2006 17:30:37 -0800, "Me" <an*****************@yahoo.com>
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/~a...FAQ-acllc.html

[ena8t8si]

Jack Klein wrote:

On 5 Mar 2006 17:30:37 -0800, "Me" <an*****************@yahoo.com>
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?

[Ian Collins]

en******@yahoo.com wrote:

Jack Klein wrote:

On 5 Mar 2006 17:30:37 -0800, "Me" <an*****************@yahoo.com>
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.

[ena8t8si]

Ian Collins wrote:

en******@yahoo.com wrote:

Jack Klein wrote:

On 5 Mar 2006 17:30:37 -0800, "Me" <an*****************@yahoo.com>
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.

[Robin Haigh]

"Jack Klein" <ja*******@spamcop.net> wrote in message
news:h9********************************@4ax.com...

On 5 Mar 2006 17:30:37 -0800, "Me" <an*****************@yahoo.com>
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

[Ian Collins]

en******@yahoo.com wrote:

Ian Collins wrote:

en******@yahoo.com wrote:

Jack Klein wrote:
On 5 Mar 2006 17:30:37 -0800, "Me" <an*****************@yahoo.com>
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.

[ena8t8si]

Ian Collins wrote:

en******@yahoo.com wrote:

Ian Collins wrote:

en******@yahoo.com wrote:

Jack Klein wrote:
>On 5 Mar 2006 17:30:37 -0800, "Me" <an*****************@yahoo.com>
>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.

[S.Tobias]

Jack Klein <ja*******@spamcop.net> wrote:

On 5 Mar 2006 17:30:37 -0800, "Me" <an*****************@yahoo.com>
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 si***@FamOuS.BedBuG.pAlS.INVALID | sed s/[[:upper:]]//g`

[Christian Bau]

In article <47************@individual.net>,
"S.Tobias" <si***@FamOuS.BedBuG.pAlS.INVALID> wrote:

Jack Klein <ja*******@spamcop.net> wrote:

On 5 Mar 2006 17:30:37 -0800, "Me" <an*****************@yahoo.com>
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.

[Me]

Jack Klein wrote:

On 5 Mar 2006 17:30:37 -0800, "Me" <an*****************@yahoo.com>
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.

[Jack Klein]

On 5 Mar 2006 21:55:29 -0800, en******@yahoo.com wrote in comp.lang.c:

Jack Klein wrote:

On 5 Mar 2006 17:30:37 -0800, "Me" <an*****************@yahoo.com>
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/~a...FAQ-acllc.html

[Chris Torek]

In article <11**********************@j33g2000cwa.googlegroups .com>
Me <an*****************@yahoo.com> 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) [phone]
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.