Clarifying pointers to shared arrays, and multi-D shared arrays

[GoogleCodeExporter]

Evidence for pointer-to-local interpretation
--------------------------------------------

The following parts of the UPC spec and C99 spec indicate that a pointer to an
array-of-shared is NOT a pointer-to-shared:

UPC 1.2 3.2.3 - "shared array: an array with elements that have shared qualified
type"

UPC 1.2 3.4 - "pointer-to-shared: a pointer whose referenced type is
shared-qualified"

UPC 1.2 6.5.2.1.4 - "In an array declaration, the type qualifier applies to the
elements."

C99 6.7.3.8 - "If the specification of an array type includes any type
qualifiers, the element type is so qualified, not the array type."

Because the pointer's target is an array and the array itself cannot be shared 
qualified, such a pointer must be a pointer-to-local.  This conclusion is very
non-intuitive to most users.

Evidence for pointer-to-shared interpretation
---------------------------------------------

Other parts of the spec appear to (very indirectly) imply that such a pointer is
indeed a pointer-to-shared:

UPC 1.2 6.5.2.1.5 - "For any shared array, a, upc_phaseof( &a ) is zero."

UPC 1.2 7.2.3.2 - "size_t upc_phaseof( shared void *ptr );"

C99 6.5.3.2.3 - "if the operand is the result of a [] operator, neither the &
operator nor the unary * that is implied by the [] is evaluated and the result
is as if the & operator were removed and the [] operator were changed to a +
operator."

If the call to upc_phaseof( &a ) is legal, then &a must be a pointer-to-shared. 

However, &a is distinct from &a[0] and simply "a" given the quoted section of 
C99, which establishes the equivalence between &a[0] and a.  &a is a pointer to
an array.

Recommendation
--------------

The spec should be clarified.  The pointer-to-local interpretation is the most 
consistent with the rest of the spec, but users seem to expect a 
pointer-to-shared.  If it IS a pointer-to-shared, then there are other issues to
resolve with regards to pointer-to-shared arithmetic on such a pointer.

Original issue reported on code.google.com by johnson....@gmail.com on 13 Mar 2012 at 3:49

[GoogleCodeExporter]

The following code illustrates one interesting aspect of this ambiguity:

typedef int T1;
shared T1* p1;

typedef int T2[2];
shared T2* p2;

Under the pointer-to-local interpretation, p1 is a pointer-to-shared but p2 is 
a pointer-to-local.  Therefore, for a programmer, "shared <TYPE>*" is an 
ambiguous pointer-to-something until they track down the typedef and check if 
it is an array.

The pointer-to-shared interpretation treats both p1 and p2 as a 
pointer-to-shared, but then what does it mean to do pointer arithmetic on p2?  
Consider these examples:

shared [10] int A[THREADS][10];

typedef int T[10];
shared [10] T* p;

p = &A[0];
p = p + 1;   // Does p == &A[1] afterward?
(*p)[3] = 1; // Does this set A[1][3]?

-------------------

shared [5] int A[20][10];

typedef int T[10];
shared [5] T* p;

p = &A[0];
p = p + 1;
(*p)[9] = 1; // Does this set A[1][9]?

Original comment by johnson....@gmail.com on 18 Mar 2012 at 5:53

[GoogleCodeExporter]

Does anyone have any comments on this issue?  This is one issue that I'd like 
to see clarified sooner than later because different compilers currently 
resolve this issue differently.

Original comment by johnson....@gmail.com on 29 May 2012 at 3:24

[GoogleCodeExporter]

Attached, is a test program which attempts to codify the examples shown above.  
Please review and correct the example if it doesn't accurately demonstrate the 
issue.

When compiled with GUPC, it fails as follows.

$ upc -fupc-threads-2 -fupc-debug -W -Werror -Wpedantic -O2 -o array_test 
array_test.upc
array_test.upc: In function ‘main’:
array_test.upc:28:3: error: UPC operator upc_blocksizeof applied to a 
non-shared type
   assert (upc_blocksizeof &B[1] == 0);
   ^

When compiled with BUPC, it fails as follows.

$ $ bld/upcr-packed-dbg/dbg/upcc -network=smp -T2 -o array_test array_test.upc  

upcc: error during UPC-to-C translation (sgiupc stage): 
array_test.upc: In function `main':
array_test.upc:26: warning: assignment from incompatible pointer type
array_test.upc:28: upc_blocksizeof applied to a nonshared type
array_test.upc:29: warning: comparison of distinct pointer types lacks a cast
array_test.upc:32: warning: assignment from incompatible pointer type

Here is the text of the program.

     1  #include <upc.h>
     2  #include <assert.h>
     3
     4  shared [5]  int A[5*THREADS];
     5  shared [10] int B[THREADS][10];
     6  shared [5]  int C[20][10];
     7
     8  typedef int TB[10];
     9  shared [10] TB* pb;
    10
    11  typedef int TC[10];
    12  shared [5] TC* pc;
    13
    14  int main()
    15  {
    16    size_t bs_a, bs_a_0;
    17    size_t phase_a, phase_a_0;
    18    bs_a = upc_blocksizeof A;
    19    bs_a_0 = upc_blocksizeof A[0];
    20    assert (bs_a == 5);
    21    assert (bs_a == bs_a_0);
    22    phase_a = upc_phaseof (A);
    23    phase_a_0 = upc_phaseof (&A[0]);
    24    assert (phase_a == 0);
    25    assert (phase_a == phase_a_0);
    26    pb = &B[0];
    27    pb = pb + 1;   // Does pb == &B[1] afterward?
    28    assert (upc_blocksizeof &B[1] == 0);
    29    assert (pb == &B[1]);
    30    (*pb)[3] = 1;   // Does this set B[1][3]?
    31    assert (B[1][3] == 1);
    32    pc = &C[0];
    33    pc = pc + 1;
    34    (*pc)[9] = 1; 
    35    assert (C[1][9] == 1);
    36    return 0;
    37  }

They agree on the interpretation of line 28 as an error.  (Note: the 
introduction of parentheses after the upc_blocksizeof operator will not change 
the meaning or the result, due to operator precedence.)

Original comment by gary.funck on 29 May 2012 at 4:27

Attachments:

• array_test.upc

[GoogleCodeExporter]

So first, for completeness, Cray emits this message (which is very oddly worded 
-- I'll have to look into that):

CC-1172 craycc: WARNING File = gary.c, Line = 28
  Argument of upc_blocksizeof is a pointer to a shared type (not shared type
          itself).

    assert (upc_blocksizeof &B[1] == 0);
    ^

When I run the executable:

a.out: gary.c:28: main: Assertion `upc_blocksizeof( &B[1] ) == 0' failed.

--------

You chose upc_blocksizeof for this example code.  If you switch upc_blocksizeof 
to upc_phaseof or upc_threadof, the error issued by BUPC goes away.  Does GUPC 
produce a consistent error for all three?

Original comment by johnson....@gmail.com on 29 May 2012 at 4:46

[GoogleCodeExporter]

On this virtual Monday, it seems that I need another cup of coffee.  Attached 
an updated example with two corrections:

- check for correct block size (ie, 10) of B.

- require indirection to check for the blocksize B[1]:
     assert (upc_blocksizeof (*&B[1]) == 10);

- add a check for the block size of *pb:
      assert (upc_blocksizeof (*pb) == 10);

GUPC compiles this without complaint, but fails at runtime:

$ upc -fupc-threads-2 -fupc-debug -W -Werror -Wpedantic -O2 -o array_test 
array_test.upc
$ array_test
array_test: at array_test.upc:30, UPC error: Invalid conversion of shared 
address to local pointer;
thread does not have affinity to shared address

BUPC issues some warnings:

$ bld/upcr-packed-dbg/dbg/upcc -network=smp -T2 -o array_test array_test.upc
array_test.upc: In function `main':
array_test.upc:26: warning: assignment from incompatible pointer type
array_test.upc:30: warning: comparison of distinct pointer types lacks a cast
array_test.upc:33: warning: assignment from incompatible pointer type

and fails at runtime with an assertion.

$ bld/upcr-packed-dbg/dbg/upcrun array_test
array_test: array_test.upc:29: main: Assertion `upc_blocksizeof (*pb) == 10' 
failed.
array_test: array_test.upc:29: main: Assertion `upc_blocksizeof (*pb) == 10' 
failed.

I'm still not sure if I have got this example right.  Please 
review/comment/correct as needed.

Original comment by gary.funck on 29 May 2012 at 4:47

Attachments:

• array_test.upc

[GoogleCodeExporter]

For completeness, here is the new example.

     1  #include <upc.h>
     2  #include <assert.h>
     3
     4  shared [5]  int A[5*THREADS];
     5  shared [10] int B[THREADS][10];
     6  shared [5]  int C[20][10];
     7
     8  typedef int TB[10];
     9  shared [10] TB* pb;
    10
    11  typedef int TC[10];
    12  shared [5] TC* pc;
    13
    14  int main()
    15  {
    16    size_t bs_a, bs_a_0;
    17    size_t phase_a, phase_a_0;
    18    bs_a = upc_blocksizeof A;
    19    bs_a_0 = upc_blocksizeof A[0];
    20    assert (bs_a == 5);
    21    assert (bs_a == bs_a_0);
    22    phase_a = upc_phaseof (A);
    23    phase_a_0 = upc_phaseof (&A[0]);
    24    assert (phase_a == 0);
    25    assert (phase_a == phase_a_0);
    26    pb = &B[0];
    27    pb = pb + 1;   // Does pb == &B[1] afterward?
    28    assert (upc_blocksizeof (*&B[1]) == 10);
    29    assert (upc_blocksizeof (*pb) == 10);
    30    assert (pb == &B[1]);
    31    (*pb)[3] = 1;   // Does this set B[1][3]?
    32    assert (B[1][3] == 1);
    33    pc = &C[0];
    34    pc = pc + 1;
    35    (*pc)[9] = 1; 
    36    assert (C[1][9] == 1);
    37    return 0;
    38  }

Original comment by gary.funck on 29 May 2012 at 4:50

[GoogleCodeExporter]

Troy asks:
> You chose upc_blocksizeof for this example code.
> If you switch upc_blocksizeof to upc_phaseof or upc_threadof,
> the error issued by BUPC goes away.
> Does GUPC produce a consistent error for all three?

I used upc_blocksizeof, because it should issue a compile-time error message if 
passed an argument that is not shared qualified.  upc_phaseof() and 
upc_threadof() are implemented as functions, and will evaluate their argument 
(a pointer-to-shared) at runtime.  Both cases may be useful to illustrate this 
issue under discussion.  

Please make corrections/additions to illustrate your points and submit as an 
attachment.

As far as consistency, I haven't looked in detail at the warnings issued by 
BUPC to see if GUPC should be following suit, or if in fact the ambiguity of 
interpretation is leading to the warnings.  It is unexpected that GUPC may be 
silently casting a shared pointer to local, and that issue requires further 
investigation.  But first, I think it is worthwhile to have a complete test 
case for which there is consensus that it illustrates the point of this issue, 
and that it should be a valid UPC test program under a reasonable 
interpretation of the language specification.

Original comment by gary.funck on 29 May 2012 at 5:03

[GoogleCodeExporter]

I understand.  Your latest test case looks okay and compiles with Cray UPC 
without any messages.  It produces this error at runtime:

a.out: gary.c:30: main: Assertion `pb == &B[1]' failed.

Cray UPC currently follows the pointer-to-local interpretation in Comment #0, 
but we don't diagnose improper usage under that interpretation very well.  For 
example, to return to a simpler compile-only test:

#include <upc.h>

shared int x[THREADS];

int foo( void )
{
    return upc_phaseof( &x );
}

Under the pointer-to-local interpretation, the &x there should be either x or 
&x[0] to be legal.  Cray is prepared to make this an error in the next release 
if the community consensus is the pointer-to-local interpretation in Comment 
#0.  Cray is also prepared to make this code actually work as expected under 
the pointer-to-shared interpretation if that's what everyone decides upon.  We 
don't believe that either interpretation is clearly expressed by the UPC 1.2 
spec.

Original comment by johnson....@gmail.com on 29 May 2012 at 5:22

[GoogleCodeExporter]

The latest test case compiles and runs without any messages using HP UPC.

Gary wrote:
I used upc_blocksizeof, because it should issue a compile-time error message if 
passed an argument that is not shared qualified.

The specification does not require an error message.  Should it?

The language in the specification just says that the operator applies only to 
shared types; it is silent on how the compiler should treat operands that do 
not fit that criterion.  HP UPC does not currently issue an error message, but 
I now think it should do so, and think requiring an error message in this case 
is prudent.

Original comment by brian.wibecan on 29 May 2012 at 5:52

[GoogleCodeExporter]

Two additional data points: sgiupc and MTU's mupcc

Use of Gary's first test case w/ the SGI compiler yields:

$ sgiupc -c -LANG:upc_threads=2 test.upc 
"test.upc", line 28: warning: argument of upc_blocksizeof is a pointer to a
          shared type (not shared type itself)
    assert (upc_blocksizeof &B[1] == 0);
    ^

And MTU's mupcc:
$ mupcc -fthreads 2 test.c
"test.c", line 28: warning: argument of upc_blocksizeof is a pointer to a
          shared type (not shared type itself)
    assert (upc_blocksizeof &B[1] == 0);
    ^

Both of which are in agreement w/ GUPC, BUPC and Cray.
The message is both cases is identical to the one from the Cray compiler.

Unfortunately, in addition to that warning, the sgiupc version I have access to 
also ICEs on both examples.  So, I can't tell what the runtime result on the 
second test case might be.

When given the second testcase mupcc compiles and runs without any complaints.

Aside: I agree with Brian (in comment #9) that the warning that most of the 
compilers have issued about the argument to upc_blocksizeof does NOT appear to 
be required by the spec.  I also agree that a compiler *should* issue this 
warning, but DISAGREE that the spec should require it.

Original comment by phhargr...@lbl.gov on 29 May 2012 at 6:28

[GoogleCodeExporter]

Brian wrote:
> The specification does not require an error message.  Should it?
> The language in the specification just says that the operator applies only to
> shared types; it is silent on how the compiler should treat operands that do 
not
> fit that criterion.  HP UPC does not currently issue an error message, but I 
now
> think it should do so, and think requiring an error message in this case
> is prudent.

I will file a separate issue on this, if we determine that an error is not 
currently required, or if the behavior is currently unspecified, and there is 
some (possibly non-unanimous) support for defining this usage as an error.

Howver, my reading of the specification is that this usage is defined as an 
error.

The C99 specification in Section 4 ("Conformance") states:

4. Conformance
1 In this International Standard, ‘‘shall’’ is to be interpreted as a 
requirement on an implementation or on a program; conversely, ‘‘shall 
not’’ is to be interpreted as a prohibition.
2 If a ‘‘shall’’ or ‘‘shall not’’ requirement that appears 
outside of a constraint is violated, the behavior is undefined. Undefined 
behavior is otherwise indicated in this International Standard by the words 
‘‘undefined behavior’’ or by the omission of any explicit definition of 
behavior. There is no difference in emphasis among these three; they all 
describe ‘‘behavior that is undefined’’.

The UPC 1.2 Specification lists the following _constraint_ under section 
6.4.1.3 ("The upc_blocksizeof operator").

1 The upc blocksizeof operator shall apply only to shared-qualified expressions
or shared-qualified types. All constraints on the sizeof operator
[ISO/IEC00 Sec. 6.5.3.4] also apply to this operator.

Given the use of the term "shall" within a constraint, does the specification 
not already require that the argument of upc_blocksizeof must be a shared 
qualified expression.  Thus, any other usage is an error?

In the C99 specification, 'sizeof' lists this constraint:

1 The sizeof operator shall not be applied to an expression that has function 
type or an incomplete type, to the parenthesized name of such a type, or to an 
expression that designates a bit-field member.

Is the use of 'shall not' some how a stronger restriction, and therefore a 
prescription that these excluded cases are definitely erroneous uses, but the 
"shall" language of the UPC speicification is somehow more permissive?

If that is the case (and interpretation), I would like to see the UPC 
specification amended to use the "shall not" form of description, and will 
submit a separate tracking issue to discuss that proposal.  Otherwise, it seems 
to me that this erroneous use case is already covered.

Original comment by gary.funck on 29 May 2012 at 11:35

[GoogleCodeExporter]

Gary wrote:
> Given the use of the term "shall" within a constraint, does the specification 
not
> already require that the argument of upc_blocksizeof must be a shared 
qualified
> expression.  Thus, any other usage is an error?

It's clear that any other usage is relying on undefined behavior, which is 
incorrect usage.  The question is whether the compiler is required to issue an 
error message.  Theoretically, undefined behavior can be handled however the 
implementation wants.  In this case, no, the compiler has not up to now been 
required to diagnose and report this situation.  If it were, the behavior would 
change from "undefined" to "defined: produces a compile-time error message".

Original comment by brian.wibecan on 30 May 2012 at 7:29

[GoogleCodeExporter]

Brian wrote:
> It's clear that any other usage is relying on undefined behavior, which is
> incorrect usage.  The question is whether the compiler is required to
> issue an error message.

Brian/all, is there any place in the UPC specification that states explicitly 
that a translation error must be issued for a particular use case?  I see only 
footnote 7 referenced from section 6.3.3 ("UPC MAX BLOCK SIZE"), which states:

7 e.g. shared [UPC MAX BLOCK SIZE+1] char x[UPC MAX BLOCK SIZE+1] and shared
[*] char x[(UPC MAX BLOCK SIZE+1)*THREADS] are translation errors

When I read the constraint "shall apply only to shared-qualified expressions", 
it seems to me that passing a non-shared qualified expression value to 
upc_blocksizeof should be considered a translation error.

Original comment by gary.funck on 30 May 2012 at 9:29

[GoogleCodeExporter]

Back to the main line of this issue, I tried Troy's example in comment #8 on 
both GUPC and BUPC.

     1  #include <upc.h>
     2
     3  shared int x[THREADS];
     4
     5  int main()
     6  {
     7      return upc_phaseof( &x );
     8  }

There were no compiler complaints and the program returned 0 on all threads.  
It is possible that both compilers are handling this case of & applied to a 
shared array specially, or some other part of the shared GCC infra-structure is 
stepping in and interpreting &x to be equivalent to &x[0].  Probably, we would 
need to dump the internal tree representation to see how this is being handled.

Note that regarding the longer example that I submitted in comment #5 and the 
varying compiler responses to same, there may be other implementation issues 
that need to be understood and resolved besides this issue under discussion.

Original comment by gary.funck on 30 May 2012 at 11:16

[GoogleCodeExporter]

As an additional data point, consider the following "C" program.

$ cat -n array_qual.c
     1
     2  const int x[100];
     3
     4  int
     5  addr_eq_x (const int *p)
     6  {
     7    return p == x;
     8  }
     9
    10  int main()
    11  {
    12      return !addr_eq_x (&x);
    13  }

When compiled with GCC.

$ gcc -o array_qual array_qual.c
array_qual.c: In function ‘main’:
array_qual.c:12:5: warning: passing argument 1 of ‘addr_eq_x’ from 
incompatible pointer type [enabled by default]
     return !addr_eq_x (&x);
     ^
array_qual.c:5:1: note: expected ‘const int *’ but argument is of type 
‘const int (*)[100]’
 addr_eq_x (const int *p)
 ^

However, if the example is changed to:
    return !addr_eq_x (x);
all is well.

Does that help to shed any further light on the issue?

Original comment by gary.funck on 30 May 2012 at 11:27

[GoogleCodeExporter]

In comment #15, I indicated that just passing 'x', was OK.  Perhaps that was a 
cockpit error.  Here is the actual output.

$ cat -n array_qual.c
     1
     2  const int x[100];
     3
     4  int
     5  addr_eq_x (void *p)
     6  {
     7    return p == x;
     8  }
     9
    10  int main()
    11  {
    12      return !addr_eq_x (x);
    13  }

Above the only change is to pass 'x' instead of '&x'.

$ gcc -std=c99 -W -Wpedantic -o array_qual array_qual.c
array_qual.c: In function ‘main’:
array_qual.c:12:5: warning: passing argument 1 of ‘addr_eq_x’ discards 
‘const’ qualifier from pointer target type [enabled by default]
     return !addr_eq_x (x);
     ^
array_qual.c:5:1: note: expected ‘void *’ but argument is of type ‘const 
int *’
 addr_eq_x (void *p)
 ^

Original comment by gary.funck on 30 May 2012 at 11:39

[GoogleCodeExporter]

Regarding Comment #15, yes, it is instructive to experiment with how C handles 
pointers to arrays and it shows the exact problem.  &x in your example has type 
const int (*)[100], which in English is a pointer to an array of 100 const 
ints.  If you were to ask the question, "does this pointer type point to 
something that is const qualified?", the answer is No according to C99 6.7.3.8: 
"If the specification of an array type includes any type qualifiers, the 
element type is so qualified, not the array type."  The type is a pointer to an 
array and that array is not const qualified.

Now, replace "const" with "shared" and one concludes that a pointer to an array 
of shared-qualified objects is not a pointer-to-shared.  Therefore, it must be 
a plain old C pointer because there is no third alternative.  The real question 
is, is that what we want?  Is there some utility to going contrary to C99 and 
deciding that it is a pointer-to-shared?

Original comment by johnson....@gmail.com on 31 May 2012 at 2:51

[GoogleCodeExporter]

It seems ill-advised to go contrary to the C99 specification, because UPC is 
generally defined as an extension to "C", not a revision of "C".

Perhaps one way out is for UPC to disallow application of & to an operand 
expression that has type that is a shared array?

Are there other contexts where this "shared array" and "shared array element" 
dichotomy come into play?  Is that list sufficiently small that it can be 
compactly addressed in the UPC specification?

Original comment by gary.funck on 31 May 2012 at 3:08

[GoogleCodeExporter]

I think it is the main situation in which the dichotomy arises and I'm not 
aware of others.  I've seen people try to code essentially this:

    shared [M*N] int xyz[THREADS][M][N];

    typedef shared [M*N] int (*ptype)[M][N];
    ptype p;

    ...

    p = &xyz[t];

The intention here is to point p at the part of array xyz that is local to 
thread t, i.e.

       Thread 0       Thread 1         Thread t
                                     p
         N              N            |    N
    ------------   ------------ ...  ------------ ...
    |          |   |          |      |          |
 M  |          |   |          |      |          |
    |          |   |          |      |          |
    ------------   ------------ ...  ------------ ...

such that p[0 <= i < M][0 <= j < N] reference data on Thread t.

Given what I just wrote in Comment #17, p is a pointer to an array of M of an 
array of N shared ints.  Because that makes it a normal C pointer, p has no 
thread or phase associated with it, so the fact that it points to data on 
Thread t cannot be represented and it cannot participate in pointer-to-shared 
arithmetic.

To go contrary to C99, we'd need to decide that code similar to the above is 
sufficiently useful.

Original comment by johnson....@gmail.com on 31 May 2012 at 4:45

[GoogleCodeExporter]

Er, that should be "(*p)[0 <= i < M][0 <= j < N] reference data on Thread t."

Original comment by johnson....@gmail.com on 31 May 2012 at 4:47

[GoogleCodeExporter]

For an example of "real code" that tries to use a pointer to an array of 
shared, see the UPC Run Time Error Detection Test suite from ISU: 
http://rted.public.iastate.edu/UPC/

Where tests such as RTED_UPC/UPC/C_Outofbnds/c_C_10_1_a_F.upc have declarations 
like:

shared [K] float (* arrA)[K];

Original comment by johnson....@gmail.com on 5 Jun 2012 at 7:06

[GoogleCodeExporter]

I'd like to see this answered in 1.3.

Original comment by johnson....@gmail.com on 15 Jun 2012 at 5:09

• Added labels: Milestone-Spec-1.3

[GoogleCodeExporter]

As an additional data point, clang and GCC appear to differ on the 
interpretation of whether the target of a pointer to an array which in turns 
has type qualified elements is itself type qualified or not.

Consider:

const int array[10];
void *ptr = &array;

Here is what a recent version of clang does with the test case.

$ clang -cc1 -std=c99 t.c   
t.c:2:7: warning: initializing 'void *' with an expression of type 'const int 
(*)[10]' discards qualifiers
void *ptr = &array;
      ^     ~~~~~~
1 warning generated.

which indicates that clang propagated the element type qualifiers to the array 
type that is the target of the declared pointer type.

A recent version of GCC on the other hand will compile the test case above 
without complaint (even with full pedantic warnings enabled).

Thus, GCC supports the interpretation cited by Troy, and clang does not.

GCC will issue a warning given this variation.

const int array[10];
void *ptr = array;

$ gcc -std=c99 -c t.c
t.c:2:13: warning: initialization discards ‘const’ qualifier from pointer 
target type [enabled by default]

This makes sense, because per the C99 specification 'array' on its own is 
interpreted as &array[0] which is a pointer to the first element of 'array'.

Original comment by gary.funck on 29 Jun 2012 at 11:18

[GoogleCodeExporter]

As a follow up to comment #12 above, regarding a compiler's response to a 
constraint violation ("shall" or "shall not"), the following section of the C99 
specification is applicable.

5.1.1.3 Diagnostics

1 A conforming implementation shall produce at least one diagnostic message 
(identified in an implementation-defined manner) if a preprocessing translation 
unit or translation unit contains a violation of any syntax rule or constraint, 
even if the behavior is also explicitly specified as undefined or 
implementation-defined. Diagnostic messages need not be produced in other 
circumstances.

Per above, doesn't the specification require that a UPC compiler issue a 
diagnostic if the operand of upc_blocksizeof is not a shared qualified 
expression?

Original comment by gary.funck on 30 Jun 2012 at 12:14

[GoogleCodeExporter]

An additional example, using upc_forall:

#include <upc.h>
#include <stdio.h>
#include <assert.h>

int main(void)
{
  static shared [10] int array[THREADS][10];
  upc_forall(int i = 0; i < THREADS; ++i; array[i])
    {
      int *p = (int *)array[i];
      for (int j = 0; j < 10; ++j)
        {
          p[j] = MYTHREAD * 10 + (j + 1);
        }
    }
  upc_barrier;
  if (MYTHREAD == 0)
    {
      for (int i = 0; i < THREADS; ++i)
        for (int j = 0; j < 10; ++j)
          {
            printf ("array[%d][%d] = %d\n", i, j, array[i][j]);
            assert (array[i][j] == i * 10 + (j + 1));
          }
      printf ("Test passed.\n");
    }
  return 0;
}

This test case passes when compiled with GUPC.

BUPC issues the following error:

forall_array.upc: In function `main':
forall_array.upc:8: Affinity expression is not an integral/shared address 
expression

which makes sense.  Since GUPC is probably using logic common to GCC, I'm 
guessing that the expression was promotoed to the address of the array.

Original comment by gary.funck on 5 Jul 2012 at 8:58

[GoogleCodeExporter]

"As an additional data point, clang and GCC appear to differ on the 
interpretation of whether the target of a pointer to an array which in turns 
has type qualified elements is itself type qualified or not."

I'm guessing clang's warning message is just a bit unclear and that they're 
still simply saying that the element type 'const int' is qualified, and by 
casting the pointer to void *, that qualification is lost.  The message is 
simply ambiguous as to what part of the type is qualified.  I can't imagine 
them ignoring C99 6.7.3.8 that blatantly. ;)

Original comment by sdvor...@cray.com on 14 Aug 2012 at 2:59

[GoogleCodeExporter]

Steve wrote: "I'm guessing clang's warning message is just a bit unclear and 
that they're still simply saying that the element type 'const int' is 
qualified, and by casting the pointer to void *, that qualification is lost."

Agreed.  This version of the test compiles without complaint.

int main(void)
{
const int array[10];
const void *ptr = &array;
return 0;
}

Original comment by gary.funck on 14 Aug 2012 at 3:40

[GoogleCodeExporter]

As a more motivating example of the implications of this, consider trying to 
dynamically allocate a multidimensional shared array:

  shared int (*array0)[10];
  shared int (*array1)[10];
  array0 = (shared int (*)[10]) upc_all_alloc( 10 * THREADS, sizeof( int ) );
  array1 = array0 + 1;

Where does array1 point, and why?

Is it even possible to dynamically allocate a multidimensional shared array 
under the pointer-to-local interpretation, given that the return from all the 
dynamic shared allocation routines returns a pointer-to-shared that would be 
immediately cast to pointer-to-local?

Original comment by sdvor...@cray.com on 14 Aug 2012 at 4:29

[GoogleCodeExporter]

Set default Consensus to "Low".

Original comment by gary.funck on 19 Aug 2012 at 11:26

• Added labels: Consensus-Low

[GoogleCodeExporter]

Note that code affected by this is very common in some publicly available test 
suites--notably the Run-time Error Detection suite from Iowa State University 
(http://rted.public.iastate.edu/UPC/) and the GWU Unified Testing Suite suite 
from (The) George Washington University 
(http://threads.hpcl.gwu.edu/sites/guts).  It appears that they are expecting 
the "pointer-to-shared" interpretation, as the code doesn't work as documented 
under the "pointer-to-local" interpretation.

Original comment by sdvor...@cray.com on 4 Sep 2012 at 4:45

[GoogleCodeExporter]

Another small program to consider.  I'm not sure what this argues for, as the 
results do not seem intuitive to me under either interpretation.

#include<stdio.h>
#include<upc.h>

typedef int MYTYPEA;
typedef int MYTYPEB[2];

shared [2] MYTYPEA a[2*THREADS];
shared [2] MYTYPEB b[2*THREADS];

int main()
{
    if ( MYTHREAD == 0 ) {
        if ( upc_threadof( &a[0] ) == upc_threadof( &a[1] ) ) {
            printf( "&a[0] and &a[1] point to the same thread\n" );
        }
        else {
            printf( "&a[0] and &a[1] point to different threads\n" );
        }

        if ( upc_threadof( &b[0] ) == upc_threadof( &b[1] ) ) {
            printf( "&b[0] and &b[1] point to the same thread\n" );
        }
        else {
            printf( "&b[0] and &b[1] point to different threads\n" );
        }
    }
}

Under the local pointer interpretation, &b[0] and &b[1] are NOT shared 
pointers, and it is therefore erroneous to pass them to upc_threadof().

Under the shared pointer interpretation, when run with more than 1 thread, it 
should print

&a[0] and &a[1] point to the same thread
&b[0] and &b[1] point to different threads

which seems really odd until you look at the typedefs.  Perhaps EXAMPLE 4 under 
Array declarators could be expanded upon to make this result more clear?

Original comment by sdvor...@cray.com on 4 Sep 2012 at 9:56

[GoogleCodeExporter]

Some additional observations, consider UPC v1.2 6.4.2 4:

"In addition, the correspondence between shared and local addresses and 
arithmetic is defined using the following constructs:

  T *P1, *P2;
  shared T *S1, *S2;

  P1 = (T*) S1; /* allowed if S1 has affinity to MYTHREAD */
  P2 = (T*) S2; /* allowed if S2 has affinity to MYTHREAD */"

Assume T is defined as

  typedef int T[2];

Then it is erroneous to use the results of those casts in the general case, as 
(*P1)[1] (or (*P2)[1]) may point to unused memory as the shared object may have 
no additional elements on the local thread.

==========

Also, consider C99 6.5.2.1 3:

"Successive subscript operators designate an element of a multidimensional 
array object.  If E is an n-dimensional array (n >= 2) with dimensions 
ixjx...xk then E (used as other than an lvalue) is converted to a pointer to an 
(n-1)-dimensional array with dimensions jx...xk.  If the unary * operator is 
applied to this pointer explicitly, or implicitly as a result of subscripting, 
the result is the pointed-to (n-1)-dimensional array, which itself is converted 
into a pointer if used as other than an lvalue."

Indexing of multidimensional arrays is defined using pointers to arrays, and 
therefore, indexing of multidimensional shared arrays is defined using pointers 
to shared arrays.  Therefore, this issue affects not only pointers to shared 
arrays, but any non-trivial use of multidimensional shared arrays.

Original comment by sdvor...@cray.com on 7 Sep 2012 at 4:43

[GoogleCodeExporter]

Getting back to the original issue here..

It seems to me that at a high-level this problem arises because UPC defines 
"shared" as a C type qualifier (mostly for syntactic convenience), but it's 
really much more than that. When C99's type qualifiers (const, restrict, 
volatile) are applied to an object (eg an array element) they truly qualify and 
enforce a property upon that specific element (eg const states that element may 
not be modified), and the property is orthagonal to the (cast-free) expression 
used to reach the object. UPC's shared qualifier is different, because it 
specifies not only a property of the qualified object (ie it lives in shared 
space) but ALSO a property of the expression used to reach that object (ie a 
pointer-to-shared must be a "wide" pointer, with a different representation 
than a pointer-to-local). So when you declare a pointer-to-shared (shared int 
*p), it is technically the *referent* type that is shared-qualified, but the 
representation and type compatibility of the pointer itself is also affected. I 
believe there is no analogue to this in C99. The UPC shared qualifier is 
already "much more" than a plain C99 type qualifier, and most of UPC 6.4 is 
dedicated to explaining the monstrous additional properties of our "super 
qualifier". I don't see it as a serious additional conflict with C99 to extend 
the specification of our super-qualifier a tiny bit further to include a 
special relationship with arrays.

IMHO it seems linguistically cleanest (and also most intuitive) to treat 
pointer-to-shared-array similarly to pointer-to-shared-scalar, ie follow the 
"pointer-to-shared" interpretation suggested in comment #0. This has the 
benefit of maintaining the duality of pointers and arrays that most C 
programmers intuitively take for granted, extended to shared types.

Proposal:

Keeping in mind:
C99 6.7.3.8 - "If the specification of an array type includes any type
qualifiers, the element type is so qualified, not the array type."

Update the following text from UPC 1.2 6.5.2.1.4:

"In an array declaration, the type qualifier applies to the elements."

to read something like:

"As specified in [C99 6.7.3.8], if the specification of an array type includes 
any type qualifiers (possibly via one or more typedefs), the element type is so 
qualified, not the array type. Additionally, the shared qualifier ALSO applies 
to the array itself~\footnote{This implies that a pointer to an array-of-shared 
is itself a pointer-to-shared.}"

Much of the discussion in prior comments seems to implicitly assume we should 
follow the pointer-to-local interpretation, but aside from quoting existing 
spec language I don't see any strong arguments against taking the 
pointer-to-shared interpretation suggested in this proposal. Everyone seems to 
agree this is the most intuitive behavior, so is there anything that "breaks" 
if we clarify to take this option?

Original comment by danbonachea on 7 Sep 2012 at 5:56

[GoogleCodeExporter]

"As specified in [C99 6.7.3.8], if the specification of an array type includes 
any type qualifiers (possibly via one or more typedefs), the element type is so 
qualified, not the array type. Additionally, the shared qualifier ALSO applies 
to the array itself~\footnote{This implies that a pointer to an array-of-shared 
is itself a pointer-to-shared.}"

I think it would be much simpler to change the definition of 
'pointer-to-shared' (UPC 3.4.1) to be 'a pointer whose referenced type is 
shared qualified or is a shared array type'.  Then we don't need an exception 
to C99 6.7.3.8.

Original comment by sdvor...@cray.com on 7 Sep 2012 at 8:10

[GoogleCodeExporter]

RE Comment 33: "Much of the discussion in prior comments seems to implicitly 
assume we should follow the pointer-to-local interpretation, but aside from 
quoting existing spec language I don't see any strong arguments against taking 
the pointer-to-shared interpretation suggested in this proposal. Everyone seems 
to agree this is the most intuitive behavior, so is there anything that 
"breaks" if we clarify to take this option?"

I'm fairly neutral on what option UPC /should/ support.  The pointer-to-local 
interpretation has some limited utility in allowing a thread to indirectly 
refer to one of many arrays of shared that have the same shape, but it can 
point only to the start of a whole array since it lacks affinity and phase 
information.  The pointer-to-shared interpretation has greater utility in 
providing access to slices of multidimensional arrays of shared objects, but 
then again multidimensional arrays are generally accepted to be a pain in C and 
I'm not sure that it was a goal of UPC to address that in any way.

Given public codes that I have seen, there is some user desire for the 
pointer-to-shared interpretation.  What "breaks" if we choose it is not 
anything else in the UPC spec, although for clarity the section on pointer 
addition could benefit from a note about how it applies to a pointer to array 
of shared.  What breaks is existing compiler type systems.  The 
pointer-to-local interpretation is what naturally falls out by following the C 
rules, at least for Cray and GCC.  So settling on the pointer-to-shared 
interpretation for UPC 1.3 is basically saying to at least two implementers "go 
change your type system."  I don't mind having to make the change, I just 
wonder if that's the sort of change that people expected in a 1.2->1.3 version 
bump.

Original comment by johnson....@gmail.com on 13 Sep 2012 at 4:55

[GoogleCodeExporter]

"So settling on the pointer-to-shared interpretation for UPC 1.3 is basically 
saying to at least two implementers "go change your type system.""

The same is true for settling on the pointer-to-local interpretation.

"I think it would be much simpler to change the definition of 
'pointer-to-shared' (UPC 3.4.1) to be 'a pointer whose referenced type is 
shared qualified or is a shared array type'."

We would also need a clarification to the definition of "shared array type":

Original: "shared array: an array with elements that have shared qualified type"
Suggestion 1: "shared array: an array with elements that have shared qualified 
or shared array type"
Suggestion 2: "shared array: an array with an underlying element type that is 
shared qualified"

Without this change, it is not clear that AAA in

  shared int AAA[3][4][5][6];

is a "shared array" type, because the elements of AAA are "array [4][5][6] of 
shared int", and are thus not shared qualified.  (Question: "underlying element 
type" is a well-understood concept, isn't it?  It wouldn't need explanation?)

Dan's suggested change to what is considered "shared qualified" covers this 
case by making each of the array components "shared qualified" recursively.

I think both wordings are good.  I have a slight preference for keeping the 
concept of "shared qualified" attached to the underlying element type, but I 
like the simplicity of Dan's suggestion, too.

Original comment by brian.wibecan on 13 Sep 2012 at 5:39

[GoogleCodeExporter]

"The same is true for settling on the pointer-to-local interpretation."

Yep, certainly true.  Cray UPC follows pointer-to-local and notes in 
documentation that the UPC spec is ambiguous, but I'm sure there are other UPC 
implementations that follow pointer-to-shared.  It would be interesting to have 
a count of each, but I'm just raising the question of if it's a UPC 1.2->1.3 
level of change to actually pick one.  I've investigated the changes enough 
that I believe it's not a massive undertaking for our implementation, so I'm 
fine with pointer-to-shared for 1.3, but I could sympathize with other 
implementations where it might require more work or where they were not 
expecting a type system change.

Original comment by johnson....@gmail.com on 13 Sep 2012 at 5:57

[GoogleCodeExporter]

"(Question: "underlying element type" is a well-understood concept, isn't it?  
It wouldn't need explanation?)"

Actually, we already have this problem elsewhere in the spec, for instance 
6.5.1.10 says (emphasis mine):

"The layout qualifier dictates the blocking factor for the type being shared 
qualified.  This factor is the nonnegative number of consecutive ELEMENTS (when 
evaluating pointer-to-shared arighmetic and array declarations) which have 
affinity to the same thread..."

Original comment by sdvor...@cray.com on 13 Sep 2012 at 6:00

[GoogleCodeExporter]

"so is there anything that "breaks" if we clarify to take this option?"

We'll probably have to clean-up the pointer-to-shared arithmetic section, as 
there's nothing in there that clearly states how it should work in this case.  
For the expected behavior, I believe we'd have to point out that the increment 
would need to be scaled by the number of elements in the array type when 
determining the new phase and thread.

Original comment by sdvor...@cray.com on 13 Sep 2012 at 6:04

[GoogleCodeExporter]

Steve proposed:
"I think it would be much simpler to change the definition of 
'pointer-to-shared' (UPC 3.4.1) to be 'a pointer whose referenced type is 
shared qualified or is a shared array type'.  Then we don't need an exception 
to C99 6.7.3.8."

I'm concerned Steve's suggested wording may be too strong (or possibly just 
ambiguous). We are trying to clarify that an array of shared elements is itself 
a shared-qualified type, and thus a POINTER to an array of shared is a 
pointer-to-shared. Steve's wording could be interpreted (misread?) to imply 
that a shared array type IS a pointer-to-shared, which I don't think is what we 
want. In the spirit of C99 where pointers and arrays are often interchangeable, 
we want shared arrays and pointer-to-shared to be interchangeable in similar 
ways - but that is weaker than stating they are EQUIVALENT types, which they 
definitely are not (prime example being when you pass one to sizeof()). I think 
he probably meant to write something more like 'a pointer whose referenced type 
is shared qualified or WHOSE REFERENCED TYPE is a shared array type'

In any case, Steve's proposal is also incomplete - both in the ways pointed out 
by Brian in comment #36 wrt multi-D arrays, and more importantly in that it 
references a "shared array type", which as we've already discussed is a type 
that does not exist under C99 6.7.3.8, until we add an explicit exception.

So I stand by my original proposal in comment #33.

Original comment by danbonachea on 13 Sep 2012 at 6:12

[GoogleCodeExporter]

I don't like the proposal in comment #33, because it explicitly permits a 
shared-qualified type that doesn't obey affinity rules, doesn't permit a layout 
specifier, and could span multiple threads.  It also needlessly violates C99 
6.7.3.8.  Perhaps the wording in comment #34 is bad, but that can be fixed 
without adding new shared-qualified types that don't act like other 
shared-qualified types.

In general, there are a lot of places in the 1.2 spec that assume all shared 
arrays have a single dimension and are ambiguous if they have more than one 
dimension.  For instance (emphasis mine),

3.2.3.1
"shared array
an array with ELEMENTS that have shared qualified type"

3.9.1 
"phase
an unsigned integer value associated with a pointer-to-shared which indicates 
the ELEMENT-offset within an affinity block; ..."

6.4.2.4
{ see comment 32 }

6.4.2.5
"...The expression ((ptrdiff_t) upc_addrfield(S2) - (ptrdiff_t) 
upc_addrfield(S1)) shall evaluate to the same value as ((P2 - P1) * sizeof(T))"

This fails miserably if T is an array type.

6.4.3.6
"Shared objects with affinity to a given thread can be accessed by either 
pointers-to-shared or pointers-to-local of that thread."

What is the affinity of a shared object that spans multiple threads?

6.5.1.1.10
"... This factor is the nonnegative number of consecutive ELEMENTS (when 
evaluating pointer-to-shared arighmetic and array declarations) which have 
affinity to the same thread..."

6.5.2.1.3
"ELEMENTS of shared arrays are distributed in a round robin fashion, by chunks 
of block-size ELEMENTS, such that the i-th ELEMENT has affinity with thread 
(floor (i/block_size) mod THREADS)"

Fortran 2008 side-stepped this issue nicely by making dimensions that span 
images distinct from dimensions that span memory addresses.  UPC made things 
ridiculously complicated by supporting multiple block distributions that are 
barely used because they are so complicated.

Original comment by sdvor...@cray.com on 13 Sep 2012 at 6:57

[GoogleCodeExporter]

"I don't like the proposal in comment #33, because it explicitly permits a 
shared-qualified type that doesn't obey affinity rules, doesn't permit a layout 
specifier, and could span multiple threads."

This is a fair point.. which leaves us with no complete proposal that gives us 
everything we want.

Perhaps we should consider just DIRECTLY stating the property we're looking 
for, with something like:

Change 1.2 6.5.2.1.4:
"In an array declaration, the type qualifier applies to the elements."

to read something like:

"As specified in [C99 6.7.3.8], if the specification of an array type includes 
any type qualifiers (possibly via one or more typedefs), the element type is so 
qualified, not the array type. Additionally, a pointer to an array of shared 
elements is a pointer-to-shared.\footnote{This also applies to 
multi-dimensional arrays, so a pointer to an array of array of shared elements 
is a pointer-to-shared.}" 

With the second sentence being the direct statement of the clarification we are 
attempting to provide. The footnote clarifies the rule also applies to multi-D.

"In general, there are a lot of places in the 1.2 spec that assume all shared 
arrays have a single dimension and are ambiguous if they have more than one 
dimension."

This is a valid point and seems worthy of study, but is also somewhat 
off-topic. Steve can you please create a new separate issue to address those 
ambiguities?

Original comment by danbonachea on 13 Sep 2012 at 7:32

[GoogleCodeExporter]

"Steve can you please create a new separate issue to address those ambiguities?"

Issue 85 has been created.

Original comment by sdvor...@cray.com on 13 Sep 2012 at 7:41

[GoogleCodeExporter]

I'll handle this one.

Original comment by ga10...@gmail.com on 14 Sep 2012 at 9:26

[GoogleCodeExporter]

Original comment by ga10...@gmail.com on 14 Sep 2012 at 9:27

[GoogleCodeExporter]

Sorry about the confusion. It's Friday evening and I hit the wrong key. 
Obviously.

Original comment by ga10...@gmail.com on 14 Sep 2012 at 9:28

[GoogleCodeExporter]

"I'll handle this one."

Didn't I get the action item on this (to write up the proposed changes with 
Dan's help)?

Original comment by sdvor...@cray.com on 14 Sep 2012 at 9:29

[GoogleCodeExporter]

fixed.

Original comment by danbonachea on 14 Sep 2012 at 9:36

[GoogleCodeExporter]

Original comment by sdvor...@cray.com on 21 Sep 2012 at 7:30

• Now blocking: #85

[GoogleCodeExporter]

Set critical priority on the unresolved technical issues slated for 1.3 which 
are blocking progress on ratification.

Original comment by danbonachea on 24 Jan 2013 at 7:40

• Added labels: Priority-Critical
• Removed labels: Priority-Medium