This is an archive of the discontinued LLVM Phabricator instance.

[MachineModuleInfoImpls] Replace qsort with array_pod_sort
ClosedPublic

Authored by mgrang on Oct 23 2017, 4:19 PM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

mgrang created this revision.Oct 23 2017, 4:19 PM

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.)

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 edited edge metadata.Oct 24 2017, 11:25 PM

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.

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 requested changes to this revision.Oct 25 2017, 1:20 AM

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.

This revision now requires changes to proceed.Oct 25 2017, 1:20 AM
mgrang updated this revision to Diff 120287.Oct 25 2017, 11:23 AM
mgrang edited edge metadata.
mgrang retitled this revision from [MachineModuleInfoImpls] Replace qsort with std::stable_sort to [MachineModuleInfoImpls] Replace qsort with array_pod_sort.
mgrang edited the summary of this revision. (Show Details)
bkramer accepted this revision.Oct 26 2017, 12:30 AM

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.

This revision is now accepted and ready to land.Oct 26 2017, 12:30 AM
mgrang added inline comments.Oct 26 2017, 9:05 AM
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.

This revision was automatically updated to reflect the committed changes.