#pragma omp atomic changes

[jakub]

What was the reason to add the x = expr binop x; form to #pragma omp atomic update and v = x = expr binop x; or { v = x; x = expr binop x; } or { x = expr binop x; v = x; } forms to #pragma omp atomic capture? I think their presence will make it very difficult to parse this properly. Both to be able to find out early during parsing if we are looking at expr or at x, and also because parsing of the x = expr binop x; form means after parsing any binary operator it can either be followed by further part of expr, or by x. x doesn't have to be just a variable name, or can be
#pragma omp atomic update
x[i] = x[j] * x[k] + x[i];
where if j != i and k != i, it would be valid, or
extern int bar (int), *foo (int);
#pragma omp atomic update
foo (bar (5) + 6)[7] = foo (bar (5) + 5)[7] * foo (bar (6) + 5)[7] + foo (bar (5) + 6)[7];
iff foo (bar (5) + 6) always returns the same pointer for all these calls, different from foo (bar (5) + 5) or foo (bar (6) + 5).

So far, we could in GCC get away without actually doing any analysis on matching x in the expression (with the exception where it is a simple variable, where we'd error if there was a mismatch). But we'd let say
void
baz (int *x, int i, int j, int k)
{
#pragma omp atomic update
x[i] = x[j] + x[k];
}
with say baz (x, 5, 5, 6); caller to compile, assuming x[i] and x[j] is the same thing and expr is x[k], and user ensured i = j and k != i.
If the x = expr binop x; forms are allowed, then this isn't possible anymore. What should be then used to find out if we are parsing x vs. expr? Shall we require exactly same spelling tokens, or parse x as unary expression (as we do in C front end right now), fold it and compare? Is
#pragma omp atomic update
x[5 + 6] = x[6 + 5] + x[7 + 5];
supposed to be valid (where x is x[5 + 6] and x[6 + 5] and expr is x[7 + 5])?

[jakub]

Related to viewtopic.php?t=1199

[sandoval]

What was the reason to add the x = expr binop x; form to #pragma omp atomic update and v = x = expr binop x; or { v = x; x = expr binop x; } or { x = expr binop x; v = x; } forms to #pragma omp atomic capture? I think their presence will make it very difficult to parse this properly.

I agree that it does make parsing more difficult, but I don't think it's too unreasonable. I can't speak as to why the change was made (as I wasn't involved in the decision), but I've implemented this form of atomic statements for the Cray compiler and I can offer my insight. This topic recently came up on the openmp mailing list, so I'll re-post my comments here and then comment on your specific examples.

My interpretation of the atomic directive is that all occurrences of "x" in the allowed forms must be lexically identical.  Any scalar l-value is acceptable, which includes function calls.  If "x" is a function call, then all occurrences of "x" must be the same function call with the same arguments.  It is the user's responsibility to ensure that "multiple syntactic occurrences of x must designate the same storage location" -- that is, the function must return the same l-value for all occurrences of "x".  Also, "x" must not match to or occur in the "v" or "expr" part of the atomic statement (e.g., "foo() = foo() + foo()" is not legal).  Finally, "the number of times that x is evaluated is unspecified", so an implementation may remove extra function calls.

Using this interpretation, the following example is not legal because "x" is not lexically identical in all occurrences (assuming either foo() or bar() returns a reference to x):

  int x;
  int &foo();
  int &bar();

  #pragma omp atomic update
  x = foo() + bar();

However, the following example would be legal:

  #pragma omp atomic update
  foo() = foo() + bar();

More generally, the following is legal:

  int &foo(int);

  #pragma omp atomic update
  foo(0) = foo(0) + foo(1)

But the compiler is free to rewrite it as follows:

  int &t1 = foo(0)
  int &t2 = foo(1)
  #pragma omp atomic update
  t1 = t1 + t2

It seems reasonable for a compiler to generate an error if it can prove (e.g., through inlining) that an atomic statement containing function calls is illegal:
 
  int x;
  int &foo(int i) { return x; }

  #pragma omp atomic update
  foo(0) = foo(0) + foo(1)

Finally, requiring strict lexical equivalence would prohibit the following example, although it seems reasonable for an implementation to accept it:

  int *x;
  #pragma omp atomic update
  *x = x[0] + 1;

Both to be able to find out early during parsing if we are looking at expr or at x, and also because parsing of the x = expr binop x; form means after parsing any binary operator it can either be followed by further part of expr, or by x. x doesn't have to be just a variable name, or can be
#pragma omp atomic update
x[i] = x[j] * x[k] + x[i];
where if j != i and k != i, it would be valid

Yes, I agree that this is legal as long j != i and k != i. If the compiler can prove statically that the constraints are violated (e.g., through constant propagation), then it would be free to reject the construct as an error.

or
extern int bar (int), *foo (int);
#pragma omp atomic update
foo (bar (5) + 6)[7] = foo (bar (5) + 5)[7] * foo (bar (6) + 5)[7] + foo (bar (5) + 6)[7];
iff foo (bar (5) + 6) always returns the same pointer for all these calls, different from foo (bar (5) + 5) or foo (bar (6) + 5).

In a strict static sense, the above appears legal since it is of the form "x = expr + x" where "x" is "foo (bar(5) + 6)[7]" (and "x" does not occur inside of "expr"). It is the user's responsibility to ensure that this code conforms at runtime (i.e., "expr" does not reference "x" and both occurences of "x" are identical). It is certainly easy to implement foo or bar such that this example is illegal at runtime -- in that case, the program is non-conforming.

So far, we could in GCC get away without actually doing any analysis on matching x in the expression (with the exception where it is a simple variable, where we'd error if there was a mismatch). But we'd let say
void
baz (int *x, int i, int j, int k)
{
#pragma omp atomic update
x[i] = x[j] + x[k];
}
with say baz (x, 5, 5, 6); caller to compile, assuming x[i] and x[j] is the same thing and expr is x[k], and user ensured i = j and k != i.

I believe the above example is illegal, because the "x" on the left-hand side does not appear (lexically) on the right-hand side. Instead, it could be "x[i] = x[i] + x[k]" or "x[i] = x[j] + x[i]", with the constraint that i != x and i != j.

If the x = expr binop x; forms are allowed, then this isn't possible anymore. What should be then used to find out if we are parsing x vs. expr? Shall we require exactly same spelling tokens, or parse x as unary expression (as we do in C front end right now), fold it and compare? Is
#pragma omp atomic update
x[5 + 6] = x[6 + 5] + x[7 + 5];
supposed to be valid (where x is x[5 + 6] and x[6 + 5] and expr is x[7 + 5])?

In a strict sense, I'd argue that the above is statment is illegal because "x" on the left-hand side does not appear on the right-hand side. But, as you say, you could fold the constants and get "x[11] = x[11] + x[12]", which would be legal.

So, this question remains: if a statement should be rejected in a strict interpretation, may an implementation still choose to accept it?

[MarkB]

So, this question remains: if a statement should be rejected in a strict interpretation, may an implementation still choose to accept it?

I think this is just a quality-of-implementation issue: an implementation can legally do anything it likes with non-conforming code.

[ftinetti]

Hi Mark,

I think this is just a quality-of-implementation issue: an implementation can legally do anything it likes with non-conforming code.

Is this association of "quality-of-implementation" with "non-conforming code" defined or suggested in the OpenMP spec.? I always thought that there is nothing to say about non-conforming code, it is just "out of the scope" of everything. Actually, If I would associate something to non-conforming code it would be "non-portable" or even "erroneous/buggy" code, don't you?

Fernando.

[MarkB]

Hi Fernando,

s this association of "quality-of-implementation" with "non-conforming code" defined or suggested in the OpenMP spec.? I always thought that there is nothing to say about non-conforming code, it is just "out of the scope" of everything. Actually, If I would associate something to non-conforming code it would be "non-portable" or even "erroneous/buggy" code, don't you?

You are right: the spec says (as a note to the Glossary definition of compliant implementation) "A compliant implementation may exhibit unspecified behavior when compiling or executing a non-conforming program."

All I am saying is that a compliant implementation can, in principle, do anything when it encounters non-conforming code, without breaking the standard. However some forms of unspecified behaviour (such as implementing an extension or throwing a sensible error message) can be considered a better quality implementation than others (such as failing in silent and unpredictable ways, or painting your screen blue, for example!)

[ftinetti]

Hi Mark,

All I am saying is that a compliant implementation can, in principle, do anything when it encounters non-conforming code, without breaking the standard. However some forms of unspecified behaviour (such as implementing an extension or throwing a sensible error message) can be considered a better quality implementation than others (such as failing in silent and unpredictable ways, or painting your screen blue, for example!)

I see, I was trying to understand your post along the lines of compilers' extension but I wanted to check, thanks,

Fernando.

[jakub]

I agree that it does make parsing more difficult, but I don't think it's too unreasonable.

Ok, I got the parsing done now (for C++ and C so far), especially for C the error recovery isn't best (we don't have tentative parsing for C frontend), but I hope we accept all the valid OpenMP 4.0 atomics now.