[MachineModuleInfoImpls] Replace qsort with array_pod_sort

[mgrang]

Summary

This seems to be the only place in llvm we directly call qsort. We can replace
this with a call to array_pod_sort. Also minor cleanup of the sorting function.

[efriedma]

Using stable_sort doesn't solve anything here: the input is constructed by iterating over a DenseMap whose key is a pointer.

(If you just want to clean this up without actually changing the algorithm, there's a three-operand overload of array_pod_sort.)

[mgrang]

In D39214#904490, @efriedma wrote:

Using stable_sort doesn't solve anything here: the input is constructed by iterating over a DenseMap whose key is a pointer.

(If you just want to clean this up without actually changing the algorithm, there's a three-operand overload of array_pod_sort.)

I agree. But using array_pod_sort also does not solve anything since the input order itself is random. Maybe we can specify a stronger sort predicate?

[bkramer]

Can you point at the test cases that are failing? This would mean that there are two symbols with the same name, which seems like something that shouldn't happen.

[mgrang]

In D39214#906176, @bkramer wrote:

Can you point at the test cases that are failing? This would mean that there are two symbols with the same name, which seems like something that shouldn't happen.

The following 3 tests fail:

LLVM :: CodeGen/ARM/available_externally.ll
LLVM :: CodeGen/ARM/darwin-tls.ll
LLVM :: CodeGen/ARM/indirect-hidden.ll

[bkramer]

In D39214#906190, @mgrang wrote:

In D39214#906176, @bkramer wrote:

Can you point at the test cases that are failing? This would mean that there are two symbols with the same name, which seems like something that shouldn't happen.

The following 3 tests fail:

LLVM :: CodeGen/ARM/available_externally.ll
LLVM :: CodeGen/ARM/darwin-tls.ll
LLVM :: CodeGen/ARM/indirect-hidden.ll

I think this is just a result of your predicate being wrong for std::sort (it's also wrong for stable_sort, but there you might get lucky). It wants a bool that's true when the symbol is compares less than, instead of the tristate you have in this change.

I'd prefer to just use array_pod_sort here. It also wants a tristate so just swapping out qsort for array_pod_sort should pass tests.

[bkramer]

Looks good, thanks!

lib/CodeGen/MachineModuleInfoImpls.cpp

29–31

Any reason for moving this using decl out of the function?

38

Nit: array_pod_sort checks for empty, so this if isn't necessary anymore.

[mgrang]

lib/CodeGen/MachineModuleInfoImpls.cpp

29–31

I think the casts from void * to PairTy * and then saving to MCSymbol were not really needed. So I moved the using decl outside and use it in the function signature. This simplifies the sorting function.

38

Will remove this check.

lib/CodeGen/MachineModuleInfoImpls.cpp

 // This file implements object-file format specific implementations of
 // MachineModuleInfoImpl.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/MachineModuleInfoImpls.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/MC/MCSymbol.h"
-#include <cstdlib>
-#include <utility>
 
 using namespace llvm;
 
 //===----------------------------------------------------------------------===//
 // MachineModuleInfoMachO
 //===----------------------------------------------------------------------===//
 
 // Out of line virtual method.
 void MachineModuleInfoMachO::anchor() {}
 void MachineModuleInfoELF::anchor() {}
 
-static int SortSymbolPair(const void *LHS, const void *RHS) {
-  using PairTy = std::pair<MCSymbol *, MachineModuleInfoImpl::StubValueTy>;
-
-  const MCSymbol *LHSS = ((const PairTy *)LHS)->first;
-  const MCSymbol *RHSS = ((const PairTy *)RHS)->first;
-  return LHSS->getName().compare(RHSS->getName());
+static int SortSymbolPair(PairTy LHS, PairTy RHS) {
+  return LHS.first->getName().compare(RHS.first->getName());
 }
 
 MachineModuleInfoImpl::SymbolListTy MachineModuleInfoImpl::getSortedStubs(
     DenseMap<MCSymbol *, MachineModuleInfoImpl::StubValueTy> &Map) {
   MachineModuleInfoImpl::SymbolListTy List(Map.begin(), Map.end());
 
   if (!List.empty())
-    qsort(&List[0], List.size(), sizeof(List[0]), SortSymbolPair);
+    std::stable_sort(List.begin(), List.end(), SortSymbolPair);
 
   Map.clear();
   return List;
 }