c const

[Duncan_Sands]

Hi Christopher,

The benefits of a const * __restrict come from two different places.
The const part is essentially enforced by the front-end and the
restrict part is used to inform the alias analysis (it becomes a
noalias parameter attribute). The noalias parameter attribute may be
of use to you eventually, but full noalias implementation isn't yet
complete. Specifically the case where a function with noalias
parameter attributes is inlined does not currently preserve the
noalias information.

> Here's a thread about it:
>
> http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-March/thread.html#8291

You should also take a look at PR 1373, as that is where progress is
being tracked. 1373 – Some method to represent alias information in LLVM would be useful

> I don't think anything has been implemented.

Per the discussion and PR there has been work done to implement the
'noalias' parameter attribute in LLVM, and currently BasicAA will use
this attribute to inform alias queries that are made. There has also
been work to map __restrict C/C++ pointer and reference parameters
onto the noalias parameter attribute. There is still much work to be
done to fully implement noalias in LLVM, notably the intrinsic and
updates to tolerate/use it, as well as to fully support all uses of
the __restrict qualifier in the C/C++ front end.

it looks like noalias might be very useful for Ada: for certain types,
such as array types, the language standard explicitly allows the compiler
to pretend that a formal argument of that type is passed by-copy (= by-value)
for alias analysis purposes, while actually passing it by-reference (= via a pointer).
I'm not sure, but based on Chris's suggested implementation
http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-March/008323.html
it seems that this may map exactly to "noalias". There is a subtlety
though: the compiler may pretend that a copy was passed in, but it must
correspond to a copy made at the moment of the function call, not later.

In Chris's description
" The semantics of 'noalias' are that they "define a new object" "
it is not specified *when* the new object gets its value; Ada requires
the pretend "new object" to act as if it got its value at the start of
the function body, not later, as if a copy of the real object was made
at that point.

For example, suppose that there are two formal array parameters A and B,
and in the function body A is read then later B is written:
  read from A
...
  write to B
In general it is wrong to re-order the read after the write, since
then the read might get a new value written via B, which would be
inconsistent with A being a copy made at the start of the function
call (instead it would correspond to A being a copy made part way
through the execution of the body, after the write to B). On the
other hand, if first B is written and later A is read:
  write to B
...
  read from A
then it is legal to re-order the read before the write.

I very much hope that noalias semantics are or can be made to be
consistent with this scheme: it represents an important optimization
for Ada, since the language standard permits it in many significant
cases.

Ciao,

Duncan.

[Christopher_Lamb]

Hi Christopher,

The benefits of a const * __restrict come from two different places.
The const part is essentially enforced by the front-end and the
restrict part is used to inform the alias analysis (it becomes a
noalias parameter attribute). The noalias parameter attribute may be
of use to you eventually, but full noalias implementation isn’t yet
complete. Specifically the case where a function with noalias
parameter attributes is inlined does not currently preserve the
noalias information.

Here’s a thread about it:

http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-March/thread.html#8291

You should also take a look at PR 1373, as that is where progress is
being tracked. http://llvm.org/bugs/show_bug.cgi?id=1373

I don’t think anything has been implemented.

Per the discussion and PR there has been work done to implement the
‘noalias’ parameter attribute in LLVM, and currently BasicAA will use
this attribute to inform alias queries that are made. There has also
been work to map __restrict C/C++ pointer and reference parameters
onto the noalias parameter attribute. There is still much work to be
done to fully implement noalias in LLVM, notably the intrinsic and
updates to tolerate/use it, as well as to fully support all uses of
the __restrict qualifier in the C/C++ front end.

it looks like noalias might be very useful for Ada: for certain types,
such as array types, the language standard explicitly allows the compiler
to pretend that a formal argument of that type is passed by-copy (= by-value)
for alias analysis purposes, while actually passing it by-reference (= via a pointer).
I’m not sure, but based on Chris’s suggested implementation
http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-March/008323.html
it seems that this may map exactly to “noalias”. There is a subtlety
though: the compiler may pretend that a copy was passed in, but it must
correspond to a copy made at the moment of the function call, not later.

In Chris’s description
" The semantics of ‘noalias’ are that they “define a new object” "
it is not specified when the new object gets its value; Ada requires
the pretend “new object” to act as if it got its value at the start of
the function body, not later, as if a copy of the real object was made
at that point.

I can’t see how the semantics could be anything other than for the “new object” that the noalias argument points to could be created at any other time than the beginning of the function. By definition a noalias argument cannot point to the same object as any other argument, or else C/C++ restrict semantics wouldn’t map onto it either.

For example, suppose that there are two formal array parameters A and B,
and in the function body A is read then later B is written:
read from A
…
write to B
In general it is wrong to re-order the read after the write, since
then the read might get a new value written via B, which would be
inconsistent with A being a copy made at the start of the function
call (instead it would correspond to A being a copy made part way
through the execution of the body, after the write to B). On the
other hand, if first B is written and later A is read:
write to B
…
read from A
then it is legal to re-order the read before the write.

In both of these cases it would be wrong to reorder the memory operations unless alias analysis concluded that they did not alias each other. If either of A or B (or both) are marked as noalias parameters then the alias analysis will return that A does not alias B, allowing either of the transforms that you mention. This applies to derived pointers to any two distinct objects where one is a noalias parameter as well (i.e. via GEP).

I very much hope that noalias semantics are or can be made to be
consistent with this scheme: it represents an important optimization
for Ada, since the language standard permits it in many significant
cases.

It seems that you may be in luck.

[Duncan_Sands]

Hi Christopher,

> it looks like noalias might be very useful for Ada: for certain types,
> such as array types, the language standard explicitly allows the
> compiler
> to pretend that a formal argument of that type is passed by-copy (=
> by-value)
> for alias analysis purposes, while actually passing it by-reference
> (= via a pointer).
> I'm not sure, but based on Chris's suggested implementation
> http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-March/008323.html
> it seems that this may map exactly to "noalias". There is a subtlety
> though: the compiler may pretend that a copy was passed in, but it
> must
> correspond to a copy made at the moment of the function call, not
> later.
>
> In Chris's description
> " The semantics of 'noalias' are that they "define a new object" "
> it is not specified *when* the new object gets its value; Ada requires
> the pretend "new object" to act as if it got its value at the start of
> the function body, not later, as if a copy of the real object was made
> at that point.

I can't see how the semantics could be anything other than for the
"new object" that the noalias argument points to could be created at
any other time than the beginning of the function. By definition a
noalias argument cannot point to the same object as any other
argument, or else C/C++ restrict semantics wouldn't map onto it either.

no! In the Ada case, the arguments can point to the same object (I think
this is the same for Fortran too - not sure). For example, if the same
array pointer is passed for two arguments, the compiler is allowed to pretend
that the two arguments point to different objects as long as it only performs
transforms that would be correct if pointers to two distinct copies of the array
had been passed, copies made at the point of the call. Of course no such copies
are made, and the same pointer is actually passed for both arguments. Programmers
who are not aware of this will of course be surprised at the results, but will
be shot down by the language lawyers

Also, I don't understand your remark about C/C++ restrict semantics: I thought
noalias meant that you can *pretend* that two noalias arguments point to
different objects; and if you pass the same object then you get what you
deserve, and C/C++ doesn't define what happens in this case. Since C/C++
doesn't define this case, we can define it to mean what we like. I would like
to define the set of legal transformations to be as described above, when
aliased pointers are passed.

Further, in the Ada case you are allowed to suppose that the parameter doesn't
alias anything, including global variables and all other parameters, even if it
fact it does. Subject of course to the restriction that the transforms should
result in a program that would be correct if pointers to copies of each object
pointed to by a noalias pointer had been passed in.

> For example, suppose that there are two formal array parameters A
> and B,
> and in the function body A is read then later B is written:
> read from A
> ...
> write to B
> In general it is wrong to re-order the read after the write, since
> then the read might get a new value written via B, which would be
> inconsistent with A being a copy made at the start of the function
> call (instead it would correspond to A being a copy made part way
> through the execution of the body, after the write to B). On the
> other hand, if first B is written and later A is read:
> write to B
> ...
> read from A
> then it is legal to re-order the read before the write.

In both of these cases it would be wrong to reorder the memory
operations unless alias analysis concluded that they did not alias
each other. If either of A or B (or both) are marked as noalias
parameters then the alias analysis will return that A does not alias
B, allowing either of the transforms that you mention. This applies
to derived pointers to any two distinct objects where one is a
noalias parameter as well (i.e. via GEP).

This is bad, and means that noalias is useless for Ada. The first
transformation is not allowed, because it is not consistent with a
pointer to a copy being passed in. Is it clear why it is inconsistent?
Suppose A and B point to the same object, an array of one element.
Suppose the array element equals 0 at the point of the call. If I
do
x = A[0]
B[0] = 1
in Ada, then the value of x must be 0 not 1: if copies C, D of the array
had been made at the point of the call, and C and D had been passed in
instead of A and B, then x would be equal to 0 because the assignment
D[0]=1 won't change the value of C[0]. Thus the "as-if-copies-had-been-passed"
rule means that x must equal 0. If you switch the order
B[0] = 1
x = A[0]
then x would equal 1 not 0, which would not be possible if copies had
been passed. Thus this transform is illegal in Ada, because it is
inconsistent with what would happen if pointers to copies had been
passed in.

[Note that in Ada you pass arrays not pointers to arrays, but they will
usually be passed "by-reference" and end up being passed as pointers in
LLVM, which is why I talked about pointers to arrays above.]

> I very much hope that noalias semantics are or can be made to be
> consistent with this scheme: it represents an important optimization
> for Ada, since the language standard permits it in many significant
> cases.

It seems that you may be in luck.

No, it seems I am out of luck unless the definition of noalias is modified.

Ciao,

Duncan.

[Christopher_Lamb]

Please excuse this atrocious sentence. It’s completely misleading (I don’t drink coffee, but maybe I should start?)

It should read: I can’t see how the semantics could be anything but for the “new object” to be created at the beginning of the function.

I merged the wrong parts of two sentences in my earlier email. Sorry for the grief!

[Christopher_Lamb]

Hi Christopher,

In C/C++ a restrict pointer is also assumed not to alias any other
parameters, global values or local value. However the compiler must
not assume that pointers “based on” a restrict pointer do not alias.

does “based on” mean something like: copies of the pointer made in the
function body?

To be precise (brackets mine):

In what follows, a pointer expression E is said to be based on object P [a pointer] if (at some
sequence point in the execution of B [the enclosing block] prior to the evaluation of E) modifying P to point to
a copy of the array object into which it formerly pointed would change the value of E.
Note that ‘‘based’’ is defined only for expressions with pointer types.

This is from http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf Sec 6.7.3.1 para 3

Your example strikes me as contradictory to your description of Ada
aliasing rules above. If A and B were in fact copies of an object
then in your first example x would always be 0, no matter which order
the reads and writes are performed. Thus if permuting those memory
operations is safe when copies are passed then that same transform
is, by your definition, allowed when the same array is passed as both
parameters by reference.

I can’t reconcile your statement that in Ada array parameters can be
assumed to not alias, but that that the compiler must be careful to
limit the transforms it applies in the case that they do alias.

Is there a reference that you can point to in the Ada spec that
describes this concretely?

Sure, check out
http://www.adaic.com/standards/05aarm/html/AA-6-2.html
Some types, like array types, are neither by-copy types nor by-reference
types. The candidates I have in mind for noalias are formal parameters
of such a type. The parameter passing mechanism used for the parameter
is then not specified (6.2.11). As explained in 6.2.12, if you write
to the passed object via some other parameter or a global variable,
then read via this parameter, it is undefined as to whether you read
the new value or some old value (or raise an exception). The rest of
section 6.2 discusses this rule, see especially 6.2.12.j.

I’ll take a look as time permits.

[Duncan_Sands]

Hi Christopher,

>> In C/C++ a restrict pointer is also assumed not to alias any other
>> parameters, global values or local value. However the compiler must
>> not assume that pointers "based on" a restrict pointer do not alias.
>
> does "based on" mean something like: copies of the pointer made in the
> function body?

To be precise (brackets mine):

In what follows, a pointer expression E is said to be based on object
P [a pointer] if (at some
sequence point in the execution of B [the enclosing block] prior to
the evaluation of E) modifying P to point to
a copy of the array object into which it formerly pointed would
change the value of E.
Note that ‘‘based’’ is defined only for expressions with pointer types.

This is from Index of /jtc1/sc22/wg14/www/docs
n1124.pdf Sec 6.7.3.1 para 3

suppose A and B are array pointers, and are in fact equal. Consider
the code sequences

(i)
x = A[0] (a)
B[0] = 1 (b)

and

(ii)
B[0] = 1 (b)
x = A[0] (a)

If I understand right, (i)(b) is not based on A, either because it
has no value (not sure what "the value of E" means) or because changing
A to point to a copy would make no difference because (i)(a) is only a
read. Also (i)(a) is not based on B because this is the first instruction.
On the other hand (ii)(a) is based on B because the value of x
is 1, but would be something else if B was changed to point to a copy.

Does this mean that if B is a restricted pointer, then the lines can be
swapped in (i). That if A is a restricted pointer then the lines can be
swapped in (i) and (ii)?

This sounds very similar to the Ada setup, though somehow "dual" to it.

Ciao,

Duncan.

[Christopher_Lamb]

If A and B are function arguments then there is no “based on” relationship between pointer expressions A+0 and B+0. This is because changing one of the pointers, A for example, to point to a copy of the object it points to would change the value of the pointer expression A+0, but not the expression B+0.

This means that if either A or B is a restrict pointer then the expressions in both (i) and (ii) may be executed in any order.

This also means that if the function were called with A == B and either A or B is defined as restrict then the result would be undefined behavior.

[Duncan_Sands]

Hi Christopher,

If A and B are function arguments then there is no "based on"
relationship between pointer expressions A+0 and B+0. This is because
changing one of the pointers, A for example, to point to a copy of
the object it points to would change the value of the pointer
expression A+0, but not the expression B+0.

I was assuming that *(A+0) and *(B+0) are pointer expressions. Is
that not the case?

Thanks,

Duncan.

[Christopher_Lamb]

I believe the expressions you mention are indeed not pointer expressions as they evaluate to a value of the pointed-to type rather than a pointer to the type. Only pointers may be “based on” other pointers from my reading of the spec.

[Daniel_Berlin1]

Christopher, just to point something out.

Earlier you said that restrict says something about the relationship
of a pointer to non-restricted pointers. This is not true except for
one small case.
Restricted pointers in general only tell you things about a
relationship to other restricted pointers.

IE the following is perfectly legal:

int foo(int *a, restrict int *b)
{
int *c = a;

a = b;
*a = 90;
a = c;
*a = 90;
}

The following is not:

int foo(int *a, restrict int *b, restrict int *c)
{
a = b;
*a = 90;
a = c;
*a = 90;
}

6.7.3.1 only says you can't change a pointer to point to *another
restricted pointer*.

"If P is assigned the value of a pointer expression that is based on
*another restricted pointer object P2*, associated with block B2, then
either the execution of B2 shall begin before
the execution of B, or the execution of B2 shall end prior to the
assignment. If these
requirements are not met, then the behavior is undefined.
"

It also says that the behavior is only undefined if the value is modified.

This means loads from restricted pointers and non-restricted pointers
can alias, as can loads from restricted pointers and other restricted
pointers.

They even given an example of this, and declare it legal.

Restrict is sadly not that useful in the way the standard actually specfiies.

[Christopher_Lamb]

Hi Daniel,

Hi Christopher,

If A and B are function arguments then there is no "based on"
relationship between pointer expressions A+0 and B+0. This is because
changing one of the pointers, A for example, to point to a copy of
the object it points to would change the value of the pointer
expression A+0, but not the expression B+0.

I was assuming that *(A+0) and *(B+0) are pointer expressions. Is
that not the case?
I believe the expressions you mention are indeed not pointer expressions as
they evaluate to a value of the pointed-to type rather than a pointer to the
type. Only pointers may be "based on" other pointers from my reading of the
spec.

Christopher, just to point something out.

Earlier you said that restrict says something about the relationship
of a pointer to non-restricted pointers. This is not true except for
one small case.
Restricted pointers in general only tell you things about a
relationship to other restricted pointers.

I'm not sure which previous statement was unclear, but I can believe I was a bit loose with the details on this point. My understanding is that as long as the analysis can determine the "based on" relationship between two pointers, then restrict does say something about those two pointers, even if one is not restrict.

IE the following is perfectly legal:

int foo(int *a, restrict int *b)
{
int *c = a;

a = b; (1)
*a = 90;
a = c; (2)
*a = 90;
}

Here the alias analysis would be incorrect if it determined that the value of 'a' at point (2) was "based on" 'b'. This allows restrict to play a role in allowing the query alias(a(2), b) == No.

Here's an example where restrict would have a harder time playing a role:

int foo(int *a, restrict int *b)
{
int *c = bar(a, b);

a = b; (1)
*a = 90;
a = c; (2)
*a = 90;
}

Here 'a' at point (2) may be "based on" 'b', depending on the implementation of bar(). Unless the compiler can determine that the second parameter of bar() has no affect on its return value, then the alias analysis will have to return alias(a(2), b) == May.

The following is not:

int foo(int *a, restrict int *b, restrict int *c)
{
a = b;
*a = 90;
a = c;
*a = 90;
}

6.7.3.1 only says you can't change a pointer to point to *another
restricted pointer*.

"If P is assigned the value of a pointer expression that is based on
*another restricted pointer object P2*, associated with block B2, then
either the execution of B2 shall begin before
the execution of B, or the execution of B2 shall end prior to the
assignment. If these
requirements are not met, then the behavior is undeÞned.
"

I don't agree. The spec defines P as "designating an object P as a restrict-qualified pointer". The preceding example casts away the restrict-ness of the pointers, but is perfectly legal by my reading of the spec given that P in your example is not a restrict-qualified pointer and so the clause you cite is not applicable.

If the function were foo(int * restrict a, restrict int *b, restrict int *c), then I believe that the the behavior would be undefined because of the clause you cite.

It also says that the behavior is only undefined if the value is modified.

This means loads from restricted pointers and non-restricted pointers
can alias, as can loads from restricted pointers and other restricted
pointers.

They even given an example of this, and declare it legal.

Indeed, if you are referring to Example 3 in 6.7.3.1 this does not imply that the compiler must determine that these pointers may or must alias. My reading of this example is that it explains that even though the compiler can assume that two restrict pointers, or even a restrict and a non-restrict pointer, do not alias, when those pointers point to the same object it will not lead to undefined behavior if the two pointers are not used to modify the objects they point to.

Their example:

void h(int n, int * restrict p, int * restrict q, int * restrict r)
{
   int i;
   for (i = 0; i < n; i++)
     p[i] = q[i] + r[i];
}

If a and b are disjoint, then h(100, a, b, b) has defined behavior. This is not a requirement of the spec, but an example of defined behavior that emerges due to the requirements set out earlier in the section.

By my reading of the spec, the following modified example would also have defined behavior under the same conditions as the previous one.

void h'(int n, int * restrict p, int * restrict q, int * r)
{
   int i;
   for (i = 0; i < n; i++)
     p[i] = q[i] + r[i];
}

As neither p nor q is "based on" r, the alias analysis is free to determine that they do not alias r given the restrict nature of q and q. And neither q nor r is used to modify the object it points to.

Restrict is sadly not that useful in the way the standard actually specfiies.

In practice I have actually found the restrict qualifier to be critical to generating efficient code in certain circumstances. These cases were specialized compute codes, however, not typically user apps.

Cheers

[Daniel_Berlin1]

Hi Daniel,

>>
>>
>>
>> Hi Christopher,
>>
>>
>> If A and B are function arguments then there is no "based on"
>> relationship between pointer expressions A+0 and B+0. This is because
>> changing one of the pointers, A for example, to point to a copy of
>> the object it points to would change the value of the pointer
>> expression A+0, but not the expression B+0.
>>
>> I was assuming that *(A+0) and *(B+0) are pointer expressions. Is
>> that not the case?
>> I believe the expressions you mention are indeed not pointer
>> expressions as
>> they evaluate to a value of the pointed-to type rather than a
>> pointer to the
>> type. Only pointers may be "based on" other pointers from my
>> reading of the
>> spec.
>
> Christopher, just to point something out.
>
> Earlier you said that restrict says something about the relationship
> of a pointer to non-restricted pointers. This is not true except for
> one small case.
> Restricted pointers in general only tell you things about a
> relationship to other restricted pointers.

I'm not sure which previous statement was unclear, but I can believe
I was a bit loose with the details on this point. My understanding is
that as long as the analysis can determine the "based on"
relationship between two pointers, then restrict does say something
about those two pointers, even if one is not restrict.

> IE the following is perfectly legal:
>
> int foo(int *a, restrict int *b)
> {
> int *c = a;
>
> a = b; (1)
> *a = 90;
> a = c; (2)
> *a = 90;
> }

Here the alias analysis would be incorrect if it determined that the
value of 'a' at point (2) was "based on" 'b'. This allows restrict to
play a role in allowing the query alias(a(2), b) == No.

Any alias anlysis performed on SSA form will already get that (a(2),
b) = No without restrict.

Restrict answers no query you can't already answer here.

Here's an example where restrict would have a harder time playing a
role:

int foo(int *a, restrict int *b)
{
int *c = bar(a, b);

a = b; (1)
*a = 90;
a = c; (2)
*a = 90;
}

Here 'a' at point (2) may be "based on" 'b', depending on the
implementation of bar(). Unless the compiler can determine that the
second parameter of bar() has no affect on its return value, then the
alias analysis will have to return alias(a(2), b) == May.

Again, SSA form alias analysis takes care of this without restrict

Indeed, if you are referring to Example 3 in 6.7.3.1 this does not
imply that the compiler must determine that these pointers may or
must alias.
My reading of this example is that it explains that even
though the compiler can assume that two restrict pointers, or even a
restrict and a non-restrict pointer, do not alias, when those
pointers point to the same object it will not lead to undefined
behavior if the two pointers are not used to modify the objects they
point to.

It says the example "illustrate how an unmodified object can be aliased
through two restricted pointers."

You cannot assume they do not alias simply because they are
restricted, as you claim, as the object they point to is not modified.
As a result, they must be assumed to alias unless you can prove
otherwise, and again, restrict does nothing.

You also say, following your example.
"
As neither p nor q is "based on" r, the alias analysis is free to
determine that they do not alias r given the restrict nature of q and
q. "

Where do you find support for this? Nowhere in the function is an
pointer based on q modified, so why do you believe that you can
suddenly determine that q and r do not alias.

You can only assume that p and q do not alias, and p and r do not
alias, based on the restrict clause, as otherwise, it would invoke
undefined behavior.

I see no undefined behavior from q and r aliasing.

> Restrict is sadly not that useful in the way the standard actually
> specfiies.

In practice I have actually found the restrict qualifier to be
critical to generating efficient code in certain circumstances. These
cases were specialized compute codes, however, not typically user apps.

I will bet you a large amount of money the compiler you are using and
seeing these performance gains is not implementing restrict properly.

In particular, they use it to say things about two loads when they shouldn't.

--Dan