The affinity test on integer values in a upc_forall statement is undefined for negative values

[Former user]

Originally reported on Google Code with ID 59

A discussed in http://code.google.com/p/upc-specification/issues/detail?id=43#c7 ...

We saw this definitional aspect of '%' crop up on a test failure in the a GUTS 'main'
test: iteration4.

Until we fixed the compiler, the test was failing on this test, when compiled in a
static THREADS compilation environment.


#define N 10
upc_forall (i=-N; i<N; i++; i) {
  if (i >= 0)
    check(i % THREADS == MYTHREAD);
  else
    check(((i % THREADS)+THREADS)%THREADS == MYTHREAD);
}

You'll note that the index, 'i' ranges from -N .. (N-1).  You'll also note that the
test doesn't make any shared references at all, so the question of array/pointer bounds
doesn't come into play.

The bug turned out to be due to the fact that the compiler used an unsigned type when
performing the '%' operation, and further, this unsigned '%' was optimized to be performed
as a multiply by the reciprical and that gave incorrect values when i is negative.


This reference discusses the defined behavior of %.
http://bytes.com/topic/c/answers/444522-modulus-negative-operands [^]
The gist is that in C89 this was implementation-defined. In C99 they defined '/' as
always rounding towards 0, which is conventional and compatible with Fortran.

If 'affinity' is determined in terms of '%', but '%' returns a negative number, how
can upc_forall() determine affinity?

The test masks over this issue by doing something different for negative values of
'i'.

  if (i >= 0)
    check(i % THREADS == MYTHREAD);
  else
    check(((i % THREADS)+THREADS)%THREADS == MYTHREAD);

In any event, we "fixed" this test failure by insuring that the division was done using
signed arithmetic.

Proposal
--------

Based upon the above example and discussion, we propose that a semantics clause is
added that says that if an integer valued expression is used as the affinity expression
that it effect is undefined for values less than zero.

Alternatively, the specification could be changed to add a constraint that the integer
expression value shall be greater than or equal to zero, which would make the use of
negative values an error.  Such a constraint is not backwards compatible with version
1.2 of the specification, however.

Reported by gary.funck on 2012-07-02 17:57:28

[Former user]

``` Correct the subject line to add the word "negative". ```

Reported by `gary.funck` on 2012-07-02 18:06:51

[Former user]

Reported by `gary.funck` on 2012-07-02 18:07:26

[Former user]

``` Some relavent text from 6.6.2 in the current spec

Constraints: 4 The expression for affinity shall have pointer-to-shared type or integer type.

Semantics: 8 When affinity is an integer expression, the loop body of the upc forall statement is executed for each iteration in which the value of MYTHREAD equals the value affinity mod THREADS.

Note that Constraint clause #4 says "integer" which is unambiguously a signed type. So, as Gary says this proposed change would be an incompatible one (though with admittedly small real-world impact in my estimation).

Note the use of the "mod" (not "%") in Semantic clause #8. Since "mod" was given a specific definition in 6.4.2 with respect to the specification of shared pointer arithmetic, one is left to wonder if the same definition was intended here. I suspect that it was. If so, then there is a clear definition of the behavior for negative affinity expression.

So...

COUNTER proposal:

Append to Semantic clause #8 of Section 6.6.2: "where the \texttt{mod} operator is defined as in Section 6.4.2"

```

Reported by `[e-mail]` on 2012-07-02 18:53:38

[Former user]

``` Paul's suggested resolution is semantically cleaner, but I'm worried about the potential impact on current and future loop optimizations if we require well-defined semantics for this dirty special case. Specifically, we don't want to burden a loop optimizer with PROVING the affinity expression returns a non-zero result before it can apply the straightforward arithmetic instructions for the expected common case.

This scenario is notably somewhat different from pointer arithmetic, where dealing with negative values is commonplace and should have well-defined behavior. It seems like a very strange programming practice to use an affinity expression that evaluates to a negative value, but a programmer who deliberately does this probably has a very specific behavior in mind they want. So rather than trying to second-guess what that might be, Gary's proposal forces them to resolve the ambiguity themselves (ie make the programmer apply the mathematical expression that maps it to a positive number so that % always results in a valid thread id). It also has the benefit of not rendering existing loop optimizer implementations non-compliant in ways that might be devilishly tricky to fix (for a very minimal payoff). The downside is this may break some small number of existing codes that intentionally use a negative affinity expression (does anyone have reason to believe this is a common practice?), but the "fix" that would be required is small and localized (and easily detectable if the compiler has a debugging feature to report this).

So I think I agree with Gary - make behavior undefined if the affinity expression returns a negative value.

```

Reported by `danbonachea` on 2012-08-17 08:35:38

[Former user]

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

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

[Former user]

``` This issue seems easy to fix.. if we can agree on which semantic we want.

Bump it back to new for more discussion.

I'd especially like to hear opinions from implementers of loop optimizations. ```

Reported by `danbonachea` on 2012-09-26 18:53:40 - Status changed: `New`

[Former user]

``` Based on the discussion on the 9/26/2012 telecon, we seem to have consensus that affinity expressions that evaluate to a negative value should have undefined behavior.

This resolution allows implementations to issue a helpful error message for this case (which probably represents a programming mistake). In the rare cases where such practice was intentional, it places the burden on the programmer to explicitly map the negative value to a positive value using their preferred algorithm, which seems like a Good Thing.

```

Reported by `danbonachea` on 2012-09-26 22:35:55 - Status changed: `Accepted` - Labels added: Consensus-High - Labels removed: Consensus-Low

[Former user]

``` Would it be useful to constrain "non-negative" (not just positive) integer to be within the range 0..(THREADS-1)?

```

Reported by `gary.funck` on 2012-09-26 22:43:40

[Former user]

``` Official change proposal mailed to the lists 9/26/2012: Proposed Change: ------------------------- --- upc-language.tex (revision 143) +++ upc-language.tex (working copy) @@ -964,6 +974,7 @@ \np When {\em affinity} is an integer expression, the loop body of the {\tt upc\_forall} statement is executed for each iteration in which the value of {\tt MYTHREAD} equals the value {\em affinity }{\tt mod THREADS}. + \xadded[id=DB]{59}{If the value of {\em affinity} is negative, behavior is undefined.}

\np When {\em affinity} is {\tt continue} or not specified, each loop body of the {\tt upc\_forall} statement is performed by every thread and ```

Reported by `danbonachea` on 2012-09-26 22:46:41 - Status changed: `PendingApproval`

[Former user]

```

Would it be useful to constrain "non-negative" (not just positive) integer to be within

the range 0..(THREADS-1)?

I think that would be a significant departure from the "spirit" of an integer affinity expression, which definitely is supposed to include a mod operation for positive values exceeding THREADS. Removing that seems far more likely to break existing codes.

The point of this issue was to resolve the ambiguity of mod on negative values (which we've decided to resolve by passing the responsibility on to the user), not to remove the mod entirely.

```

Reported by `danbonachea` on 2012-09-26 22:50:08

[Former user]

``` Gary asked:

Would it be useful to constrain "non-negative" (not just positive) integer to be

within the range 0..(THREADS-1)?

That restriction is out of the question in my opinion, as it breaks the "classic" example: upc_forall (i=0; i<SIZE; ++i; i) { a[i] = whatever; }

Even if it didn't break a huge fraction of existing codes, I expect an optimizer to be able to recognize that idiom easily, where an explicit "i % THREADS" in the affinity expression would be "harder" for a compiler to match to the "a[i]" in the loop body. ```

Reported by `[e-mail]` on 2012-09-26 22:52:47

[Former user]

these issues have all reached the end of their 4-week comment period 
and were accepted into the working draft at the 10/31 telecon.
Committed SVN r181

Reported by danbonachea on 2012-10-31 20:49:32 - Status changed: Ratified