By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
429,313 Members | 2,725 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,313 IT Pros & Developers. It's quick & easy.

What does 'restrict' mean?

P: n/a
I see a lot of use in function declarations, such as

size_t fread(void* restrict ptr, size_t size, size_t nobj, FILE*
restrict fp);

but what does the keyword 'restrict' mean? there is no definition found
in K&R 2nd.
Apr 3 '06 #1
Share this Question
Share on Google+
21 Replies


P: n/a
Niu Xiao <gn******@gmail.com> writes:
I see a lot of use in function declarations, such as

size_t fread(void* restrict ptr, size_t size, size_t nobj, FILE*
restrict fp);

but what does the keyword 'restrict' mean? there is no definition
found in K&R 2nd.


restrict keyword

C99 supports the restrict keyword, which allows for certain
optimizations involving pointers. For example:

void copy(int *restrict d, const int *restrict s, int n)
{
while (n-- > 0)
*d++ = *s++;
}

C++ does not recognize this keyword.

A simple work-around for code that is meant to be compiled as
either C or C++ is to use a macro for the restrict keyword:

#ifdef __cplusplus
#define restrict /* nothing */
#endif

(This feature is likely to be provided as an extension by many
C++ compilers. If it is, it is also likely to be allowed as a
reference modifier as well as a pointer modifier.)

[C99: §6.2.5, 6.4.1, 6.7.3, 6.7.3.1, 7, A.1.2, J.2]
[C++98: §2.11]



from http://david.tribble.com/text/cdiffs.htm#C99-restrict

--
burton samograd kruhft .at. gmail
kruhft.blogspot.com www.myspace.com/kruhft metashell.blogspot.com
Apr 3 '06 #2

P: n/a
Burton Samograd wrote:
Niu Xiao <gn******@gmail.com> writes:

I see a lot of use in function declarations, such as

size_t fread(void* restrict ptr, size_t size, size_t nobj, FILE*
restrict fp);

but what does the keyword 'restrict' mean? there is no definition
found in K&R 2nd.

restrict keyword

C99 supports the restrict keyword, which allows for certain
optimizations involving pointers. For example:

void copy(int *restrict d, const int *restrict s, int n)
{
while (n-- > 0)
*d++ = *s++;
}

C++ does not recognize this keyword.

A simple work-around for code that is meant to be compiled as
either C or C++ is to use a macro for the restrict keyword:

#ifdef __cplusplus
#define restrict /* nothing */
#endif

(This feature is likely to be provided as an extension by many
C++ compilers. If it is, it is also likely to be allowed as a
reference modifier as well as a pointer modifier.)

[C99: 6.2.5, 6.4.1, 6.7.3, 6.7.3.1, 7, A.1.2, J.2]
[C++98: 2.11]



from http://david.tribble.com/text/cdiffs.htm#C99-restrict


but what optimizations invoving pointers?
Apr 3 '06 #3

P: n/a
Burton Samograd <kr**********@gmail.com> wrote:
Niu Xiao <gn******@gmail.com> writes:
I see a lot of use in function declarations, such as

size_t fread(void* restrict ptr, size_t size, size_t nobj, FILE*
restrict fp);

but what does the keyword 'restrict' mean? there is no definition
found in K&R 2nd.


restrict keyword

C99 supports the restrict keyword,


And note that the reason you won't find it in K&R 2 is that that book
covers C(almost-)89, not C99.

Richard
Apr 3 '06 #4

P: n/a
Niu Xiao wrote:

I see a lot of use in function declarations, such as

size_t fread(void* restrict ptr, size_t size, size_t nobj, FILE*
restrict fp);

but what does the keyword 'restrict' mean?
there is no definition found
in K&R 2nd.


Consider the types of memcpy and memmove:

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

The reason that memcpy has the restrict keyword and memmove doesn't
is because the parameters don't overlap in memcpy,
but they are allowed to, in memmove.

What it means is that in memcpy,
all accesses to the object pointed by s1,
will be made from s1 or pointers derived from s1
and that all accesses to the object pointed to by s2
will be made from s2 or pointers derived from s2.
There may or may not be optimizations available
because of that. Bear in mind that standard library functions
can be written in assembley langauge or any language.

In memmove, because the objects may overlap,
it's possible to be accessing both objects at the same time
with the same pointer.

--
pete
Apr 3 '06 #5

P: n/a
Niu Xiao schrieb:
Burton Samograd wrote:
Niu Xiao <gn******@gmail.com> writes:
I see a lot of use in function declarations, such as

size_t fread(void* restrict ptr, size_t size, size_t nobj, FILE*
restrict fp);

but what does the keyword 'restrict' mean? there is no definition
found in K&R 2nd.


restrict keyword
C99 supports the restrict keyword, which allows for certain
optimizations involving pointers. For example:
void copy(int *restrict d, const int *restrict s, int n)
{
while (n-- > 0)
*d++ = *s++;
} C++ does not recognize this keyword.
A simple work-around for code that is meant to be compiled as
either C or C++ is to use a macro for the restrict keyword:
#ifdef __cplusplus
#define restrict /* nothing */
#endif (This feature is likely to be provided as an
extension by many
C++ compilers. If it is, it is also likely to be allowed as a
reference modifier as well as a pointer modifier.)
[C99: §6.2.5, 6.4.1, 6.7.3, 6.7.3.1, 7, A.1.2, J.2]
[C++98: §2.11]


from http://david.tribble.com/text/cdiffs.htm#C99-restrict


but what optimizations invoving pointers?


If you know that two pointers do not point to the same object,
then you can leave out some kinds of sanity checks, can change
loops (e.g. make a while (a!=b) loop into a do--while(a != b)
loop), can work directly without intermediate copy.
Think of memcpy() and memmove(). If you had to implement
memmove() portably and had no way of checking whether the source
and destination pointers belong to the same object, you were
not allowed to compare the pointers with < or >, thus you cannot
take care of overlapping objects flexibly. This means that you
have to do something along the lines of

void *MemMove (void *pDest, void *pSrc, size_t size)
{
if (pDest == pSrc) {
return pDest;
}
void *pTemp = malloc(size);
if (pTemp) {
unsigned char * pMDest = pTemp;
unsigned char * pMSrc = pSrc;
for (size_t i = 0; i < size; i++) {
*pMDest++ = *pMSrc++;
}
pMDest = pDest;
pMSrc = pTemp;
for (size_t i = 0; i < size; i++) {
*pMDest++ = *pMSrc++;
}
free(pTemp);
pTemp = pDest;
}
return pTemp;
}

which may be pretty wasteful of memory. For MemCopy(), you
can do

void *MemCopy (void * restrict pDest,
void * restrict pSrc, size_t size)
{
unsigned char * restrict pCDest = pDest;
unsigned char * restrict pCSrc = pSrc;
for (size_t i = 0; i < size; i++) {
*pCDest++ = *pCSrc++;
}
return pDest;
}

That is quite a difference, I'd say.
Now, imagine for a moment we were an optimizing compiler and
would optimize the following function

1)
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
/* Never true: Can be thrown away */
if (pDest == pSrc) {
return pDest;
}
void *pTemp = malloc(size);
if (pTemp) {
unsigned char * pMDest = pTemp;
unsigned char * pMSrc = pSrc;
/* Loops can be merged if auxiliary variable is introduced */
for (size_t i = 0; i < size; i++) {
*pMDest++ = *pMSrc++;
}
pMDest = pDest;
pMSrc = pTemp;
for (size_t i = 0; i < size; i++) {
*pMDest++ = *pMSrc++;
}
free(pTemp);
pTemp = pDest;
}
return pTemp;
}

2)
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
void *pTemp = malloc(size);
if (pTemp) {
unsigned char * pMDest = pTemp;
unsigned char * restrict pMSrc = pSrc;
unsigned char * restrict pAux = pDest;
for (size_t i = 0; i < size; i++) {
/* pMDest is only used to change the object pointed to by pTemp */
*pMDest++ = *pMSrc++;
*pAux++ = *pMDest++;
}
/* The object pointed to by pTemp is not used after the redefinition */
free(pTemp);
pTemp = pDest;
}
return pTemp;
}

3)
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
unsigned char *pTemp = malloc(size);
if (pTemp) {
unsigned char * restrict pMSrc = pSrc;
unsigned char * restrict pAux = pDest;
for (size_t i = 0; i < size; i++) {
*pAux++ = *pMSrc++;
}
/* Code could be rescheduled to sooner free resources */
free(pTemp);
pTemp = pDest;
}
return pTemp;
}

4)
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
unsigned char *pTemp = malloc(size);
if (pTemp) {
free(pTemp);
pTemp = pDest;
unsigned char * restrict pMSrc = pSrc;
unsigned char * restrict pAux = pDest;
for (size_t i = 0; i < size; i++) {
*pAux++ = *pMSrc++;
}
}
return pTemp;
}

Not the optimum. If we imagine for a moment a compiler that
can do truly wondrous things, then we could eliminate the
calls to malloc() and free() as there is only a use of pTemp
in a Boolean context in between.

5->7)
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
unsigned char *pTemp;
if (size <= __MAX_MALLOC) {
pTemp = pDest;
unsigned char * restrict pMSrc = pSrc;
unsigned char * restrict pAux = pDest;
for (size_t i = 0; i < size; i++) {
*pAux++ = *pMSrc++;
}
}
else {
pTemp = NULL;
}
return pTemp;
}

where __MAX_MALLOC may be an implementation dependent constant
defining the maximal number of bytes that can be allocated by
one call to malloc().
If __MAX_MALLOC does not exist, we arrive at MemCpy(), otherwise
we arrive at

void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
if (size <= __MAX_MALLOC) {
unsigned char * restrict pMSrc = pSrc;
unsigned char * restrict pAux = pDest;
for (size_t i = 0; i < size; i++) {
*pAux++ = *pMSrc++;
}
return pDest;
}
return NULL;
}

Nice, huh?
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Apr 3 '06 #6

P: n/a
Michael Mair schrieb:
Now, imagine for a moment we were an optimizing compiler and
would optimize the following function

1)
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
/* Never true: Can be thrown away */
if (pDest == pSrc) {
return pDest;
}
void *pTemp = malloc(size);
if (pTemp) {
unsigned char * pMDest = pTemp;
unsigned char * pMSrc = pSrc;
/* Loops can be merged if auxiliary variable is introduced */
for (size_t i = 0; i < size; i++) {
*pMDest++ = *pMSrc++;
}
pMDest = pDest;
pMSrc = pTemp;
for (size_t i = 0; i < size; i++) {
*pMDest++ = *pMSrc++;
}
Note that this is the crucial step: We only may merge the loops
without further thought if pDest and pSrc are guarantueed to not
point to the same object.
I failed to make this clear originally.
free(pTemp);
pTemp = pDest;
}
return pTemp;
}


Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Apr 4 '06 #7

P: n/a
Niu Xiao wrote:
I see a lot of use in function declarations, such as

size_t fread(void* restrict ptr, size_t size, size_t nobj, FILE*
restrict fp);

but what does the keyword 'restrict' mean? there is no definition found
in K&R 2nd.

thanks for ur help :-)
Apr 4 '06 #8

P: n/a
Niu Xiao opined:
Niu Xiao wrote:
I see a lot of use in function declarations, such as

size_t fread(void* restrict ptr, size_t size, size_t nobj, FILE*
restrict fp);

but what does the keyword 'restrict' mean? there is no definition
found in K&R 2nd.

thanks for ur help :-)

^^

I didn't think it was that ancient...

--
A bird in the hand is worth what it will bring.

<http://clc-wiki.net/wiki/Introduction_to_comp.lang.c>

Apr 4 '06 #9

P: n/a
Me
Michael Mair wrote:
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
/* Never true: Can be thrown away */
if (pDest == pSrc) {
return pDest;
}


I don't think that's true.

Apr 4 '06 #10

P: n/a
Me wrote:

Michael Mair wrote:
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
/* Never true: Can be thrown away */
if (pDest == pSrc) {
return pDest;
}


I don't think that's true.


Do you think it's OK to call memcpy
with the first two arguments being equal?

--
pete
Apr 4 '06 #11

P: n/a
Me
pete wrote:
Me wrote:

Michael Mair wrote:
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
/* Never true: Can be thrown away */
if (pDest == pSrc) {
return pDest;
}


I don't think that's true.


Do you think it's OK to call memcpy
with the first two arguments being equal?


I think it's ok but it ultimately depends on if the committee considers
[p,p+0) and [p,p+0) overlapping or not. If they don't for the same
object then they should at least consider it not overlapping for the
end+1 and beginning of another object that just happens to compare
equal.

In any event, take a look at 6.7.3.1/10 as to why memcpy's semantics
looks irrelevant in this case.

Apr 4 '06 #12

P: n/a
pete wrote:
Me wrote:
Michael Mair wrote:
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
/* Never true: Can be thrown away */
if (pDest == pSrc) {
return pDest;
}


I don't think that's true.


Do you think it's OK to call memcpy
with the first two arguments being equal?


Doesn't the restrict by itself forbid those arguments from being
equal?

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

Apr 4 '06 #13

P: n/a
pete wrote:
Me wrote:
Michael Mair wrote:
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
/* Never true: Can be thrown away */
if (pDest == pSrc) {
return pDest;
}

I don't think that's true.


Do you think it's OK to call memcpy
with the first two arguments being equal?


I don't, since if they are equal the regions obviously overlap so the
behaviour is undefined.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc
Apr 4 '06 #14

P: n/a
Me schrieb:
Michael Mair wrote:
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
/* Never true: Can be thrown away */
if (pDest == pSrc) {
return pDest;
}


I don't think that's true.


I forgot to make sure that neither pDest nor pSrc is a null
pointer -- this part should have been excluded beforehand;
if we assume that we know that neither is a null pointer,
then -- if I have understood restrict right -- this means
that pDest cannot be equal to pSrc.
Is this what you are getting at?
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Apr 4 '06 #15

P: n/a
CBFalconer <cb********@yahoo.com> writes:
pete wrote:
Me wrote:
Michael Mair wrote:

void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
/* Never true: Can be thrown away */
if (pDest == pSrc) {
return pDest;
}

I don't think that's true.


Do you think it's OK to call memcpy
with the first two arguments being equal?


Doesn't the restrict by itself forbid those arguments from being
equal?


It doesn't forbid anything. It causes undefined behavior if they
overlap (which includes the case where they're equal) -- which means
the compiler could legally replace "if (pDest == pSrc)" with "if (0)".

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Apr 4 '06 #16

P: n/a
Keith Thompson wrote:
CBFalconer <cb********@yahoo.com> writes:

.... snip ...

Doesn't the restrict by itself forbid those arguments from being
equal?


It doesn't forbid anything. It causes undefined behavior if they
overlap (which includes the case where they're equal) -- which means
the compiler could legally replace "if (pDest == pSrc)" with "if (0)".


Oh very well. It forbids the programmer, on pain of undefined
behaviour, from supplying equal arguments.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

Apr 4 '06 #17

P: n/a
Me
Michael Mair wrote:
Me schrieb:
Michael Mair wrote:
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
/* Never true: Can be thrown away */
if (pDest == pSrc) {
return pDest;
}


I don't think that's true.


I forgot to make sure that neither pDest nor pSrc is a null
pointer -- this part should have been excluded beforehand;
if we assume that we know that neither is a null pointer,
then -- if I have understood restrict right -- this means
that pDest cannot be equal to pSrc.
Is this what you are getting at?


No, I'm saying that just because a pointer is marked as restrict
doesn't give the compiler any information at all to say if it overlaps
with another object or not. It has to examine the use of the pointer
expressions inside a block to determine this information, hence the
comparison of the pointers in MemFoo cannot be eliminated as is.
Christian Bau's post about restrict is a pretty good approximation to
what the standard says:

http://groups.google.com/group/comp....4409dea7e43736

just be careful when reading it because he uses "const restrict
pointer" to mean "const T * restrict".

http://www.lysator.liu.se/c/restrict.html

Is also a good (outdated) reference. The most important piece of
information to glean from it is 3.9 which describes how return values
and typecasts with restrict are meaningless.
To summarize what's ok and what isn't with just the minimum amount of
information:

void f(int *restrict, int *restrict){}

/* ok */
int a;
f(&a, &a);

/* also ok */
int a;
int *restrict pa = &a;
int *restrict pb = &a;
f(pa, pb);

/* undefined */
int a;
int *restrict pa = &a;
f(pa, pa);

Apr 5 '06 #18

P: n/a
"Me" <an*****************@yahoo.com> wrote:
Michael Mair wrote:
Me schrieb:
Michael Mair wrote:

> void *MemFoo (void * restrict pDest,
> void * restrict pSrc, size_t size)
> {
>/* Never true: Can be thrown away */
> if (pDest == pSrc) {
> return pDest;
> }

I don't think that's true.
I forgot to make sure that neither pDest nor pSrc is a null
pointer -- this part should have been excluded beforehand;
if we assume that we know that neither is a null pointer,
then -- if I have understood restrict right -- this means
that pDest cannot be equal to pSrc.
Is this what you are getting at?


No, I'm saying that just because a pointer is marked as restrict
doesn't give the compiler any information at all to say if it overlaps
with another object or not.


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.
void f(int *restrict, int *restrict){}

/* ok */
int a;
f(&a, &a);

/* also ok */
int a;
int *restrict pa = &a;
int *restrict pb = &a;
f(pa, pb);


Not OK, and not OK, except for the quibble that your function body is
empty (and the declaration incomplete). 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)

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,
_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.

Richard
Apr 5 '06 #19

P: n/a
Me schrieb:
Michael Mair wrote:
Me schrieb:
Michael Mair wrote:

void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
/* Never true: Can be thrown away */
if (pDest == pSrc) {
return pDest;
}

I don't think that's true.
I forgot to make sure that neither pDest nor pSrc is a null
pointer -- this part should have been excluded beforehand;
if we assume that we know that neither is a null pointer,
then -- if I have understood restrict right -- this means
that pDest cannot be equal to pSrc.
Is this what you are getting at?


No, I'm saying that just because a pointer is marked as restrict
doesn't give the compiler any information at all to say if it overlaps
with another object or not. It has to examine the use of the pointer
expressions inside a block to determine this information, hence the
comparison of the pointers in MemFoo cannot be eliminated as is.


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.
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.
Christian Bau's post about restrict is a pretty good approximation to
what the standard says:

http://groups.google.com/group/comp....4409dea7e43736
Thanks for the link.
just be careful when reading it because he uses "const restrict
pointer" to mean "const T * restrict".

http://www.lysator.liu.se/c/restrict.html

Is also a good (outdated) reference. The most important piece of
information to glean from it is 3.9 which describes how return values
and typecasts with restrict are meaningless.
Which is consistent.

To summarize what's ok and what isn't with just the minimum amount of
information:

void f(int *restrict, int *restrict){}

/* ok */
int a;
f(&a, &a);
I'd expect at least a warning from a good compiler in this case.

/* also ok */
int a;
int *restrict pa = &a;
int *restrict pb = &a;
f(pa, pb);
The same. The only reason why I see this and the above as safe is
that f()'s body is empty.
/* undefined */
int a;
int *restrict pa = &a;
f(pa, pa);


Here we agree.

I do not know if there are compilers who actually use the
information gleaned from restrict or who even use it aggressively;
I really would welcome a compiler writer's point of view for this
case as it may clarify potential and actual uses as well as less
obvious defects in the specification of restrict.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Apr 6 '06 #20

P: n/a
Me
Richard Bos wrote:
"Me" <an*****************@yahoo.com> wrote:
No, I'm saying that just because a pointer is marked as restrict
doesn't give the compiler any information at all to say if it overlaps
with another object or not.
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.
void f(int *restrict, int *restrict){}

/* ok */
int a;
f(&a, &a);

/* also ok */
int a;
int *restrict pa = &a;
int *restrict pb = &a;
f(pa, pb);


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

Apr 6 '06 #21

P: n/a
Me
Michael Mair wrote:
Me schrieb:
Michael Mair wrote:
Me schrieb:
Michael Mair wrote:

> void *MemFoo (void * restrict pDest,
> void * restrict pSrc, size_t size)
> {
>/* Never true: Can be thrown away */
> if (pDest == pSrc) {
> return pDest;
> }

I don't think that's true.

I forgot to make sure that neither pDest nor pSrc is a null
pointer -- this part should have been excluded beforehand;
if we assume that we know that neither is a null pointer,
then -- if I have understood restrict right -- this means
that pDest cannot be equal to pSrc.
Is this what you are getting at?
No, I'm saying that just because a pointer is marked as restrict
doesn't give the compiler any information at all to say if it overlaps
with another object or not. It has to examine the use of the pointer
expressions inside a block to determine this information, hence the
comparison of the pointers in MemFoo cannot be eliminated as is.


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.

Apr 6 '06 #22

This discussion thread is closed

Replies have been disabled for this discussion.