Page MenuHomePhabricator

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

Authored by mgrang on Nov 12 2017, 12:13 PM.

Details

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

Diff Detail

Repository
rL LLVM

Event Timeline

mgrang created this revision.Nov 12 2017, 12:13 PM
mgrang added a comment.EditedNov 12 2017, 12:17 PM

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 edited edge metadata.Nov 12 2017, 1:51 PM

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 added a comment.EditedNov 12 2017, 4:23 PM

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 -

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 updated this revision to Diff 122751.Nov 13 2017, 5:08 PM

Fixed the sorting order for stable_sort.

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.

Ping for reviews please.

This revision is now accepted and ready to land.Nov 20 2017, 11:15 AM
rjmccall accepted this revision.Nov 20 2017, 2:44 PM

Yes, LGTM.

This revision was automatically updated to reflect the committed changes.