Add language to clarify shared/non-shared alias relationships

[Former user]

Originally reported on Google Code with ID 36

This issue is responsive to the item 47 in the open issues list.

47. Aliasing guarantees?  Meaning of the restrict keyword when applied to a pointer-to-shared?

It is unclear from the brief problem statement above the detailed nature of the of
the problem with respect to restrict qualified pointer target types. Therefore no particular
proposal is expressed in the problem description.  Further comments added to this issue
are invited that amplify the problem description and that propose UPC specification
changes.

Reported by gary.funck on 2012-05-22 05:41:37

[Former user]

``` As Gary indicated, there is not much "meat" to the problem statement. So, I'll take a shot at throwing out my random thoughts in the hope of finding something we want/need to put in the spec:

If we consider the restrict keyword in C99, the guarantee is that given two or more pointers with the "restrict" qualifier they will each address (at least "dynamically") distinct (non-overlapping) objects and they cannot address an "extern" qualified object. The gory details are found in the original C proposal here: http://www.lysator.liu.se/c/restrict.html

In the "linear" address space of C that all makes sense. In UPC however, one can "reshape" a pointer by cast: for instance taking an indefinite pointer-to-shared (with it's "regular C" layout) and casting it to a cyclic layout. So, does that change what "restrict" should mean? I would hope it does not.

My experience with using "restrict" is limited to function parameters, though the C99 spec allows wider used. Based on the "gut feeling" that comes along with "restrict" in this context I expect that as an implementer I can freely reorder accesses made via the two (or more) distinct pointers knowing that no changes to the program behavior can result.

So, do we want to clarify that "restrict" still means the same thing?

Does this interact or conflict with the "strict" modifier? My feeling here (with only brief thought) is that the "strict" qualifier PROHIBITS exactly the re-ordering that "restrict" is meant to enable. So, I would think these two qualifiers should NOT be permitted to be applied to the same pointer.

What about the "relaxed" qualifier? The "restrict" qualifier applied to a relaxed pointer would, I believe, allow one to legally assume that the "same address" rule won't apply to shared accesses via two relaxed/restricted pointers. So, there does seem to be some "performance utility" to "relaxed" in combination with "shared", by allowing optimization that we otherwise cannot perform even in the relaxed model. ```

Reported by `[e-mail]` on 2012-06-01 07:06:49

[Former user]

``` Oops. The very last sentence of my previous comment read:

So, there does seem to be some "performance utility" to "relaxed" in combination with "shared", by allowing optimization that we otherwise cannot perform even in the relaxed model.

The first instance of "relaxed" should have said "restrict":

So, there does seem to be some "performance utility" to "restrict" in combination with "shared", by allowing optimization that we otherwise cannot perform even in the relaxed model.

```

Reported by `[e-mail]` on 2012-06-01 07:17:02

[Former user]

``` The C99 semantics of restrict revolve around the objects accessed via dereference of the qualified pointer, so the fact that you traversed a wide pointer to reach those elements and the exact blocking factor in the type of that pointer should be completely irrelevant. In my opinion restrict already makes perfect sense on a pointer-to-shared and no further clarification is required.

I agree that the presence of strict on a restrict-qualified pointer probably negates any useful access optimizations, but the language concept being expressed by the annotation is still fully meaningful, so I see no reason to prohibit it.

I invite further examples where the combination is unclear, otherwise moving to close with WontFix. ```

Reported by `danbonachea` on 2012-06-15 15:37:37

[Former user]

``` I originally added this issue to the list. I perhaps should not have mentioned restrict and taken us on that detour. restrict is related to aliasing, but not to my main point. Let me start with a few examples:

shared int* p; shared int a[THREADS];

It is perfectly valid to point p at any part of array a. A reference through p, therefore, may modify an element of array a. So far not surprising.

Now consider:

shared int* p; int b[100];

It is not legal in UPC to cast a pointer-to-local to a pointer-to-shared, so one cannot write p = (shared int*)&b[0], for example. A compiler safely can assume that references through p cannot modify an element of array b. I'm not sure how many compilers make use of this fact, but it exists.

Now here's where it gets messy...

Arguments of this function may alias since q1 could equal (int*)p:

void foo1( shared int* p, int* q1 );

Arguments of this function may not alias(!)

void foo2( shared int* p, int q2[] );

because C99 draws a distinction between int* and int[] in 6.7.5.2.8 and, as established above, UPC makes it illegal to point a pointer-to-shared at non-shared-qualified data. So in foo2, p can never point into the q2 array. Thus, an implementation can assume that p and q2 do not alias...or can it?

You will find that C compilers are perfectly okay with the following call:

void test( int q[] ); int* x; ... test( x );

Therefore, it is possible to cast a pointer-to-shared to a pointer-to-local, pass that pointer-to-local to a function with an array parameter, and have a UPC compiler incorrectly assume that the non-shared array parameter cannot alias with any shared data. You might argue that one needs this declaration instead:

void foo2( shared int* restrict p, int q2[restrict] );

But I'm arguing that code explicitly states a no-aliasing relationship that appears to be already implied by C99 and UPC 1.2, when in fact it is not true.

I propose that we add some language to UPC 1.2 6.4.3.1 to say that it does not imply this particular no-aliasing relationship. Or perhaps near UPC 1.2 6.5.1.1 near footnote 14 (which also talks about aliasing), ```

Reported by `johnson.troy.a` on 2012-06-15 19:43:47 - Labels added: Milestone-Spec-1.3

[Former user]

``` Update title to better reflect the issue that I wanted to raise. ```

Reported by `johnson.troy.a` on 2012-06-15 19:57:24

[Former user]

``` Re-assign Troy as owner. ```

Reported by `gary.funck` on 2012-06-29 19:28:28

[Former user]

Reported by `gary.funck` on 2012-07-03 15:10:26 - Labels added: Type-Clarification - Labels removed: Type-Defect

[Former user]

``` Set default Consensus to "Low". ```

Reported by `gary.funck` on 2012-08-19 23:26:19 - Labels added: Consensus-Low

[Former user]

``` For completeness, here is the text Troy quoted from 6.7.5.2-8:

"EXAMPLE 2 Note the distinction between the declarations extern int *x; extern int y[]; The first declares x to be a pointer to int; the second declares y to be an array of int of unspecified size (an incomplete type), the storage for which is defined elsewhere."

Note this designates the type (int y[]) as an INCOMPLETE type.

However, it appears there is some subtle "adjustment" which automatically takes place when one of these incomplete array types appears as a formal parameter to a function.

6.5.2.2 constraint and semantics on function calling (emphasis added):

"Each argument shall have a type such that its value may be assigned to an object with the unqualified version of the type of its corresponding parameter. ... In preparing for the call to a function, the arguments are evaluated, and each parameter is assigned the value of the corresponding argument[78] [78]...A parameter declared to have ARRAY or function type is ADJUSTED TO HAVE A POINTER TYPE as described in 6.9.1."

6.9.1-7: Function definitions:

"the type of EACH PARAMETER IS ADJUSTED as described in 6.7.5.3 for a parameter type list; the resulting type shall be an OBJECT type."

6.7.5.3: Function declarators:

"After adjustment, the parameters in a parameter type list in a function declarator that is part of a definition of that function SHALL NOT HAVE INCOMPLETE TYPE."

My interpretation of these C99 passages is that in a declaration of the form:

void foo2( shared int* p, int q2[] );

the second parameter is automatically "adjusted" to instead be:

void foo2( shared int* p, int *q2 );

Troy's basis for comment 4 seems to be that the first form is somehow different from the second and implies some sort of freedom from aliasing, but the C99 verbiage quoted above seems to indicate they are in fact equivalent, and moreover the first is automatically "adjusted" (aka rewritten) to be the second. Furthermore, in the absence of restrict there is nothing to prohibit aliasing of these incomplete array formal arguments in pure C, eg:

void foo(int x[], int y[], int *q) { } int main() { int a[7]; foo(a,a,a); /* permitted */ return 0; }

This code is fully legal (or at least `gcc -pedantic` accepts it and I can't find anything in C99 to prohibit it) and all three arguments of foo are aliased.

So I think this means that as a general rule incomplete array type formal arguments are equivalent to a pointer-to-local, and (in the absence of restrict) can always be aliased with other pointer arguments. This is an (unstated) aliasing property of pure C99 which exists completely independently of any UPC extensions. C99 does not list all the ways in which pointers can be aliased, so it would seem odd for us to start doing that. Perhaps this is something we can add to the Rationale doc under "Advice to Implementers"?

I still move to close with NoChange. ```

Reported by `danbonachea` on 2012-09-26 23:15:33

[Former user]

We discussed this issue at the 1/17 telecon and did not reach a consensus.

We agreed to table the issue for now, and perhaps reconsider it at a later date with
a concrete proposal from Troy.

Reported by danbonachea on 2013-01-17 19:49:54 - Labels added: Milestone-Spec-1.4 - Labels removed: Milestone-Spec-1.3

[Former user]

Proposed language to add to UPC Section 6.4.3 "Cast and assignment expressions" as new
paragraphs 8 and 9:

8   A pointer-to-shared cannot alias with an array that is not shared qualified; however
a pointer-to-shared can alias with a pointer-to-local, even if that pointer-to-local
arises via type adjustment of an array parameter that is not shared qualified.

9   EXAMPLE 2

    /* ISO/IEC00 Section 6.7.5.3 Paragraph 7 adjusts q to int*  */
    void foo( shared int* p, int q[] ); /* p and q may alias */

    static shared int x[10*THREADS];
    int* y = (int*)&x[MYTHREAD];

    foo( &x[MYTHREAD], y );

Reported by johnson.troy.a on 2013-01-22 21:26:38

[Former user]

I think Troy's text would be a great addition to the "Advice to Implementers" document:
http://code.google.com/p/upc-specification/wiki/UPCSpecCompanion

However I'm still opposed to this going into the language spec for several reasons:

1. It addresses a purely implementation issue - an aliasing property which is already
derivable from a close reading of C99/UPC semantics, and is completely irrelevant to
users. Realistically the only people who may ever need this information are probably
all on this mailing list.

2. There is nothing remotely like this in C99. It defines how objects may legally be
accessed (6.5-7 and 6.7.3.1), and leaves it up to implementers to infer what optimizations
are possible that won't affect the observable behavior of the program in a way that
differs from execution on the abstract machine. In fact C99 5.1.2.3 even states: "The
semantic descriptions in this International Standard describe the behavior of an abstract
machine in which issues of optimization are irrelevant."

3. It begs the question of what are the other aliasing properties of the language that
an implementer needs to write a correct alias analysis.

4. The proposed language makes an overly broad statement: "a pointer-to-shared can
alias with a pointer-to-local". This could be misread to mean that any two such pointers
may be aliased. This property is true in the very narrow case shown in proposed example,
but there are in fact many more examples where two randomly-chosen pointers in the
program may NOT be aliased. The most obvious case is simply adding restrict to the
arguments in the example. Other common cases include when the referent types are incompatible,
or when analysis of surrounding code can prove the pointers reference two objects known
to be distinct.

Reported by danbonachea on 2013-01-22 23:26:37

[Former user]

We need more people to choose a side on this issue...

1) The added language is relevant and helpful to programmers working within a C-based
language targeting HPC because it helps to know when they need to worry about assisting
the compiler by adding "restrict."  These paragraphs explicitly call out a situation
where it may appear that aliasing is prohibited but is in fact allowed.  "restrict"
is necessary (for greatest performance) if the programmer knows that they aren't generating
aliases.

2) There is no constraint on the UPC spec that it must include only statements that
sound like things in C99.  We can say whatever we want (and could even contradict C99),
it's just that the spec falls back on C99 for anything that we don't mention.

3) I'm not suggesting that we include an in depth discussion of all possible C99 aliases
among pointers-to-local or UPC aliases among pointers-to-shared.  This section in the
UPC spec discusses casts between pointers-to-shared and pointers-to-local, and because
UPC permits that (in one direction), it opens up the possibility of aliases between
those different kinds of pointers.  This section is the place to clarify any unusual
side effect of that consequence.

4) I chose "can" instead of "may" to avoid saying "may alias" which has a specific
pointer-aliasing definition already.  We can work on the wording.  The point is that
without this clarification, a programmer may think that the compiler can assume that
no alias exists and that they don't need to bother with "restrict," but that's not
true.  "restrict" may be beneficial here.

Reported by johnson.troy.a on 2013-01-23 00:12:37

[Former user]

> We need more people to choose a side on this issue...

I agree it may be helpful for more people to state their opinion on this one.

> it helps to know when they need to worry about assisting the compiler by adding "restrict."

> These paragraphs explicitly call out a situation where it may appear that aliasing
is prohibited 
> but is in fact allowed.  "restrict" is necessary (for greatest performance) if the
programmer 
> knows that they aren't generating aliases.
> ... they don't need to bother with "restrict," but that's not true.  "restrict" may
be beneficial here.

I don't buy this argument. You're basically saying the average UPC programmer believes
he can replicate the compiler's alias analysis in his head and wants to infer the minimal
set of restrict keywords he needs to get the optimizations he wants to be applied.
Excluding programmers who helped write the compiler, or some very detailed user feedback
from the optimizer, that doesn't seem like a realistic way to optimize. A more principled
and portable approach for a performance-conscious author to optimize their UPC program
is to insert a restrict annotation at *every* function declaration used by inner loops
where he knows the pointer arguments will never be aliased. Ie express the non-aliased
property wherever the program design ensures it, and let the optimizer sort it out.
If the analysis in one compiler is already smart enough to prove lack of aliasing in
some of those cases, the restrict keyword makes no difference but hurts nothing. A
compiler with a less aggressive analysis may benefit more from the programmer's annotation.

> There is no constraint on the UPC spec that it must include only statements that
sound like things in C99.

Agreed, but C99 is also an excellent model for us, since it's very closely related
and has endured decades of scrutiny and tweaking from many more users, implementers
and language writers than our project. Also, if we're still considering the possibility
of the UPC spec somehow/someday being promoted to a more formal part of the C language,
we should try not to gratuitously diverge from the form and conventions of the C spec
(not to be confused with language features).

Also, as I argued in comment 9, the aliasing scenario you propose to specify already
exists in pure C99:

   void foo(int x[], int y[], int *q) { } 

All three arguments to this pure C99 function may legally be aliased, although a casual
C programmer might not immediately realize that. Regardless, the C spec doesn't explicitly
state that or any other aliasing property - it's just an inferred property of the language
semantics.

Reported by danbonachea on 2013-01-23 03:18:29

[Former user]

I think Troy has valid points that would be valuable to express *somewhere* writing.
However, I agree with Dan that given C99 as our "basis" these clarifications are not
appropriate for inclusion in the normative portion of the UPC spec.

Reported by [e-mail] on 2013-01-23 06:57:00

[Former user]

I understand that this information could go into the UPCSpecCompanion document that
Dan linked in Comment #12, but the proposed text in Comment #11 is brief, fits with
an existing section of the spec, and is similar to an existing aliasing clarification
in Footnote 14.  Is there some distinction between the proposed text and Footnote 14
that would make you want to keep Footnote 14 in the spec but relegate the proposed
text to the UPCSpecCompanion, or would you also want to remove Footnote 14 from the
spec and put it into the UPCSpecCompanion?

Reported by johnson.troy.a on 2013-01-23 16:50:11

[Former user]

Troy,

I assume you are talking about the following from the 1.2 spec:

14  This is a powerful statement which allows, for example, that in an implementation
sizeof(shared int *) may differ from sizeof (shared [10] int *) and if T and S
are pointer-to-shared types with different block sizes, then T* and S* cannot be aliases.

If so, then I would answer "YES" to your question "would you also want to remove Footnote
14 from the spec and put it into the UPCSpecCompanion?".

If there were no Companion or other document in which to put this kind of elaboration,
then I'd reluctantly accept them in the Spec itself.  I look at the Spec as providing
the equivalent of "Axioms" and both Footnote 14 and your proposed addition are more
like "Theorems" that one can derive from the axioms.  The analogy is far from perfect,
but felt like a good way to express my view compactly.

-Paul

Reported by [e-mail] on 2013-01-23 21:35:36

[Former user]

Thanks Paul.  As long as both that footnote and my proposed language are in the same
document, I can accept putting them both into either the spec or the companion document.
 It would not be helpful to have aliasing clarifications split across two different
documents.

To use your analogy, I like having both the axioms and the theorems (especially the
non-obvious ones) in a single document, but I can understand your point of view too.

Reported by johnson.troy.a on 2013-01-23 21:51:35

[Former user]

I strongly disagree about removing footnote 14, because I feel it has a much broader
audience than the clarification proposed in this issue. I've argued in comments 12
and 14 that the clarification proposed in this issue is only relevant to optimizer
writers. Troy has argued that it may rarely also be of interest to programmers who
want to micromanage their restrict keywords. 

Whichever view you accept, I hope we can agree that the current issue applies to a
property that is strictly "beneath" the level of the abstract machine (the central
goal of the semantic specification). Aliasing properties that an optimizer can infer
from a function declaration has no semantic impact on the abstract machine; by definition
any correct optimizations on a legal program must preserve the external semantic behavior
of the unoptimized abstract machine. Stated another way, the topic of this issue never
has an impact on the *correctness* of a user program, merely the compiler analysis
used to perform optimizations.

In contrast, the primary purpose of footnote 14 clarifies a non-obvious restriction
on the correctness of user programs, and thus has a much wider audience. The footnote
is annotating semantic para 13:

     The block size is a part of the type compatibility(14)

Most users lacking a deep understanding of C99 would not understand the full correctness
implications of this powerful statement without a footnote. Specifically, the footnote
clarifies that a UPC program which does something like the following is invalid and
leads to undefined behavior:

shared int *p1 = upc_alloc(1);
shared int **pp1 = &p1;
shared [10] int **pp2 = (void *)pp1;
**pp2 = 5;

Note this program is fully type-correct and should not be rejected by the type checker,
but it is erroneous because it has aliased two pointers (pp1 and pp2) with incompatible
referent types (and those types are incompatible solely because of the difference in
block size and para 13). This program is likely to demonstrate incorrect behavior at
runtime in any UPC compiler that optimizes phaseless PTS using a dedicated representation.
In fact, the motivation for this semantic restriction on the user was precisely to
allow implementations to perform that powerful optimization.

Footnote 14 clarifies a semantic restriction that affects the correctness of programs
and that restriction DOES apply at the level of the abstract machine. All users need
to understand this property in order to write correct UPC programs with aggressive
use of pointer-to-shared. Despite the fact the word "alias" appears in the text of
the footnote, this text is mostly targeted at end-users and not optimizer writers.
I agree with Paul's analogy about providing semantic axioms and letting compiler writers
derive the theorems they need to write a correct optimization, but I don't think we
should expect the same level of sophistication from casual UPC programmers. Important,
non-obvious restrictions on program correctness should be spelled out explicitly for
users in the interests of clarity, and that's what footnote 14 does.

Reported by danbonachea on 2013-01-24 07:12:31

[Former user]

As an aside, I think the importance of this issue pales in comparison to issues 3 and
85, which are directly blocking progress on the ratification of 1.3. My impression
from the call is we'd agreed to table this for now in the interests of focusing on
the high-priority issues?

Reported by danbonachea on 2013-01-24 07:37:33 - Labels added: Priority-Low - Labels removed: Priority-Medium

[Former user]

RE importance, note the owner field for this issue versus issues 3 and 85.  I'm dealing
with this issue and Steve is handling issues 3 and 85, so this discussion isn't impeding
his progress on 3 or 85.

RE footnote 14, yes, it is a more important clarification than the one that I am proposing,
so could we keep footnote 14 in the spec but repeat it (quote it verbatim) in the companion
document near the new text?  I guess I just want one-stop shopping for UPC aliasing
information because there was a time that I went searching for guidance on UPC aliasing
rules and the only thing I could find anywhere was footnote 14 and it was insufficient
for my needs.  Just trying to make it easier for others despite whatever size audience
that ends up being.

Side note:

RE phaseless PTS and "the motivation for this semantic restriction on the user was
precisely to allow implementations to perform that powerful optimization" -- Cray intentionally
got rid of phaseless PTS years ago.  It was very awkward to deal with PTS's of two
different sizes in all phases of our compiler and runtime implementation, plus gave
the generated code no measurable performance benefit despite its theoretical prospects.
 It actually used to give multiple customers headaches when they would change the block
size of a PTS inside a struct only to discover that doing so changed their struct size,
struct packing, field alignments, etc. which they had carefully designed to fit in
a cache line or to make some other manual optimization work correctly.  I like the
no-alias implications of footnote 14 because it assists with compiler alias analysis,
but don't find phaseless PTS to be important at all -- it's just confusing.

Reported by johnson.troy.a on 2013-01-24 18:55:19

[Former user]

First, I'm not sure about the implications of the following proposed paragraph:
"8   A pointer-to-shared cannot alias with an array that is not shared qualified;"

I just made up a contrived aliasing example and could run it successfully with BUPC
(with --enable-sptr-struct).

int main(int argc, char **argv)
{
  shared [0] char *p = 0; 
  char a[1] = {'U'};
  p += (size_t)&a[0];
  printf("*p is %c\n", *p);
  return 0;
}

Second, I also feel that Footnote 14 is too much a burden to the user because it requires
the user to guarantee that there is always no aliasing between two pointers to pointer-to-shared.

To conclude, I agree with Paul's comment #17 that both Troy's proposed language and
Footnote 14 should go to the companion document rather than the spec.

Reported by [e-mail] on 2013-01-24 20:09:44

[Former user]

That example has undefined behavior (see ISO/IEC 9899 6.5.6 paragraph 8), so as far
as the spec is concerned, there is no aliasing.  The fact that aliasing occurs with
a particular implementation is irrelevant.

Reported by [e-mail] on 2013-01-24 20:18:52

[Former user]

RE comment 23:

I also ran the example with Cray UPC :-).

But my main point is actually that it would be very "Risky" for a compiler to assume
that a local array would not be modified through a pointer-to-shared, whether it's
an accident or a buffer-overrun attack.  If I understood correctly, this assumption
was the main motivation of this issue brought up in comment 4.

Reported by [e-mail] on 2013-01-24 20:46:41

[Former user]

I agree with Steve that Yili's example in comment #22 is an erroneous program, and thus
behavior is undefined and it doesn't matter what the optimizer does with it - garbage
in, garbage out. Troy's text "A pointer-to-shared cannot alias with an array that is
not shared qualified" is valid for all correct UPC programs, and thus a safe assumption
for the alias analysis to make. There are more subtle ways to write an incorrect C99
program  (analogous to comment #19) which introduce aliasing which is equally erroneous
with undefined effects - this is one of the fundamental downsides of a non-typesafe
language and not something we can "fix".

" I also feel that Footnote 14 is too much a burden to the user"
"I like the no-alias implications of footnote 14 because it assists with compiler alias
analysis, but don't find phaseless PTS to be important at all"

Footnote 14 and the para 13 it clarifies date back to UPC 1.1 (ie over 10 years) and
IMHO are not open to semantic change. Relaxing the para 13 restriction would break
many compilers, including breaking BUPC in fundamental ways. 

Our experiments over the years have turned up many examples where the phaseless PTS
optimization makes a *huge* difference in the performance of pointer-intensive codes.
It's possible that much of this benefit arises because BUPC is source-to-source, so
the module generating assembly code lacks knowledge of PTS semantics and arithmetic.
In any case, it's a very important optimization for us. It also has the nice benefit
of recovering any performance cost that might be associated with fully-general blocked
PTS for any codes that don't use that feature (global performance impact is one of
the main arguments to remove fully-general array blocking from the language).

Reported by danbonachea on 2013-01-25 00:12:48