[PATCH] D39947: [OpenMP] Stable sort Privates to remove non-deterministic ordering
This revision was automatically updated to reflect the committed changes. Closed by commit rL319222: [OpenMP] Stable sort Privates to remove non-deterministic ordering (authored by mgrang). Changed prior to commit: https://reviews.llvm.org/D39947?vs=122751=124622#toc Repository: rL LLVM https://reviews.llvm.org/D39947 Files: cfe/trunk/lib/CodeGen/CGOpenMPRuntime.cpp Index: cfe/trunk/lib/CodeGen/CGOpenMPRuntime.cpp === --- cfe/trunk/lib/CodeGen/CGOpenMPRuntime.cpp +++ cfe/trunk/lib/CodeGen/CGOpenMPRuntime.cpp @@ -4056,9 +4056,9 @@ 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. @@ -4286,8 +4286,7 @@ /*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); Index: cfe/trunk/lib/CodeGen/CGOpenMPRuntime.cpp === --- cfe/trunk/lib/CodeGen/CGOpenMPRuntime.cpp +++ cfe/trunk/lib/CodeGen/CGOpenMPRuntime.cpp @@ -4056,9 +4056,9 @@ 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. @@ -4286,8 +4286,7 @@ /*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); ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D39947: [OpenMP] Stable sort Privates to remove non-deterministic ordering
rjmccall accepted this revision. rjmccall added a comment. Yes, LGTM. Repository: rL LLVM https://reviews.llvm.org/D39947 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D39947: [OpenMP] Stable sort Privates to remove non-deterministic ordering
ABataev accepted this revision. ABataev added a comment. This revision is now accepted and ready to land. LG Repository: rL LLVM https://reviews.llvm.org/D39947 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D39947: [OpenMP] Stable sort Privates to remove non-deterministic ordering
mgrang added a comment. Ping for reviews please. Repository: rL LLVM https://reviews.llvm.org/D39947 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D39947: [OpenMP] Stable sort Privates to remove non-deterministic ordering
mgrang added a comment. In https://reviews.llvm.org/D39947#922987, @rjmccall wrote: > In https://reviews.llvm.org/D39947#922922, @mgrang wrote: > > > In https://reviews.llvm.org/D39947#922889, @rjmccall wrote: > > > > > In https://reviews.llvm.org/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 /build/llvm/lib/clang/6.0.0/include > > -nostdsysteminc -verify -fopenmp -x c++ -triple x86_64-apple-darwin10 > > -emit-llvm > > /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. Repository: rL LLVM https://reviews.llvm.org/D39947 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D39947: [OpenMP] Stable sort Privates to remove non-deterministic ordering
mgrang updated this revision to Diff 122751. mgrang added a comment. Fixed the sorting order for stable_sort. Repository: rL LLVM https://reviews.llvm.org/D39947 Files: lib/CodeGen/CGOpenMPRuntime.cpp Index: lib/CodeGen/CGOpenMPRuntime.cpp === --- lib/CodeGen/CGOpenMPRuntime.cpp +++ lib/CodeGen/CGOpenMPRuntime.cpp @@ -4048,9 +4048,9 @@ 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. @@ -4278,8 +4278,7 @@ /*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); Index: lib/CodeGen/CGOpenMPRuntime.cpp === --- lib/CodeGen/CGOpenMPRuntime.cpp +++ lib/CodeGen/CGOpenMPRuntime.cpp @@ -4048,9 +4048,9 @@ 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. @@ -4278,8 +4278,7 @@ /*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); ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D39947: [OpenMP] Stable sort Privates to remove non-deterministic ordering
rjmccall added a comment. In https://reviews.llvm.org/D39947#922922, @mgrang wrote: > In https://reviews.llvm.org/D39947#922889, @rjmccall wrote: > > > In https://reviews.llvm.org/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 /build/llvm/lib/clang/6.0.0/include > -nostdsysteminc -verify -fopenmp -x c++ -triple x86_64-apple-darwin10 > -emit-llvm > /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 https://reviews.llvm.org/D39947 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D39947: [OpenMP] Stable sort Privates to remove non-deterministic ordering
mgrang added a comment. In https://reviews.llvm.org/D39947#922889, @rjmccall wrote: > In https://reviews.llvm.org/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 /build/llvm/lib/clang/6.0.0/include -nostdsysteminc -verify -fopenmp -x c++ -triple x86_64-apple-darwin10 -emit-llvm /src/llvm/tools/clang/test/OpenMP/task_firstprivate_codegen.cpp -o - https://reviews.llvm.org/D39947 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D39947: [OpenMP] Stable sort Privates to remove non-deterministic ordering
rjmccall added a comment. In https://reviews.llvm.org/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? https://reviews.llvm.org/D39947 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D39947: [OpenMP] Stable sort Privates to remove non-deterministic ordering
mgrang added a comment. 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. https://reviews.llvm.org/D39947 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D39947: [OpenMP] Stable sort Privates to remove non-deterministic ordering
mgrang created this revision. mgrang added a project: clang. This fixes the following failures uncovered by https://reviews.llvm.org/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 https://reviews.llvm.org/D39947 Files: lib/CodeGen/CGOpenMPRuntime.cpp Index: lib/CodeGen/CGOpenMPRuntime.cpp === --- lib/CodeGen/CGOpenMPRuntime.cpp +++ lib/CodeGen/CGOpenMPRuntime.cpp @@ -4048,9 +4048,9 @@ 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. @@ -4278,8 +4278,7 @@ /*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); Index: lib/CodeGen/CGOpenMPRuntime.cpp === --- lib/CodeGen/CGOpenMPRuntime.cpp +++ lib/CodeGen/CGOpenMPRuntime.cpp @@ -4048,9 +4048,9 @@ 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. @@ -4278,8 +4278,7 @@ /*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); ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits