[AArch64] Change std::sort to llvm::sort in response to r327219

[mgrang]

Summary

r327219 added wrappers to std::sort which randomly shuffle the container before sorting.
This will help in uncovering non-determinism caused due to undefined sorting
order of objects having the same key.

To make use of that infrastructure we need to invoke llvm::sort instead of std::sort.

Note: This patch is one of a series of patches to replace *all* std::sort to llvm::sort. Refer the comments section in D44363 for a list of all the required patches.

[rengolin]

I don't like this being on by default. I get it it uses EXPENSIVE_CHECKS, but still, most developers use Debug/Asserts builds.

I think it's fine to have the llvm::sort in tree, but the patches that make use of it should be local, as they're use for specific investigations.

Either that, or we replace *all* std::sort for llvm:sort and not just this one particular case.

[mgrang]

In D44853#1047489, @rengolin wrote:

I don't like this being on by default. I get it it uses EXPENSIVE_CHECKS, but still, most developers use Debug/Asserts builds.

I think it's fine to have the llvm::sort in tree, but the patches that make use of it should be local, as they're use for specific investigations.

Either that, or we replace *all* std::sort for llvm:sort and not just this one particular case.

This patch is one of a series of patches to replace *all* std::sort to llvm::sort in llvm/clang/polly (and other tools). I have a patch (https://reviews.llvm.org/D44363) which replaces all std::sort to llvm::sort. But as per review comments, it was suggested to break down that patch target-wise to smaller chunks. Hence I am now pushing smaller target-specific patches.

[mgrang]

Ping for review please.

[rengolin]

In D44853#1047492, @mgrang wrote:

This patch is one of a series of patches to replace *all* std::sort to llvm::sort in llvm/clang/polly (and other tools). I have a patch (https://reviews.llvm.org/D44363) which replaces all std::sort to llvm::sort. But as per review comments, it was suggested to break down that patch target-wise to smaller chunks. Hence I am now pushing smaller target-specific patches.

Right, those look to be the only two in the AArch64 back-end, LGTM. Sorry for the delay.

llvm/trunk/lib/Target/AArch64/AArch64A57FPLoadBalancing.cpp

bool AArch64A57FPLoadBalancing::runOnBasicBlock(MachineBasicBlock &MBB) {
   for (auto I = EC.begin(), E = EC.end(); I != E; ++I) {
     std::vector<Chain*> Cs(EC.member_begin(I), EC.member_end());
     if (Cs.empty()) continue;
     V.push_back(std::move(Cs));
   }
 
   // Now we have a set of sets, order them by start address so
   // we can iterate over them sequentially.
-  std::sort(V.begin(), V.end(),
+  llvm::sort(V.begin(), V.end(),
              [](const std::vector<Chain*> &A,
                 const std::vector<Chain*> &B) {
       return A.front()->startsBefore(B.front());
     });
 
   // As we only have two colors, we can track the global (BB-level) balance of
   // odds versus evens. We aim to keep this near zero to keep both execution
   // units fed.
   // Positive means we're even-heavy, negative we're odd-heavy.
   //
bool AArch64A57FPLoadBalancing::colorChainSet(std::vector<Chain*> GV,
   // sets first.
   // Tie-break equivalent sizes by sorting chains requiring fixups before
   // those without fixups. The logic here is that we should look at the
   // chains that we cannot change before we look at those we can,
   // so the parity counter is updated and we know what color we should
   // change them to!
   // Final tie-break with instruction order so pass output is stable (i.e. not
   // dependent on malloc'd pointer values).
-  std::sort(GV.begin(), GV.end(), [](const Chain *G1, const Chain *G2) {
+  llvm::sort(GV.begin(), GV.end(), [](const Chain *G1, const Chain *G2) {
       if (G1->size() != G2->size())
         return G1->size() > G2->size();
       if (G1->requiresFixup() != G2->requiresFixup())
         return G1->requiresFixup() > G2->requiresFixup();
       // Make sure startsBefore() produces a stable final order.
       assert((G1 == G2 || (G1->startsBefore(G2) ^ G2->startsBefore(G1))) &&
              "Starts before not total order!");
       return G1->startsBefore(G2);