[Support] 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.

[jordan_rose]

I'm a little disappointed that llvm::sort got added without providing a range-based variant, the way we did for llvm::none_of and llvm::find and others. (I wasn't watching the original thread.) I see no problem with these changes, though!

[bkramer]

this is trivially fine.

[mgrang]

In D45140#1054514, @jordan_rose wrote:

I'm a little disappointed that llvm::sort got added without providing a range-based variant, the way we did for llvm::none_of and llvm::find and others. (I wasn't watching the original thread.) I see no problem with these changes, though!

@jordan_rose Thanks for your suggestion. Are there instances in llvm where we perform range-based sorting? I see that std has an experimental range-based sort (std::experimental::ranges::sort) which I don't see being used in llvm.

Also what should be the semantics of a range-based shuffle sort? Will it just shuffle the given range? Or should it shuffle the entire container but just sort the range?

[jordan_rose]

Are there instances in llvm where we perform range-based sorting? I see that std has an experimental range-based sort (std::experimental::ranges::sort) which I don't see being used in llvm.

I think in practice almost *every* sort we do would be range-based (i.e. we almost always sort an entire container). We generally don't use std::experimental things in LLVM because they're not reliably present across platforms, but that doesn't mean we don't provide our own implementations for good ideas.

Also what should be the semantics of a range-based shuffle sort? Will it just shuffle the given range? Or should it shuffle the entire container but just sort the range?

I don't understand this question. You can't get to the entire container from a range.

[mgrang]

In D45140#1061971, @jordan_rose wrote:

Are there instances in llvm where we perform range-based sorting? I see that std has an experimental range-based sort (std::experimental::ranges::sort) which I don't see being used in llvm.

I think in practice almost *every* sort we do would be range-based (i.e. we almost always sort an entire container). We generally don't use std::experimental things in LLVM because they're not reliably present across platforms, but that doesn't mean we don't provide our own implementations for good ideas.

Also what should be the semantics of a range-based shuffle sort? Will it just shuffle the given range? Or should it shuffle the entire container but just sort the range?

I don't understand this question. You can't get to the entire container from a range.

I think in practice almost *every* sort we do would be range-based (i.e. we almost always sort an entire container).

Exactly that's what I thought too, and llvm::sort already accepts a range (Container.begin(), Container.end()). In that case, could you please clarify what exactly do you mean by a "range-based variant" and its use cases in LLVM?
My idea of range-based was maybe you wanted to sort a subset of the container. Apologies if I did not understand the original requirement :)

[jordan_rose]

Exactly that's what I thought too, and llvm::sort already accepts a range (Container.begin(), Container.end()). In that case, could you please clarify what exactly do you mean by a "range-based variant" and its use cases in LLVM?

Ah, sorry! A "range-based" collection algorithm means one that takes a "range" as an argument instead of a pair of iterators. The "range" is anything that has begin and end iterators. ("Container-based algorithm" might have been a better name, since usually the "range" you pass is the entire container, but "range" is already an accepted term in C++ language and library discussions.)

So in this case, the call would look like this:

llvm::sort(TimersToPrint);

You can check out the implementation of llvm::none_of in include/llvm/ADT/STLExtras.h to see how this works. It just forwards on to the regular implementation.

None of this is related to your shuffling work, by the way; it's just odd and a bit inconsistent that there's an llvm:: algorithm that only takes iterators.

[mgrang]

In D45140#1062032, @jordan_rose wrote:

Exactly that's what I thought too, and llvm::sort already accepts a range (Container.begin(), Container.end()). In that case, could you please clarify what exactly do you mean by a "range-based variant" and its use cases in LLVM?

Ah, sorry! A "range-based" collection algorithm means one that takes a "range" as an argument instead of a pair of iterators. The "range" is anything that has begin and end iterators. ("Container-based algorithm" might have been a better name, since usually the "range" you pass is the entire container, but "range" is already an accepted term in C++ language and library discussions.)

So in this case, the call would look like this:

llvm::sort(TimersToPrint);

You can check out the implementation of llvm::none_of in include/llvm/ADT/STLExtras.h to see how this works. It just forwards on to the regular implementation.

None of this is related to your shuffling work, by the way; it's just odd and a bit inconsistent that there's an llvm:: algorithm that only takes iterators.

Ah, got it! Thanks a lot for your clarification. I will explore adding a range-based version of llvm::sort when I have some cycles.

llvm/trunk/lib/Support/SourceMgr.cpp

 SMDiagnostic::SMDiagnostic(const SourceMgr &sm, SMLoc L, StringRef FN,
                            int Line, int Col, SourceMgr::DiagKind Kind,
                            StringRef Msg, StringRef LineStr,
                            ArrayRef<std::pair<unsigned,unsigned>> Ranges,
                            ArrayRef<SMFixIt> Hints)
   : SM(&sm), Loc(L), Filename(FN), LineNo(Line), ColumnNo(Col), Kind(Kind),
     Message(Msg), LineContents(LineStr), Ranges(Ranges.vec()),
     FixIts(Hints.begin(), Hints.end()) {
-  std::sort(FixIts.begin(), FixIts.end());
+  llvm::sort(FixIts.begin(), FixIts.end());
 }
 
 static void buildFixItLine(std::string &CaretLine, std::string &FixItLine,
                            ArrayRef<SMFixIt> FixIts, ArrayRef<char> SourceLine){
   if (FixIts.empty())
     return;
 
   const char *LineStart = SourceLine.begin();

llvm/trunk/lib/Support/Timer.cpp

if (FirstTimer)
     FirstTimer->Prev = &T.Next;
   T.Next = FirstTimer;
   T.Prev = &FirstTimer;
   FirstTimer = &T;
 }
 
 void TimerGroup::PrintQueuedTimers(raw_ostream &OS) {
   // Sort the timers in descending order by amount of time taken.
-  std::sort(TimersToPrint.begin(), TimersToPrint.end());
+  llvm::sort(TimersToPrint.begin(), TimersToPrint.end());
 
   TimeRecord Total;
   for (const PrintRecord &Record : TimersToPrint)
     Total += Record.Time;
 
   // Print out timing header.
   OS << "===" << std::string(73, '-') << "===\n";
   // Figure out how many spaces to indent TimerGroup name.