Trying to understand "restrict"

[Frederick Gotham]

I'm going to be using an acronym a lot in this post:

IINM = If I'm not mistaken

Let's say we've got translation units which are going to be compiled to
object files, and that these object files will be supplied to people to link
with their own projects. Here's a sample function in one of the object files:

void Func(int const *const p)
{
int i = 0;

if(*p) ++i;

if(*p) ++i;

if(*p) ++i;

if(*p) ++i;

/* More code */
}

(Forget for the moment how stupid the function is.)

We can see that "*p" is accessed four times. If I'm not mistaken, the
compiler can optimise this to the following:

void Func(int const *const p)
{
int i = 0;

if(*p) i = 4;
}

Now, "*p" is only accessed once.

IINM, the only condition under which the compiler can't perform this
optimisation is if either:

(1) "p" is a pointer to volatile.

(2) "i" is volatile.

Could someone please confirm that?

Here's our next function:

void Func(int const *const p, int (*const OtherFunc)(void))
{
int i = 0;

if (*p) i += OtherFunc();

if (*p) i += OtherFunc();
}

It is my understanding that, even thought "p" is not a pointer to volatile,
the compiler can NOT optimise this to the following:

void Func(int const *const p, int (*const OtherFunc)(void))
{
int i = 0;

if (*p)
{
i = OtherFunc() + OtherFunc();
}
}

IINM, the second access to "*p" cannot be optimised away because we don't
know if the invocation of "Func" may have altered the data at that address.
Am I right?

If I understand correctly, this is why "restrict" was brought in. If we want
to be able to optimise away the second access of "*p", then we must write the
function as:

void Func(int const *const restrict p, int (*const OtherFunc)(void));

Am I right in thinking that, because the pointer is restrict, the compiler
can know turn that into:

void Func(int const *const restrict p, int (*const OtherFunc)(void))
{
int i = 0;

if (*p)
{
i = OtherFunc() + OtherFunc();
}
}

 

[websnarf]

[...] It is my understanding that, even thought "p" is not a pointer to volatile,
the compiler can NOT optimise this to the following:

void Func(int const *const p, int (*const OtherFunc)(void))
{
int i = 0;

if (*p)
{
i = OtherFunc() + OtherFunc();
}
}

IINM, the second access to "*p" cannot be optimised away because we don't
know if the invocation of "Func" may have altered the data at that address.
Am I right?

Yes of course. C does not have a declaration for "I have no side
effects". A strong enough compiler might *deduce* such a theoretical
attribute, however (and in fact declare it for some functions like
strlen.)

If I understand correctly, this is why "restrict" was brought in.

No. Restrict was brought in to explicitely document a fundamental
weakness of the C language, and allow the compiler to perform some
optimizations that the C compiler could sometime never guaranteed to be
correct unless a no-alias assumption is made.

[...] If we want
to be able to optimise away the second access of "*p", then we must write the
function as:

void Func(int const *const restrict p, int (*const OtherFunc)(void));

Am I right in thinking that, because the pointer is restrict, the compiler
can know turn that into:

void Func(int const *const restrict p, int (*const OtherFunc)(void))
{
int i = 0;

if (*p)
{
i = OtherFunc() + OtherFunc();
}
}

I'm pretty sure that this is wrong. A side effect is not the same as a
restrict declaration. restrict just says that the pointer can be
assumed to point to storage that is distinct from anything else
directly referenced in the same scope. I.e., its meant really mostly
for leaf-node functions that do not make other calls in their inner
loop. It would be horrendously difficult to debug certain scenarios if
they did not limit the definition of restrict to this.

 

[Richard Bos]

void Func(int const *const p, int (*const OtherFunc)(void))
{
int i = 0;

if (*p) i += OtherFunc();

if (*p) i += OtherFunc();
}

It is my understanding that, even thought "p" is not a pointer to volatile,
the compiler can NOT optimise this to the following:

void Func(int const *const p, int (*const OtherFunc)(void))
{
int i = 0;

if (*p)
{
i = OtherFunc() + OtherFunc();
}
}

IINM, the second access to "*p" cannot be optimised away because we don't
know if the invocation of "Func" may have altered the data at that address.
Am I right?
Yes.

If I understand correctly, this is why "restrict" was brought in.

Amongst others. AIUI, array aliasing (more precisely, the optimisations
you can do when you can assume there is no array aliasing) was also a
major reason for it.

If we want to be able to optimise away the second access of "*p", then
we must write the function as:

void Func(int const *const restrict p, int (*const OtherFunc)(void));

Am I right in thinking that, because the pointer is restrict, the compiler
can know turn that into:

void Func(int const *const restrict p, int (*const OtherFunc)(void))
{
int i = 0;

if (*p)
{
i = OtherFunc() + OtherFunc();
}
}

Yes.

Richard