[OpenMP][WIP] atomic update only evaluate once for expression having side effect

[cchen]

Summary

This patch is for pointing out that we might need to check if the
expression in atomic update having any side effect. In the past we
always only evaluate an expression once, for example:

int cnt = 0;
int foo() {
  return ++cnt;
}

void bar() {
  int iarr[100];
#pragma omp atomic capture
  iarr[foo(), foo(), 0]  = iarr[foo(), foo(), 0] + 1;
}

For now, the result of cnt is 2, however, we probably want cnt to be 4
or we might want to tell user that we only evaluate the expression once
as diagnosis message.

Actually, atomic capture have the exact same issue, but the purpose of
this patch to expose the issue. After the discussion, I might send another
patch to fix the issue.

[ABataev]

It is against the standard, I assume. According to standard, During the execution of an atomic region, multiple syntactic occurrences of x must designate the same storage location.. In your case, this is not so. I assume it would be better to implement the diagnostic here that the code is not OpenMP compliant.

[jdoerfert]

• For forms that allow multiple occurrences of x, the number of times that x is evaluated is unspecified.

x here is iarr[foo(), foo(), 0], if I'm not mistaken. Assuming not, any multiple of 2 is a fine amount of evaluations for foo.

I'd vote for a warning here.

[cchen]

This comment was removed by cchen.

[cchen]

Oops, accidentally remove my own comment. I'm not sure why iarr[foo(), foo(), 0] violate the rule since it will be evaluated as iarr[0], and the counter foo() modified is also in the same location for both left hand side and right hand side.

[jdoerfert]

In D71225#1776105, @cchen wrote:

Oops, accidentally remove my own comment. I'm not sure why iarr[foo(), foo(), 0] violate the rule since it will be evaluated as iarr[0], and the counter foo() modified is also in the same location for both left hand side and right hand side.

It's not a violation but it taps into the unspecified behavior, which in combination with side effects seems to be worth a warning.

So my reasoning is:

x := iarr[foo(), foo(), 0]

which is fine on its own. Using it in the atomic update of the form,

x = x + 1

also fine.

However, the standard says the number of times x is evaluated is unspecified.
Thus, transforming the above to

x += 1

should be valid. So should be,

t = &x; *t = *t + 1

and even

x = (x, x, x, x+1)

[cchen]

@jdoerfert , thanks for your explanation, it's really clear and helpful. I'll add a warning message in another patch.

[ABataev]

In D71225#1776113, @jdoerfert wrote:

In D71225#1776105, @cchen wrote:

Oops, accidentally remove my own comment. I'm not sure why iarr[foo(), foo(), 0] violate the rule since it will be evaluated as iarr[0], and the counter foo() modified is also in the same location for both left hand side and right hand side.

It's not a violation but it taps into the unspecified behavior, which in combination with side effects seems to be worth a warning.

So my reasoning is:

x := iarr[foo(), foo(), 0]

which is fine on its own. Using it in the atomic update of the form,

x = x + 1

also fine.

However, the standard says the number of times x is evaluated is unspecified.
Thus, transforming the above to

x += 1

should be valid. So should be,

t = &x; *t = *t + 1

and even

x = (x, x, x, x+1)

Agree, missed that he used commas instead of array expressions.

clang/lib/CodeGen/CGStmtOpenMP.cpp

if (!Res.first) {
     } else {
       // Perform compare-and-swap procedure.
       EmitAtomicUpdate(X, AO, CommonGen, X.getType().isVolatileQualified());
     }
   }
   return Res;
 }
 
+static void traverseBinOp(CodeGenFunction &CGF, const Expr *E) {
+  if (auto *BinOp = dyn_cast<BinaryOperator>(E)) {
+    traverseBinOp(CGF, BinOp->getLHS());
+    traverseBinOp(CGF, BinOp->getRHS());
+  } else {
+    if (auto *Call = dyn_cast<CallExpr>(E)) {
+      CGF.EmitCallExpr(Call);
+    }
+  }
+}
+
+static void handleArraySubscriptSideEffect(CodeGenFunction &CGF,
+                                           const Expr *X) {
+  // If X is a ArraySubscript and the expression has side effect, then we'll
+  // have wrong result since we only evaluate the expression once.
+  if (X->getStmtClass() == Expr::ArraySubscriptExprClass) {
+    auto E = cast<ArraySubscriptExpr>(X);
+    if (E->getLHS() != E->getIdx()) {
+      assert(E->getRHS() == E->getIdx() && "index was neither LHS nor RHS");
+      traverseBinOp(CGF, E->getIdx());
+    }
+  }
+}
+
 static void emitOMPAtomicUpdateExpr(CodeGenFunction &CGF, bool IsSeqCst,
                                     const Expr *X, const Expr *E,
                                     const Expr *UE, bool IsXLHSInRHSPart,
                                     SourceLocation Loc) {
   assert(isa<BinaryOperator>(UE->IgnoreImpCasts()) &&
          "Update expr in 'atomic update' must be a binary operator.");
   const auto *BOUE = cast<BinaryOperator>(UE->IgnoreImpCasts());
   // Update expressions are allowed to have the following forms:
   // x binop= expr; -> xrval + expr;
   // x++, ++x -> xrval + 1;
   // x--, --x -> xrval - 1;
   // x = x binop expr; -> xrval binop expr
   // x = expr Op x; - > expr binop xrval;
   assert(X->isLValue() && "X of 'omp atomic update' is not lvalue");
+  handleArraySubscriptSideEffect(CGF, X);
   LValue XLValue = CGF.EmitLValue(X);
   RValue ExprRValue = CGF.EmitAnyExpr(E);
   llvm::AtomicOrdering AO = IsSeqCst
                                 ? llvm::AtomicOrdering::SequentiallyConsistent
                                 : llvm::AtomicOrdering::Monotonic;
   const auto *LHS = cast<OpaqueValueExpr>(BOUE->getLHS()->IgnoreImpCasts());
   const auto *RHS = cast<OpaqueValueExpr>(BOUE->getRHS()->IgnoreImpCasts());
   const OpaqueValueExpr *XRValExpr = IsXLHSInRHSPart ? LHS : RHS;

clang/test/OpenMP/atomic_update_codegen.cpp

 long long llv, llx;
 unsigned long long ullv, ullx;
 float fv, fx;
 double dv, dx;
 long double ldv, ldx;
 _Complex int civ, cix;
 _Complex float cfv, cfx;
 _Complex double cdv, cdx;
+int iarr[100];
+int cnt = 0;
+
+int foo() {
+  return cnt++;
+}
 
 typedef int int4 __attribute__((__vector_size__(16)));
 int4 int4x;
 
 struct BitFields {
   int : 32;
   int a : 31;
 } bfx;

 // CHECK: [[OLD_VAL:%.+]] = call i32 @llvm.read_register.i32([[REG:metadata ![0-9]+]])
 // CHECK: [[X_RVAL:%.+]] = sitofp i32 [[OLD_VAL]] to double
 // CHECK: [[DIV:%.+]] = fdiv double [[EXPR]], [[X_RVAL]]
 // CHECK: [[NEW_VAL:%.+]] = fptosi double [[DIV]] to i32
 // CHECK: call void @llvm.write_register.i32([[REG]], i32 [[NEW_VAL]])
 // CHECK: call{{.*}} @__kmpc_flush(
 #pragma omp atomic seq_cst
   rix = dv / rix;
+
+#pragma omp atomic update
+  iarr[foo(), 0]  = iarr[foo(), 0] + 1;
+// CHECK: call i32 @foo()
+// CHECK: call i32 @foo()
+// CHECK: [[ZERO:%.+]] = atomicrmw add i32* [[ARRAY_IDX:.+]], i32 1 monotonic
+
+#pragma omp atomic update
+  iarr[foo(), foo(), 0]  = iarr[foo(), foo(), 0] + 1;
+// CHECK-COUNT-4: call i32 @foo()
+// CHECK: [[ZERO:%.+]] = atomicrmw add i32* [[ARRAY_IDX:.+]], i32 1 monotonic
   return 0;
 }
 
 #endif