Clarification: can THREADS appear more than once in a PTS typedef (in a dynamic threads environment)?

[Former user]

Originally reported on Google Code with ID 95

The Clang UPC accepts the following typedefs without complaint in a dynamic threads
environment.


static void various(int ii, int jj)
{
  // These are illegal in dynamic threads environment:
  typedef shared int (*pc)[THREADS][ 13  ][THREADS];
  typedef shared int (*pd)[THREADS][ii+jj][THREADS];

This test case is described in full here:
https://upc-bugs.lbl.gov/bugzilla/show_bug.cgi?id=3057

In this test case, the typedef's above are used only as the operands of 'sizeof' and
not to declare array variables.  Thus, no error is detected.

The UPC language specification describes the constraints "Array declarators" in section
6.5.2.1.  I haven't tried yet to parse through the syntax description to determined
whether the typdef's above which declare pointers-to-shared in factor are considered
array declarators or not.  If not, then what are the operative parts of the specification
that apply to the typedef declarations above?

Reported by gary.funck on 2012-10-05 17:20:55

[Former user]

``` Ignoring the UPC spec for a moment, C99 allows typedefs of variable-length arrays:

C99 6.7.7-3: "In a declaration whose storage-class specifier is typedef, each declarator defines an identifier to be a typedef name that denotes the type specified for the identifier in the way described in 6.7.5. Any array size expressions associated with variable length array declarators are evaluated each time the declaration of the typedef name is reached in the order of execution."

so one could make an argument this typedef is permitted and defines a variable-length array type.

Now considering the current UPC text from 6.5.2.1 (emphasis added): "When a UPC program is translated in the dynamic THREADS environment and an ARRAY WITH SHARED-QUALIFIED ELEMENTS IS DECLARED with definite blocksize, the THREADS expression shall occur exactly once in one dimension of the array declarator (including through typedefs). Further, the THREADS expression shall only occur either alone or when multiplied by an integer constant expression."

This text clearly prohibits *instantiating* a cyclic shared array that includes multiple THREADS expressions in the dimensions. However it seems a bit "iffy" whether this applies to isolated typedefs of array types (which technically declare a TYPE, not an array), or similarly to declaring pointers to such arrays.

To answer Gary's question regarding the grammer, the C99 non-terminal "declarator" includes the array dimensions, and is used (via init-declarator->init-declarator-list) in every instantiation of the higher-level non-terminal "declaration", which includes all typedefs, array declarations, pointer declarations, etc. So that might be right place to plugin a strengthened constraint to prohibit these typedefs and similar shared array sub-types.

```

Reported by `danbonachea` on 2012-10-05 19:58:31

[Former user]

Reported by gary.funck on 2012-10-14 16:29:59

[Former user]

> the C99 non-terminal "declarator".. includes all typedefs, array declarations, 
> pointer declarations, etc. So that might be right place to plugin a strengthened

> constraint to prohibit these typedefs and similar shared array sub-types.

Upon further digging this would omit cast expressions, which are parsed via the non-terminal
"type-name".

Here is a proposed rewording of 6.5.2.1 that might accomplish what we're looking for:

"When a UPC program is translated in the dynamic THREADS environment, 
every {\em declarator} or {\em type-name} containing an array type with shared-qualified
elements and definite blocksize shall include the THREADS expression exactly once in
one dimension of the array (including through typedefs). 
Further, the THREADS expression shall only occur either alone or when multiplied by
an integer constant expression."

The idea here is to completely prohibit the problematic types from being expressed
anywhere in the program - ie extending the current prohibition on array declarations
to also cover typedefs, casts, and anything using them as a subtype.

Specifically, it seeks to prohibit cases like the following (in the dynamic threads
env):

shared int pa[THREADS][THREADS]; // array declaration : already clearly prohibited
by old language

typedef shared int (*pc)[THREADS][13][THREADS];  // typedef: original example

typedef shared int pb[THREADS][THREADS]; // typedef: similar example without pointer

shared int (**pd)[THREADS][THREADS];  // declaration of a pointer with a prohibited
subtype

shared void *p = (shared int (*)[THREADS][THREADS])upc_all_alloc(1,1);
  // cast expression including a prohibited subtype

I'd like to hear input from frontend implementers (and especially Gary) on this strengthened
constraint. Note the paragraph involved also affects closely-related issue 94.

Reported by danbonachea on 2013-01-17 07:05:28 - Blocked on: #94

[Former user]

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

Reported by danbonachea on 2013-01-24 07:40:02 - Labels added: Priority-Critical - Labels removed: Priority-Medium

[Former user]

I concur with the proposal in Comment #3, with the following refinement.

"multiplied by a *positive* integer constant expression"

(emphasis added)

Reported by gary.funck on 2013-01-28 21:51:37 - Labels added: Consensus-High - Labels removed: Consensus-Low

[Former user]

Official proposal for issues 94&95 mailed on 2/4/13:

--- upc-language.tex    (revision 199)
+++ upc-language.tex    (working copy)
@@ -665,18 +679,32 @@

 {\bf Constraints}

-\np When a UPC program is translated in the {\em dynamic
-    THREADS} environment and an array with shared-qualified elements
-    is declared with definite blocksize, the THREADS expression shall
-    occur exactly once in one dimension of the array declarator
-    (including through typedefs).  Further, the THREADS expression
+\np 
+    When a UPC program is translated in the {\em dynamic THREADS} environment,
+  \xreplaced[id=DB]{95}{%
+    every {\em declarator} or {\em type-name} containing an array type with 
+    shared-qualified elements and definite blocksize shall include the THREADS keyword
+  }{%
+    and an array with shared-qualified elements
+    is declared with definite blocksize, the THREADS expression shall occur 
+  }%
+    exactly once in one dimension of the array declarator
+    (including through typedefs).  
+  \xreplaced[id=DB]{94}{%
+    Further, the THREADS keyword shall only occur either alone 
+    or when multiplied by an integer constant expression
+    (as defined in [ISO/IEC00 Sec. 6.6]) with positive value.
+  }{%
+    Further, the THREADS expression
     shall only occur either alone or when multiplied by an integer
-    constant expression.\footnote{In the {\em static THREADS} environment
+    constant expression.
+  }%
+    \footnote{In the {\em static THREADS} environment
     THREADS is an integer constant expression, and is therefore valid in
     all dimensions.}

 \np \xadded[id=DB]{15}{
-    The THREADS expression
+    The THREADS keyword
     shall not appear anywhere in the declarator of a shared array with
     indefinite blocksize under the {\em dynamic THREADS} environment.
     }
@@ -704,19 +732,31 @@
 \np EXAMPLE 1: declarations allowed in either {\em static THREADS} or
     {\em dynamic THREADS} translation environments:

+\cbstart
 \begin{verbatim}
     shared int x [10*THREADS];
+    shared int x [THREADS*(100*20)];  
     shared [] int x [10];
 \end{verbatim}
+\cbend

 \np EXAMPLE 2: declarations allowed only in {\em static THREADS} translation
     environment:

+\cbstart
 \begin{verbatim}
     shared int x [10+THREADS];
     shared [] int x [THREADS];
     shared int x [10];
+    shared int x [THREADS][4*THREADS];
+    shared int x [THREADS*THREADS];
+    shared int x [THREADS*100*20];
+    shared int (**p)[THREADS][THREADS];
+    typedef shared int (*t)[THREADS][13][THREADS];
+    shared void *p = (shared int (*)[THREADS][THREADS])q;  
 \end{verbatim}
+\cbend
+\xchangenote[id=DB]{94}{SEVEN NEW EXAMPLES ADDED ABOVE}

 \np EXAMPLE 3: declaration of a shared array

Reported by danbonachea on 2013-02-04 17:46:56 - Status changed: PendingApproval

[Former user]

Steve's comments, moved from issue 3:

Don't we need to restrict this to shared array object declarators, so we can construct
pointers to dimensions lower than the THREADS-scaled dimension?

Consider the following example:

 static shared int array[THREADS][5];
 shared int (*pts)[5];
 pts = &array[MYTHREAD];

Wouldn't the declaration of 'pts' be illegal with this wording?

Reported by danbonachea on 2013-03-18 04:03:22

[Former user]

> Wouldn't the declaration of 'pts' be illegal with this wording?

Yes, the consensus on issue 95 thus far was to extend the THREADS-dimension requirement
under dynamic THREADS from shared array declarations to all shared array types. Under
those rules the declaration of pts in comment #7 would be a type error. The idea was
to prevent expressing types that cannot be instantiated or that can only point to things
that cannot be instantiated, although I guess we hadn't considered the corner case
of pointers to sub-arrays.

I agree that this particular example seems harmless, but it also seems like a very
strange thing to want to do. As discussed on previous telecons, pointer-to-array types
are already a rather "strange" bird, and this particular example is especially "weird"
with a cyclic blocking factor. However you can get the a very similar effect more clearly
and without breaking the new type rule by changing the declaration to a pointer-to-scalar
as follows:

shared int *pts2 = &array[MYTHREAD][0];

Here accesses to pts2[i] would behave the same as (*pts)[i]. Is there a motivation
to prefer the latter?

Here is a more realistic example, where the blocking factor "matches" the multi-d layout:

 static shared [5] int array[THREADS][5];
 shared [5] int (*pts3)[5];
 pts = &array[MYTHREAD];

However this can also be re-written more clearly, and without breaking the new type
rule as follows:

 shared [] int *pts4 = (shared [] int *)&array[MYTHREAD][0];

Is there a good motivation for allowing pointers to sub-arrays? If so we might consider
weakening the new type rule to allow them, but I would still like to prohibit examples
like in comment #0 which declare types that can never be instantiated under dynamic
threads, or pointers to same.

Reported by danbonachea on 2013-03-18 04:32:11

[Former user]

> Is there a good motivation for allowing pointers to sub-arrays?

Yes.  It allows you to treat dynamically allocated memory as a multidimensional array
where the left-most dimension (which isn't part of the pointer's referenced type...)
is the THREADS-scaled dimension.

What about the following wording?

"When a UPC program is translated in the dynamic THREADS environment, every shared
array declarator with definite blocksize shall include the THREADS expression exactly
once in one dimension of the array (including through typedefs).  Every type-name or
pointer-to-shared's referenced type that is a shared array type with definite blocksize
shall include the THREADS expression at most once in one dimension of the array type.
 In both cases, the THREADS expression shall only occur either alone or when multiplied
by an integer constant expression."

Reported by [e-mail] on 2013-03-18 05:55:03

[Former user]

> > Is there a good motivation for allowing pointers to sub-arrays?
>
> Yes.  It allows you to treat dynamically allocated memory as a multidimensional array
where the left-most dimension (which isn't part of the pointer's referenced type...)
is the THREADS-scaled dimension.

Also, completeness, as we otherwise have a legal type that we cannot declare nor name,
but can create expressions of.  This implies that there would exist (mostly indexing)
expressions that could not be manually split, because it would be impossible for programmers
to declare the necessary objects to store the temporary results.  This seems like a
gaping hole in the language to me.  Is there a good motivation for banning pointers
to sub-arrays?

Reported by [e-mail] on 2013-03-18 13:54:51

[Former user]

> Also, completeness, as we otherwise have a legal type that we cannot declare nor name,
but can create expressions of.

I agree it would be nice to support it from a completeness perspective. However, I
would also prefer to avoid muddying the spec with special cases for a corner-case type
that most users would never dream of using. Nevertheless lets try to compose some wording
and see how it looks.

Your proposed wording in comment #9 is missing a few important cases, notably array
types buried deeper in a derived type. It also suffers from the undefined term "shared
array type" which I mentioned in my earlier comment and omits the related fix to issue
94.

Here's a counter-proposal for that paragraph that fixes these issues:

"When a UPC program is translated in the dynamic THREADS environment, the following
restrictions apply: Every declaration of a shared array with definite blocksize shall
include the THREADS keyword exactly once in one dimension of the array (including through
typedefs).  Every array type that is a shared type with definite blocksize shall include
the THREADS keyword at most once in one dimension (including through typedefs).  In
both cases, the THREADS keyword shall only occur either alone or when multiplied by
an integer constant expression (as defined in [ISO/IEC00 Sec. 6.6]) with positive value."

Here I've taken advantage of the fact that the second clause specifies an "at most"
parameter to remove the somewhat cumbersome references to grammar nonterminals. "Every
array type" is of course intended to also apply to array types appearing inside a derived
type - by my reading of C99 6.2.5 this wording should be sufficient, especially with
the clarifying examples.

Reported by danbonachea on 2013-03-18 16:09:18

[Former user]

> Here's a counter-proposal for that paragraph that fixes these issues:
> ...

Sounds good to me.

Reported by [e-mail] on 2013-03-18 16:14:51

[Former user]

It also occurs to me that the subsequent paragraph concerning indefinitely-blocked arrays
is "too loose" in that it only restricts object declarations and not types. Specifically,
we're trying to also prohibit things like:

typedef shared [] int bad_array_t[THREADS];

shared [] int (*p)[THREADS];

Suggested fix:

 \np \xadded[id=DB]{15}{
-    The THREADS expression
-    shall not appear anywhere in the declarator of a shared array with 
+    The THREADS keyword
+    shall not appear in any array type that is a shared array with 
     indefinite blocksize under the {\em dynamic THREADS} environment.
     }

(leaving the annotation as issue 15 since it's the more relevant change to this text).

Reported by danbonachea on 2013-03-18 16:23:03 - Blocked on: #15

[Former user]

> It also occurs to me that the subsequent paragraph concerning indefinitely-blocked
arrays is "too loose" in that it only restricts object declarations and not types.

I'm not sure it's strictly necessary to prohibit such pointers (the requirement for
arrays is to enable implementations to use statically allocated memory to back them),
and they could potentially be useful for error-checking--compilers (and people!) can
do a lot better bounds analysis if you tell them the bounds ;)--when dynamically allocating
such arrays.  In any case, in the interest of time, I think we should open new issues
for any additional changes that are not specifically for merging existing PendingApproval
1.3 changes and defer them to 1.4.

Reported by [e-mail] on 2013-03-18 16:43:26

[Former user]

> I'm not sure it's strictly necessary to prohibit such pointers (the requirement for

> arrays is to enable implementations to use statically allocated memory to back them),


Actually, that's the runtime motivation for issue 94. 

The motivation for this issue 95 is primarily reducing the amount of symbolic state
that typecheckers need to maintain. Under static threads, all shared array bounds in
any type can always be constant-folded to a positive integer constant value. Under
dynamic threads, the idea is to provide "the next simplest thing" which is that all
shared array bounds can be folded at typechecking time to a positive integer constant
value, and optionally scaled once by THREADS on a single dimension (which can be represented
by a boolean flag on the dimension, or an index of which dimension is scaled).

If you allow arbitrary use of THREADS in shared array types under dynamic threads,
you can get cases like shown in comment #0, or even worse possibilities, eg:

typedef shared [] int bogus_array_t[THREADS*(21 + THREADS)/(THREADS * 13.7)];

This shared array type can never be instantiated under dynamic threads, but if we allow
it to be expressed then the typechecker is burdened with maintaining such ugly expressions
throughout compilation, and using them to codegen things like: sizeof(bogus_array_t)

If such types actually represented a useful feature under dynamic THREADS, then it
might be worth the implementation complexity that supporting them entails. Since nobody
seems to be arguing for them, it seems simplest and cheapest to just prohibit them.

Reported by danbonachea on 2013-03-19 04:00:45

[Former user]

Below is an updated full proposal that includes everything discussed.

Regarding indefinitely blocked types, the problem being addressed by issue 95 applies
equally to shared array types of any blocking factor - semantically there is nothing
here that is blocking-factor-specific. We just neglected to also fixup the sentence
for the indefinitely blocked case in the original proposal.

--- upc-language.tex    (revision 207)
+++ upc-language.tex    (working copy)
@@ -679,19 +679,41 @@

 {\bf Constraints}

-\np When a UPC program is translated in the {\em dynamic
-    THREADS} environment and an array with shared-qualified elements
-    is declared with definite blocksize, the THREADS expression shall
-    occur exactly once in one dimension of the array declarator
-    (including through typedefs).  Further, the THREADS expression
+\np 
+    When a UPC program is translated in the {\em dynamic THREADS} environment,
+  \xreplaced[id=DB]{95}{%
+    the following restrictions apply: 
+    Every declaration of a shared array with definite blocksize shall include the
+    THREADS keyword exactly once in one dimension of the array 
+    (including through typedefs).  
+    Every array type that is a shared type with definite blocksize
+    shall include the THREADS keyword at most once in one dimension
+    (including through typedefs).  
+    In both cases, the THREADS keyword shall only occur either alone or when
+    multiplied by an integer constant expression 
+    (as defined in [ISO/IEC00 Sec. 6.6]) with positive value.
+  }{%
+    and an array with shared-qualified elements
+    is declared with definite blocksize, the THREADS expression shall occur 
+  }%
+    exactly once in one dimension of the array declarator
+    (including through typedefs).  
+  \xreplaced[id=DB]{94}{%
+    Further, the THREADS keyword shall only occur either alone 
+    or when multiplied by an integer constant expression
+    (as defined in [ISO/IEC00 Sec. 6.6]) with positive value.
+  }{%
+    Further, the THREADS expression
     shall only occur either alone or when multiplied by an integer
-    constant expression.\footnote{In the {\em static THREADS} environment
+    constant expression.
+  }%
+    \footnote{In the {\em static THREADS} environment
     THREADS is an integer constant expression, and is therefore valid in
     all dimensions.}

 \np \xadded[id=DB]{15}{
-    The THREADS expression
-    shall not appear anywhere in the declarator of a shared array with 
+    The THREADS keyword
+    shall not appear in any array type that is a shared array with 
     indefinite blocksize under the {\em dynamic THREADS} environment.
     }

@@ -718,19 +740,31 @@
 \np EXAMPLE 1: declarations allowed in either {\em static THREADS} or
     {\em dynamic THREADS} translation environments:

+\cbstart
 \begin{verbatim}
     shared int x [10*THREADS];
+    shared int x [THREADS*(100*20)];  
     shared [] int x [10];
 \end{verbatim}
+\cbend

 \np EXAMPLE 2: declarations allowed only in {\em static THREADS} translation
     environment:

+\cbstart
 \begin{verbatim}
     shared int x [10+THREADS];
     shared [] int x [THREADS];
     shared int x [10];
+    shared int x [THREADS][4*THREADS];
+    shared int x [THREADS*THREADS];
+    shared int x [THREADS*100*20];
+    shared int (**p)[THREADS][THREADS];
+    typedef shared int (*t)[THREADS][13][THREADS];
+    shared void *p = (shared int (*)[THREADS][THREADS])q;  
 \end{verbatim}
+\cbend
+\xchangenote[id=DB]{94}{SEVEN NEW EXAMPLES ADDED ABOVE}

 \np EXAMPLE 3: declaration of a shared array

Reported by danbonachea on 2013-03-19 04:07:32

[Former user]

Updated proposal below mailed 3/20/13.
This is semantically the same as comment #16, but fixes a typesetting mistake in the
change annotations.

--- upc-language.tex    (revision 207)
+++ upc-language.tex    (working copy)
@@ -679,19 +679,38 @@

 {\bf Constraints}

-\np When a UPC program is translated in the {\em dynamic
-    THREADS} environment and an array with shared-qualified elements
-    is declared with definite blocksize, the THREADS expression shall
-    occur exactly once in one dimension of the array declarator
-    (including through typedefs).  Further, the THREADS expression
+\np 
+    When a UPC program is translated in the {\em dynamic THREADS} environment,
+  \xreplaced[id=DB]{95}{%
+    the following restrictions apply: 
+    Every declaration of a shared array with definite blocksize shall include the
+    THREADS keyword exactly once in one dimension of the array 
+    (including through typedefs).  
+    Every array type that is a shared type with definite blocksize
+    shall include the THREADS keyword at most once in one dimension
+    (including through typedefs).  
+  }{%
+    and an array with shared-qualified elements
+    is declared with definite blocksize, the THREADS expression shall occur 
+    exactly once in one dimension of the array declarator
+    (including through typedefs).  
+  }%
+  \xreplaced[id=DB]{94}{%
+    In both cases, the THREADS keyword shall only occur either alone or when
+    multiplied by an integer constant expression 
+    (as defined in [ISO/IEC00 Sec. 6.6]) with positive value.
+  }{%
+    Further, the THREADS expression
     shall only occur either alone or when multiplied by an integer
-    constant expression.\footnote{In the {\em static THREADS} environment
+    constant expression.
+  }%
+    \footnote{In the {\em static THREADS} environment
     THREADS is an integer constant expression, and is therefore valid in
     all dimensions.}

 \np \xadded[id=DB]{15}{
-    The THREADS expression
-    shall not appear anywhere in the declarator of a shared array with 
+    The THREADS keyword
+    shall not appear in any array type that is a shared array with 
     indefinite blocksize under the {\em dynamic THREADS} environment.
     }

@@ -718,19 +737,31 @@
 \np EXAMPLE 1: declarations allowed in either {\em static THREADS} or
     {\em dynamic THREADS} translation environments:

+\cbstart
 \begin{verbatim}
     shared int x [10*THREADS];
+    shared int x [THREADS*(100*20)];  
     shared [] int x [10];
 \end{verbatim}
+\cbend

 \np EXAMPLE 2: declarations allowed only in {\em static THREADS} translation
     environment:

+\cbstart
 \begin{verbatim}
     shared int x [10+THREADS];
     shared [] int x [THREADS];
     shared int x [10];
+    shared int x [THREADS][4*THREADS];
+    shared int x [THREADS*THREADS];
+    shared int x [THREADS*100*20];
+    shared int (**p)[THREADS][THREADS];
+    typedef shared int (*t)[THREADS][13][THREADS];
+    shared void *p = (shared int (*)[THREADS][THREADS])q;  
 \end{verbatim}
+\cbend
+\xchangenote[id=DB]{94}{SEVEN NEW EXAMPLES ADDED ABOVE}

 \np EXAMPLE 3: declaration of a shared array

Reported by danbonachea on 2013-03-20 15:02:59

[Former user]

I agree with intent of the proposed change, and with the spirit of closing all corner
cases even if it is difficult to come up with situations in which those corner cases
might be used in practice.

I do wonder if this proposed wording is sufficiently complete:

"Every declaration of a shared array with definite blocksize shall include the
THREADS keyword exactly once in one dimension of the array
(including through typedefs)."

Instead of "in one dimension", would "in one (and only one)" or "in exactly one" make
it clearer that the THREADS multiplier must appear once and in only one of the dimensions?
 (I realize that the current proposal is re-using language from the 1.2 specification.)

Reported by gary.funck on 2013-03-25 21:55:09

[Former user]

> Instead of "in one dimension", would "in one (and only one)" or "in exactly one" make
it clearer that the 
> THREADS multiplier must appear once and in only one of the dimensions?  

I believe the intent is clear, although I acknowledge that the wording could be misinterpreted
by a "determined quibbler". However I think if we want to be pedantic, both suggested
replacements could also be read as ambiguous since they don't constrain the "other
dimensions". eg:
   shared int x[THREADS][THREADS*THREADS]; 
"THREADS appears exactly once in one (and only one) dimension (the first). It does
not appear exactly once in any other dimension. It also appears twice in the second
dimension". 
Alternate explanation: "x is a one-dimensional shared array whose element type happens
to be an array. THREADS appears exactly once in the one dimension of x. The element
type also happens to contain THREADS."

Part of what we're running into here is that C99 does not define multi-D arrays as
a first class entity (or even as a defined term), only "arrays of arrays". We need
to specify a constraint that encompasses "all the dimensions" of a "maximally-sized"
array type, but this need does not arise in C99 and hence we lack the terminology for
that concept - this allows ambiguity if a "determined quibbler" chooses to apply the
constraint piecewise to each component of the array.

Rather than add additional sentences to clarify this obscure nitpick into a section
that is already quite "dense", I propose the minor clarification of adding a comma:

    Every declaration of a shared array with definite blocksize shall include the
    THREADS keyword exactly once, in one dimension of the array
    (including through typedefs).

I think that helps to clarify the intent somewhat, without adding lots of additional
machinery.

Is it a high priority to further clarify this?

Reported by danbonachea on 2013-04-30 18:15:18

[Former user]

In Comment #19, Dan wrote (in part):
"Rather than add additional sentences to clarify this obscure nitpick into a section
that is already quite "dense", I propose the minor clarification of adding a comma"

I agree: this minor adjustment improves the clarity of this constraint without resorting
to a lot of new verbiage.

Reported by gary.funck on 2013-04-30 19:40:05

[Former user]

Committed as SVN r214 (with added comma)

Reported by danbonachea on 2013-04-30 20:02:35 - Status changed: Fixed

[Former user]

Ratified in the 5/22 telecon.

Reported by danbonachea on 2013-08-03 03:55:36 - Status changed: Ratified