[ADT] Shuffle containers before sorting to uncover non-deterministic behavior

[mgrang]

Summary

std::sort and array_pod_sort both use non-stable sorting algorithms.
This means that the relative order of elements with the same key is
undefined. This patch is an attempt to uncover such scenarios by
randomly shuffling all containers before sorting, if EXPENSIVE_CHECKS
is enabled.

Here's the bugzilla for this: https://bugs.llvm.org/show_bug.cgi?id=35135

[mgrang]

I see the following tests fail if we shuffle before sorting:

Clang :: Misc/diag-template-diffing.cpp
Clang :: Misc/error-limit-multiple-notes.cpp
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_private_codegen.cpp
LLVM :: CodeGen/AArch64/global-merge-group-by-use.ll
LLVM :: Transforms/GVNHoist/hoist.ll
LLVM :: Transforms/Util/PredicateInfo/testandor.ll
LLVM :: tools/llvm-cov/hideUnexecutedSubviews.test
LLVM :: tools/llvm-cov/showTemplateInstantiations.cpp
LLVM :: tools/llvm-xray/X86/graph-zero-latency-calls.yaml

[mgrang]

I am not sure if there is a non-intrusive way to call llvm::sort when std::sort is called. Any ideas?

[mgrang]

In reply to @vsk "Do you mind sharing the llvm-cov test failure output?"

tools/llvm-cov/hideUnexecutedSubviews.test:

Regular build:
Unexecuted instantiation: _Z4funcIiEiT_
  ------------------
Unexecuted instantiation: _Z4funcIbEiT_

Shuffle & sort:
Unexecuted instantiation: _Z4funcIbEiT_
  ------------------
Unexecuted instantiation: _Z4funcIiEiT_

tools/llvm-cov/showTemplateInstantiations.cpp:

Regular build:
  | _Z4funcIbEiT_:
  |    7|      1|int func(T x) {      // ALL-NEXT:    [[@LINE]]| 2|int func(T x) {
  |    8|      1|  if(x)              // ALL-NEXT:    [[@LINE]]| 2|  if(x)
  |    9|      1|    return 0;        // ALL-NEXT:    [[@LINE]]| 1|    return 0;
  |   10|      1|  else               // ALL-NEXT:    [[@LINE]]| 2|  else
  |   11|      0|    return 1;        // ALL-NEXT:    [[@LINE]]| 1|    return 1;
  |   12|      0|  int j = 1;         // ALL-NEXT:    [[@LINE]]| 0|  int j = 1;
  |   13|      1|}                    // ALL-NEXT:    [[@LINE]]| 2|}
  ------------------
  | _Z4funcIiEiT_:
  |    7|      1|int func(T x) {      // ALL-NEXT:    [[@LINE]]| 2|int func(T x) {
  |    8|      1|  if(x)              // ALL-NEXT:    [[@LINE]]| 2|  if(x)
  |    9|      0|    return 0;        // ALL-NEXT:    [[@LINE]]| 1|    return 0;
  |   10|      1|  else               // ALL-NEXT:    [[@LINE]]| 2|  else
  |   11|      1|    return 1;        // ALL-NEXT:    [[@LINE]]| 1|    return 1;
  |   12|      0|  int j = 1;         // ALL-NEXT:    [[@LINE]]| 0|  int j = 1;
  |   13|      1|}                    // ALL-NEXT:    [[@LINE]]| 2|}

Shuffle & Sort:
  | _Z4funcIiEiT_:
  |    7|      1|int func(T x) {      // ALL-NEXT:    [[@LINE]]| 2|int func(T x) {
  |    8|      1|  if(x)              // ALL-NEXT:    [[@LINE]]| 2|  if(x)
  |    9|      0|    return 0;        // ALL-NEXT:    [[@LINE]]| 1|    return 0;
  |   10|      1|  else               // ALL-NEXT:    [[@LINE]]| 2|  else
  |   11|      1|    return 1;        // ALL-NEXT:    [[@LINE]]| 1|    return 1;
  |   12|      0|  int j = 1;         // ALL-NEXT:    [[@LINE]]| 0|  int j = 1;
  |   13|      1|}                    // ALL-NEXT:    [[@LINE]]| 2|}
  ------------------
  | _Z4funcIbEiT_:
  |    7|      1|int func(T x) {      // ALL-NEXT:    [[@LINE]]| 2|int func(T x) {
  |    8|      1|  if(x)              // ALL-NEXT:    [[@LINE]]| 2|  if(x)
  |    9|      1|    return 0;        // ALL-NEXT:    [[@LINE]]| 1|    return 0;
  |   10|      1|  else               // ALL-NEXT:    [[@LINE]]| 2|  else
  |   11|      0|    return 1;        // ALL-NEXT:    [[@LINE]]| 1|    return 1;
  |   12|      0|  int j = 1;         // ALL-NEXT:    [[@LINE]]| 0|  int j = 1;
  |   13|      1|}                    // ALL-NEXT:    [[@LINE]]| 2|}

[vsk]

@mgrang thanks, should be fixed in r316490.

[dexonsmith]

std::sort and array_pod_sort both use quicksort

FWIW, most standards-compliant std::sort implementations use introsort... although it's also unstable.

NOTE: To randomly shuffle before std::sort we may have to change all calls to std::sort with llvm::sort.

It looks to me like the current overloads of llvm::sort take a parallel execution policy, which would be unfortunate boilerplate to add. Perhaps you should create an overload in ADT/STLExtras.h with the same signature as std::sort (that wraps std::sort with the initial call to std::random_shuffle).

[mgrang]

In D39245#905733, @dexonsmith wrote:

std::sort and array_pod_sort both use quicksort

FWIW, most standards-compliant std::sort implementations use introsort... although it's also unstable.

NOTE: To randomly shuffle before std::sort we may have to change all calls to std::sort with llvm::sort.

It looks to me like the current overloads of llvm::sort take a parallel execution policy, which would be unfortunate boilerplate to add. Perhaps you should create an overload in ADT/STLExtras.h with the same signature as std::sort (that wraps std::sort with the initial call to std::random_shuffle).

Sure, I can add overload for llvm::sort which takes ExecutionPolicy and invoke std::sort. However, it would still mean changing all calls to std::sort with llvm::sort if this feature needs to be tested. Is there a way to do this w/o changing the callers? #define std::sort llvm::sort won't work because of the double colon (::), redefining std::sort will result in duplicate definitions, etc.

[dexonsmith]

In D39245#905862, @mgrang wrote:

In D39245#905733, @dexonsmith wrote:

std::sort and array_pod_sort both use quicksort

FWIW, most standards-compliant std::sort implementations use introsort... although it's also unstable.

NOTE: To randomly shuffle before std::sort we may have to change all calls to std::sort with llvm::sort.

It looks to me like the current overloads of llvm::sort take a parallel execution policy, which would be unfortunate boilerplate to add. Perhaps you should create an overload in ADT/STLExtras.h with the same signature as std::sort (that wraps std::sort with the initial call to std::random_shuffle).

Sure, I can add overload for llvm::sort which takes ExecutionPolicy and invoke std::sort.

You mean, add an overload that does not take ExecutionPolicy?

However, it would still mean changing all calls to std::sort with llvm::sort if this feature needs to be tested. Is there a way to do this w/o changing the callers? #define std::sort llvm::sort won't work because of the double colon (::), redefining std::sort will result in duplicate definitions, etc.

I think the best thing to do is to update the callers to call llvm::sort instead of std::sort.

[mgrang]

Added std::sort overloads for ExecutionPolicy.

[dexonsmith]

include/llvm/ADT/STLExtras.h

807–814 ↗

(On Diff #120187)

Doesn't this already exist in llvm/Support/Parallel.h?

[mgrang]

include/llvm/ADT/STLExtras.h

807–814 ↗

(On Diff #120187)

Yea ... it apparently does. So I guess we don't need the ExecutionPolicy overloads here. Will remove them. Thanks!

[mgrang]

Removed overloads for ExecutionPolicy as they are already present in llvm/Support/Parallel.h.

[chandlerc]

I don't really like the ever growing set of configuration macros here.

I would much prefer we have one ABI-breaking check macro and just use that for everything here...

include/llvm/ADT/STLExtras.h

792 ↗

(On Diff #120294)

This was deprecated in C++14, I think you want std::shuffle now with a PRNG parameter.

[mgrang]

In D39245#907221, @chandlerc wrote:

I don't really like the ever growing set of configuration macros here.

I would much prefer we have one ABI-breaking check macro and just use that for everything here...

Thanks @chandlerc. I am fine with enabling this based on LLVM_ABI_BREAKING_CHECKS. However, this macro is ON by default for +asserts builds. This means all existing +asserts bots would start failing as soon as this patch gets merged since there are about 15 unit test failures. Do we want to gate patches if they show up sort order failures uncovered by shuffling?
My idea was to control this via a separate macro so that we can isolate shuffle+sort failures into a separate bot which may make it easier to fix without gating the regular flow. Thoughts?

[davide]

In D39245#907426, @mgrang wrote:

In D39245#907221, @chandlerc wrote:

I don't really like the ever growing set of configuration macros here.

I would much prefer we have one ABI-breaking check macro and just use that for everything here...

Thanks @chandlerc. I am fine with enabling this based on LLVM_ABI_BREAKING_CHECKS. However, this macro is ON by default for +asserts builds. This means all existing +asserts bots would start failing as soon as this patch gets merged since there are about 15 unit test failures. Do we want to gate patches if they show up sort order failures uncovered by shuffling?
My idea was to control this via a separate macro so that we can isolate shuffle+sort failures into a separate bot which may make it easier to fix without gating the regular flow. Thoughts?

I agree with Chandler that we should avoid the proliferation of macros and use ABI_BREAKING_CHECKS instead.
Is it possible to fixing the failures before enabling the switch? (or, in the same commit?) That should avoid bot breakage [I understand it's chasing a moving target, as we did with EXPENSIVE_CHECK, but it turned out to be worth in the long run fixing all the tests and turning the switch on instead of introducing new macros, cc: @RKSimon ]

[mgrang]

In D39245#907527, @davide wrote:

In D39245#907426, @mgrang wrote:

In D39245#907221, @chandlerc wrote:

I don't really like the ever growing set of configuration macros here.

I would much prefer we have one ABI-breaking check macro and just use that for everything here...

Thanks @chandlerc. I am fine with enabling this based on LLVM_ABI_BREAKING_CHECKS. However, this macro is ON by default for +asserts builds. This means all existing +asserts bots would start failing as soon as this patch gets merged since there are about 15 unit test failures. Do we want to gate patches if they show up sort order failures uncovered by shuffling?
My idea was to control this via a separate macro so that we can isolate shuffle+sort failures into a separate bot which may make it easier to fix without gating the regular flow. Thoughts?

I agree with Chandler that we should avoid the proliferation of macros and use ABI_BREAKING_CHECKS instead.
Is it possible to fixing the failures before enabling the switch? (or, in the same commit?) That should avoid bot breakage [I understand it's chasing a moving target, as we did with EXPENSIVE_CHECK, but it turned out to be worth in the long run fixing all the tests and turning the switch on instead of introducing new macros, cc: @RKSimon ]

Thanks Davide. So the consensus seems to be that ABI_BREAKING_CHECKS would be a better option to base this patch on. I have updated my patch accordingly.
We would need to fix the existing failures before this can be merged. I will solicit help from the code owners/developers of the breaking tests to get them fixed. Once those are fixed I would push patches to change std::sort to llvm::sort for llvm/clang/polly/compiler-rt.

[dexonsmith]

In D39245#907527, @davide wrote:

In D39245#907426, @mgrang wrote:

In D39245#907221, @chandlerc wrote:

I don't really like the ever growing set of configuration macros here.

I would much prefer we have one ABI-breaking check macro and just use that for everything here...

Thanks @chandlerc. I am fine with enabling this based on LLVM_ABI_BREAKING_CHECKS. However, this macro is ON by default for +asserts builds. This means all existing +asserts bots would start failing as soon as this patch gets merged since there are about 15 unit test failures. Do we want to gate patches if they show up sort order failures uncovered by shuffling?
My idea was to control this via a separate macro so that we can isolate shuffle+sort failures into a separate bot which may make it easier to fix without gating the regular flow. Thoughts?

I agree with Chandler that we should avoid the proliferation of macros and use ABI_BREAKING_CHECKS instead.

I'm actually a bit confused by this. How is this ABI-breaking? If (1) I'm right, and it isn't ABI-breaking, and (2) we're not going to have a custom macro, then I think this should just be behind NDEBUG.

ABI_BREAKING_CHECKS is meant to be for NDEBUG-like checks that actually break the ABI. One could, in theory, build Clang with assertions, build LLVM without assertions, and still a functional compiler by overriding one of the defaults for ABI_BREAKING_CHECKS. I don't see how that applies to these checks.

[dexonsmith]

include/llvm/ADT/STLExtras.h

779–782 ↗

(On Diff #120362)

I don't see how toggling these checks would be ABI-breaking, so I think this is the wrong macro to use.

[davide]

In D39245#907960, @dexonsmith wrote:

In D39245#907527, @davide wrote:

In D39245#907426, @mgrang wrote:

In D39245#907221, @chandlerc wrote:

I don't really like the ever growing set of configuration macros here.

I would much prefer we have one ABI-breaking check macro and just use that for everything here...

Thanks @chandlerc. I am fine with enabling this based on LLVM_ABI_BREAKING_CHECKS. However, this macro is ON by default for +asserts builds. This means all existing +asserts bots would start failing as soon as this patch gets merged since there are about 15 unit test failures. Do we want to gate patches if they show up sort order failures uncovered by shuffling?
My idea was to control this via a separate macro so that we can isolate shuffle+sort failures into a separate bot which may make it easier to fix without gating the regular flow. Thoughts?

I agree with Chandler that we should avoid the proliferation of macros and use ABI_BREAKING_CHECKS instead.

I'm actually a bit confused by this. How is this ABI-breaking? If (1) I'm right, and it isn't ABI-breaking, and (2) we're not going to have a custom macro, then I think this should just be behind NDEBUG.

ABI_BREAKING_CHECKS is meant to be for NDEBUG-like checks that actually break the ABI. One could, in theory, build Clang with assertions, build LLVM without assertions, and still a functional compiler by overriding one of the defaults for ABI_BREAKING_CHECKS. I don't see how that applies to these checks.

I haven't looked very closely, mine was just a meta comment. If they don't break the ABI, probably ABI_BREAKING_CHECKS is not the correct place, of course, but I can't comment further on that.
FWIW, NDEBUG is probably OK if the cost of the check is nearly zero, otherwise I would put them under LLVM_EXPENSIVE_CHECKS (we have a bot for that already).
That said, my point that we shouldn't have yet another macro stands, I guess, independently from the bucket we decide to throw these checks in.

[dexonsmith]

In D39245#908059, @davide wrote:

That said, my point that we shouldn't have yet another macro stands, I guess, independently from the bucket we decide to throw these checks in.

Yup, no quarrel there.

[mgrang]

In D39245#907960, @dexonsmith wrote:

In D39245#907527, @davide wrote:

In D39245#907426, @mgrang wrote:

In D39245#907221, @chandlerc wrote:

I don't really like the ever growing set of configuration macros here.

I would much prefer we have one ABI-breaking check macro and just use that for everything here...

Thanks @chandlerc. I am fine with enabling this based on LLVM_ABI_BREAKING_CHECKS. However, this macro is ON by default for +asserts builds. This means all existing +asserts bots would start failing as soon as this patch gets merged since there are about 15 unit test failures. Do we want to gate patches if they show up sort order failures uncovered by shuffling?
My idea was to control this via a separate macro so that we can isolate shuffle+sort failures into a separate bot which may make it easier to fix without gating the regular flow. Thoughts?

I agree with Chandler that we should avoid the proliferation of macros and use ABI_BREAKING_CHECKS instead.

I'm actually a bit confused by this. How is this ABI-breaking? If (1) I'm right, and it isn't ABI-breaking, and (2) we're not going to have a custom macro, then I think this should just be behind NDEBUG.

ABI_BREAKING_CHECKS is meant to be for NDEBUG-like checks that actually break the ABI. One could, in theory, build Clang with assertions, build LLVM without assertions, and still a functional compiler by overriding one of the defaults for ABI_BREAKING_CHECKS. I don't see how that applies to these checks.

In D39245#908229, @dexonsmith wrote:

In D39245#908059, @davide wrote:

That said, my point that we shouldn't have yet another macro stands, I guess, independently from the bucket we decide to throw these checks in.

Yup, no quarrel there.

I guess +asserts and -asserts builds should be comparable in terms of ninja check failures. I would prefer not to add these under ABI_BREAKING. How about we add these either under EXPENSIVE_CHECKS or rename LLVM_REVERSE_ITERATION as LLVM_NON_DETERMINISM_CHECKS and add these under that?

Btw .. I ran shuffle+sort with all targets enabled and see 39 ninja check failures (previously I had built only ARM/AArch64 targets).

[chandlerc]

As with Davide, my argument was mostly "use an existing bucket" not "it should be in bucket X". =]

I'm happy with this being under NDEBUG if this doesn't break ABI. As long as shuffle is O(N), adding an O(N) check to an O(N * log(N)) algorithm seems totally fine for NDEBUG, so I'd rather not stuff it behind the "expensive checks" macro.

In D39245#908745, @mgrang wrote:

I guess +asserts and -asserts builds should be comparable in terms of ninja check failures. I would prefer not to add these under ABI_BREAKING. How about we add these either under EXPENSIVE_CHECKS or rename LLVM_REVERSE_ITERATION as LLVM_NON_DETERMINISM_CHECKS and add these under that?

Btw .. I ran shuffle+sort with all targets enabled and see 39 ninja check failures (previously I had built only ARM/AArch64 targets).

The suggestion is that we should fix these failures before we land this unless there is some reason that will be infeasible to do. That way we don't have new failures?

[davide]

In D39245#908758, @chandlerc wrote:

As with Davide, my argument was mostly "use an existing bucket" not "it should be in bucket X". =]

I'm happy with this being under NDEBUG if this doesn't break ABI. As long as shuffle is O(N), adding an O(N) check to an O(N * log(N)) algorithm seems totally fine for NDEBUG, so I'd rather not stuff it behind the "expensive checks" macro.

Makes sense.

In D39245#908745, @mgrang wrote:

I guess +asserts and -asserts builds should be comparable in terms of ninja check failures. I would prefer not to add these under ABI_BREAKING. How about we add these either under EXPENSIVE_CHECKS or rename LLVM_REVERSE_ITERATION as LLVM_NON_DETERMINISM_CHECKS and add these under that?

Btw .. I ran shuffle+sort with all targets enabled and see 39 ninja check failures (previously I had built only ARM/AArch64 targets).

The suggestion is that we should fix these failures before we land this unless there is some reason that will be infeasible to do. That way we don't have new failures?

Nod, that was my suggestion too. I completely understand it's annoying as people continue checking in code that might break other stuffs, but, I guess this frustration will also speed up the fix :)

[mgrang]

Enabled the change under NDEBUG.

[RKSimon]

@mgrang I noticed you resolved PR35135 - what are you intending to do with this patch?

[mgrang]

All outstanding unit test failures uncovered by this patch have now been resolved on the tip. Can we now please get this patch reviewed and merged?
Once this patch merges we can do a mass replacement of std::sort to llvm::sort in the entire code base.

[RKSimon]

Wouldn't this kind of testing be better under EXPENSIVE_CHECKS instead of NDEBUG?

[mgrang]

In D39245#1019143, @RKSimon wrote:

Wouldn't this kind of testing be better under EXPENSIVE_CHECKS instead of NDEBUG?

Complexity-wise std::shuffle is not too expensive (it's O(n) while sorting is O(n*log n). So I'm not sure if this should be under EXPENSIVE_CHECKS.
With that said, I am totally fine shoving this under EXPENSIVE_CHECKS as long as we have consensus that that's the most appropriate macro for this :) Otherwise, I guess this can remain under NDEBUG.
Thoughts?

[mgrang]

Ping for reviews please.

[mgrang]

Ping 2 for reviews please.

[RKSimon]

@davide @efriedma @chandlerc Does anyone want this under NDEBUG or should it be moved to EXPENSIVE_CHECKS?

[davide]

std::shuffle has linear time complexity, so I'd rather not pessimize the DEBUG build even more.

[efriedma]

EXPENSIVE_CHECKS is fine.

[RKSimon]

OK, let's go for EXPENSIVE_CHECKS

[mgrang]

In D39245#1032152, @RKSimon wrote:

OK, let's go for EXPENSIVE_CHECKS

Sounds good! Thanks everyone for your feedback. I will push a patch soon.

[mgrang]

Based std::shuffle on EXPENSIVE_CHECKS instead of NDEBUG.

[RKSimon]

LGTM, with one minor

include/llvm/ADT/STLExtras.h

794 ↗

(On Diff #137693)

Please expand this a little:

// Provide wrappers to std::sort which shuffle the elements before sorting
// to help uncover non-deterministic behavior (PR35135).

[mgrang]

Expanded comment.

[RKSimon]

Thanks, LGTM

llvm/trunk/include/llvm/ADT/STLExtras.h

 #include <initializer_list>
 #include <iterator>
 #include <limits>
 #include <memory>
 #include <tuple>
 #include <type_traits>
 #include <utility>
 
+#ifdef EXPENSIVE_CHECKS
+#include <random> // for std::mt19937
+#endif
+
 namespace llvm {
 
 // Only used by compiler if both template types are the same.  Useful when
 // using SFINAE to test for the existence of member functions.
 template <typename T, T> struct SameType;
 
 namespace detail {
 

 /// NOTE: If qsort_r were portable, we could allow a custom comparator and
 /// default to std::less.
 template<class IteratorTy>
 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
   // Don't inefficiently call qsort with one element or trigger undefined
   // behavior with an empty sequence.
   auto NElts = End - Start;
   if (NElts <= 1) return;
+#ifdef EXPENSIVE_CHECKS
+  std::mt19937 Generator(std::random_device{}());
+  std::shuffle(Start, End, Generator);
+#endif
   qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
 }
 
 template <class IteratorTy>
 inline void array_pod_sort(
     IteratorTy Start, IteratorTy End,
     int (*Compare)(
         const typename std::iterator_traits<IteratorTy>::value_type *,
         const typename std::iterator_traits<IteratorTy>::value_type *)) {
   // Don't inefficiently call qsort with one element or trigger undefined
   // behavior with an empty sequence.
   auto NElts = End - Start;
   if (NElts <= 1) return;
+#ifdef EXPENSIVE_CHECKS
+  std::mt19937 Generator(std::random_device{}());
+  std::shuffle(Start, End, Generator);
+#endif
   qsort(&*Start, NElts, sizeof(*Start),
         reinterpret_cast<int (*)(const void *, const void *)>(Compare));
 }
 
+// Provide wrappers to std::sort which shuffle the elements before sorting
+// to help uncover non-deterministic behavior (PR35135).
+template <typename IteratorTy>
+inline void sort(IteratorTy Start, IteratorTy End) {
+#ifdef EXPENSIVE_CHECKS
+  std::mt19937 Generator(std::random_device{}());
+  std::shuffle(Start, End, Generator);
+#endif
+  std::sort(Start, End);
+}
+
+template <typename IteratorTy, typename Compare>
+inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
+#ifdef EXPENSIVE_CHECKS
+  std::mt19937 Generator(std::random_device{}());
+  std::shuffle(Start, End, Generator);
+#endif
+  std::sort(Start, End, Comp);
+}
+
 //===----------------------------------------------------------------------===//
 //     Extra additions to <algorithm>
 //===----------------------------------------------------------------------===//
 
 /// For a container of pointers, deletes the pointers and then clears the
 /// container.
 template<typename Container>
 void DeleteContainerPointers(Container &C) {