[OpenMP] Stable sort Privates to remove non-deterministic ordering

[mgrang]

Summary

This fixes the following failures uncovered by D39245:

Clang :: OpenMP/task_firstprivate_codegen.cpp
Clang :: OpenMP/task_private_codegen.cpp
Clang :: OpenMP/taskloop_firstprivate_codegen.cpp
Clang :: OpenMP/taskloop_lastprivate_codegen.cpp
Clang :: OpenMP/taskloop_private_codegen.cpp
Clang :: OpenMP/taskloop_simd_firstprivate_codegen.cpp
Clang :: OpenMP/taskloop_simd_lastprivate_codegen.cpp
Clang :: OpenMP/taskloop_simd_private_codegen.cpp

[mgrang]

Although this patches fixes the above unit test failures, the generated code is very different from the one that the tests expect. As a result, these tests need to be adjusted. Could the reviewers please comment/suggest on whether it is ok to fix the tests as a result of this change?

The other way of obtaining deterministic ordering for privates with the same alignment is to use an index for each item inserted into Privates and use it as a tie-breaker. But even in that case the generated code is quite different and tests still need to be adjusted.

[rjmccall]

In D39947#922870, @mgrang wrote:

Although this patches fixes the above unit test failures, the generated code is very different from the one that the tests expect. As a result, these tests need to be adjusted. Could the reviewers please comment/suggest on whether it is ok to fix the tests as a result of this change?

The other way of obtaining deterministic ordering for privates with the same alignment is to use an index for each item inserted into Privates and use it as a tie-breaker. But even in that case the generated code is quite different and tests still need to be adjusted.

Fixing the tests may be acceptable. Can you give an example of the difference between the old and new test outputs?

[mgrang]

In D39947#922889, @rjmccall wrote:

In D39947#922870, @mgrang wrote:

Although this patches fixes the above unit test failures, the generated code is very different from the one that the tests expect. As a result, these tests need to be adjusted. Could the reviewers please comment/suggest on whether it is ok to fix the tests as a result of this change?

The other way of obtaining deterministic ordering for privates with the same alignment is to use an index for each item inserted into Privates and use it as a tie-breaker. But even in that case the generated code is quite different and tests still need to be adjusted.

Fixing the tests may be acceptable. Can you give an example of the difference between the old and new test outputs?

Please see https://www.diffchecker.com/7V2XFbk4 for the difference in output for the following test before and after my change:

clang -cc1 -internal-isystem <MYDIR>/build/llvm/lib/clang/6.0.0/include -nostdsysteminc -verify -fopenmp -x c++ -triple x86_64-apple-darwin10 -emit-llvm <MYDIR>/src/llvm/tools/clang/test/OpenMP/task_firstprivate_codegen.cpp -o -

[rjmccall]

In D39947#922922, @mgrang wrote:

In D39947#922889, @rjmccall wrote:

In D39947#922870, @mgrang wrote:

Although this patches fixes the above unit test failures, the generated code is very different from the one that the tests expect. As a result, these tests need to be adjusted. Could the reviewers please comment/suggest on whether it is ok to fix the tests as a result of this change?

The other way of obtaining deterministic ordering for privates with the same alignment is to use an index for each item inserted into Privates and use it as a tie-breaker. But even in that case the generated code is quite different and tests still need to be adjusted.

Fixing the tests may be acceptable. Can you give an example of the difference between the old and new test outputs?

Please see https://www.diffchecker.com/7V2XFbk4 for the difference in output for the following test before and after my change:

clang -cc1 -internal-isystem <MYDIR>/build/llvm/lib/clang/6.0.0/include -nostdsysteminc -verify -fopenmp -x c++ -triple x86_64-apple-darwin10 -emit-llvm <MYDIR>/src/llvm/tools/clang/test/OpenMP/task_firstprivate_codegen.cpp -o -

Does your diff have shuffling enabled on both sides? Neither layout for %struct..kmp_privates.t.3 seems to match the test's match for PRIVATES_TMAIN_TY, so I'm not completely sure which is supposed to be which. Assuming that the right diff is with your patch, something seems quite wrong, because the capture for t_var is being sorted to the end, which is producing a really terrible layout.

I think you might actually have accidentally inverted the order: a qsort comparator is supposed to return positive if `LHS > RHS, so the fact that it's returning 1 when P1->first < P2->first` means that it's actually a reversed comparison. Would you mind fixing that and then letting us know what test changes remain?

Cou

[mgrang]

Fixed the sorting order for stable_sort.

[mgrang]

In D39947#922987, @rjmccall wrote:

In D39947#922922, @mgrang wrote:

In D39947#922889, @rjmccall wrote:

In D39947#922870, @mgrang wrote:

Although this patches fixes the above unit test failures, the generated code is very different from the one that the tests expect. As a result, these tests need to be adjusted. Could the reviewers please comment/suggest on whether it is ok to fix the tests as a result of this change?

The other way of obtaining deterministic ordering for privates with the same alignment is to use an index for each item inserted into Privates and use it as a tie-breaker. But even in that case the generated code is quite different and tests still need to be adjusted.

Fixing the tests may be acceptable. Can you give an example of the difference between the old and new test outputs?

Please see https://www.diffchecker.com/7V2XFbk4 for the difference in output for the following test before and after my change:

clang -cc1 -internal-isystem <MYDIR>/build/llvm/lib/clang/6.0.0/include -nostdsysteminc -verify -fopenmp -x c++ -triple x86_64-apple-darwin10 -emit-llvm <MYDIR>/src/llvm/tools/clang/test/OpenMP/task_firstprivate_codegen.cpp -o -

Does your diff have shuffling enabled on both sides? Neither layout for %struct..kmp_privates.t.3 seems to match the test's match for PRIVATES_TMAIN_TY, so I'm not completely sure which is supposed to be which. Assuming that the right diff is with your patch, something seems quite wrong, because the capture for t_var is being sorted to the end, which is producing a really terrible layout.

I think you might actually have accidentally inverted the order: a qsort comparator is supposed to return positive if `LHS > RHS, so the fact that it's returning 1 when P1->first < P2->first` means that it's actually a reversed comparison. Would you mind fixing that and then letting us know what test changes remain?

Cou

You are correct Cou. My sorting order was indeed reversed. After fixing the order (with stable_sort) I see that all of the above failing tests pass and generate the desired output. Apologies for the false alarm.

[mgrang]

Ping for reviews please.

[ABataev]

LG

[rjmccall]

Yes, LGTM.

cfe/trunk/lib/CodeGen/CGOpenMPRuntime.cpp

auto RefLoadLVal = CGF.EmitLoadOfPointerLValue(
         RefLVal.getAddress(), RefLVal.getType()->castAs<PointerType>());
     CGF.EmitStoreOfScalar(FieldLVal.getPointer(), RefLoadLVal);
     ++Counter;
   }
   CGF.FinishFunction();
   return TaskPrivatesMap;
 }
 
-static int array_pod_sort_comparator(const PrivateDataTy *P1,
-                                     const PrivateDataTy *P2) {
-  return P1->first < P2->first ? 1 : (P2->first < P1->first ? -1 : 0);
+static bool stable_sort_comparator(const PrivateDataTy P1,
+                                   const PrivateDataTy P2) {
+  return P1.first > P2.first;
 }
 
 /// Emit initialization for private variables in task-based directives.
 static void emitPrivatesInit(CodeGenFunction &CGF,
                              const OMPExecutableDirective &D,
                              Address KmpTaskSharedsPtr, LValue TDBase,
                              const RecordDecl *KmpTaskTWithPrivatesQTyRD,
                              QualType SharedsTy, QualType SharedsPtrTy,
CGOpenMPRuntime::emitTaskInit(CodeGenFunction &CGF, SourceLocation Loc,
   for (auto *E : Data.LastprivateVars) {
     auto *VD = cast<VarDecl>(cast<DeclRefExpr>(E)->getDecl());
     Privates.push_back(std::make_pair(
         C.getDeclAlign(VD),
         PrivateHelpersTy(VD, cast<VarDecl>(cast<DeclRefExpr>(*I)->getDecl()),
                          /*PrivateElemInit=*/nullptr)));
     ++I;
   }
-  llvm::array_pod_sort(Privates.begin(), Privates.end(),
-                       array_pod_sort_comparator);
+  std::stable_sort(Privates.begin(), Privates.end(), stable_sort_comparator);
   auto KmpInt32Ty = C.getIntTypeForBitwidth(/*DestWidth=*/32, /*Signed=*/1);
   // Build type kmp_routine_entry_t (if not built yet).
   emitKmpRoutineEntryT(KmpInt32Ty);
   // Build type kmp_task_t (if not built yet).
   if (isOpenMPTaskLoopDirective(D.getDirectiveKind())) {
     if (SavedKmpTaskloopTQTy.isNull()) {
       SavedKmpTaskloopTQTy = C.getRecordType(createKmpTaskTRecordDecl(
           CGM, D.getDirectiveKind(), KmpInt32Ty, KmpRoutineEntryPtrQTy));