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

llvm/trunk/lib/Target/Hexagon/HexagonBlockRanges.cpp

 }
 
 // Merge all overlapping ranges in the list, so that all that remains
 // is a list of disjoint ranges.
 void HexagonBlockRanges::RangeList::unionize(bool MergeAdjacent) {
   if (empty())
     return;
 
-  std::sort(begin(), end());
+  llvm::sort(begin(), end());
   iterator Iter = begin();
 
   while (Iter != end()-1) {
     iterator Next = std::next(Iter);
     // If MergeAdjacent is true, merge ranges A and B, where A.end == B.start.
     // This allows merging dead ranges, but is not valid for live ranges.
     bool Merge = MergeAdjacent && (Iter->end() == Next->start());
     if (Merge || Iter->overlaps(*Next)) {

llvm/trunk/lib/Target/Hexagon/HexagonConstExtenders.cpp

bool HCE::runOnMachineFunction(MachineFunction &MF) {
 
   HII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
   HRI = MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
   MDT = &getAnalysis<MachineDominatorTree>();
   MRI = &MF.getRegInfo();
   AssignmentMap IMap;
 
   collect(MF);
-  std::sort(Extenders.begin(), Extenders.end(),
+  llvm::sort(Extenders.begin(), Extenders.end(),
     [](const ExtDesc &A, const ExtDesc &B) {
       return ExtValue(A) < ExtValue(B);
     });
 
   bool Changed = false;
   DEBUG(dbgs() << "Collected " << Extenders.size() << " extenders\n");
   for (unsigned I = 0, E = Extenders.size(); I != E; ) {
     unsigned B = I;

llvm/trunk/lib/Target/Hexagon/HexagonGenInsert.cpp

void HexagonGenInsert::buildOrderingBT(RegisterOrdering &RB,
   BitValueOrdering BVO(RB);
   RegisterCellLexCompare LexCmp(BVO, *CMS);
 
   using SortableVectorType = std::vector<unsigned>;
 
   SortableVectorType VRs;
   for (RegisterOrdering::iterator I = RB.begin(), E = RB.end(); I != E; ++I)
     VRs.push_back(I->first);
-  std::sort(VRs.begin(), VRs.end(), LexCmp);
+  llvm::sort(VRs.begin(), VRs.end(), LexCmp);
   // Transfer the results to the outgoing register ordering.
   for (unsigned i = 0, n = VRs.size(); i < n; ++i)
     RO.insert(std::make_pair(VRs[i], i));
 }
 
 inline bool HexagonGenInsert::isIntClass(const TargetRegisterClass *RC) const {
   return RC == &Hexagon::IntRegsRegClass || RC == &Hexagon::DoubleRegsRegClass;
 }

llvm/trunk/lib/Target/Hexagon/HexagonStoreWidening.cpp

bool HexagonStoreWidening::processBasicBlock(MachineBasicBlock &MBB) {
 
   createStoreGroups(MBB, SGs);
 
   auto Less = [] (const MachineInstr *A, const MachineInstr *B) -> bool {
     return getStoreOffset(A) < getStoreOffset(B);
   };
   for (auto &G : SGs) {
     assert(G.size() > 1 && "Store group with fewer than 2 elements");
-    std::sort(G.begin(), G.end(), Less);
+    llvm::sort(G.begin(), G.end(), Less);
 
     Changed |= processStoreGroup(G);
   }
 
   return Changed;
 }
 
 bool HexagonStoreWidening::runOnMachineFunction(MachineFunction &MFn) {

llvm/trunk/lib/Target/Hexagon/RDFDeadCode.cpp

bool DeadCodeElimination::erase(const SetVector<NodeId> &Nodes) {
   auto UsesFirst = [] (NodeAddr<RefNode*> A, NodeAddr<RefNode*> B) -> bool {
     uint16_t KindA = A.Addr->getKind(), KindB = B.Addr->getKind();
     if (KindA == NodeAttrs::Use && KindB == NodeAttrs::Def)
       return true;
     if (KindA == NodeAttrs::Def && KindB == NodeAttrs::Use)
       return false;
     return A.Id < B.Id;
   };
-  std::sort(DRNs.begin(), DRNs.end(), UsesFirst);
+  llvm::sort(DRNs.begin(), DRNs.end(), UsesFirst);
 
   if (trace())
     dbgs() << "Removing dead ref nodes:\n";
   for (NodeAddr<RefNode*> RA : DRNs) {
     if (trace())
       dbgs() << "  " << PrintNode<RefNode*>(RA, DFG) << '\n';
     if (DFG.IsUse(RA))
       DFG.unlinkUse(RA, true);

llvm/trunk/lib/Target/Hexagon/RDFGraph.cpp

void DataFlowGraph::buildPhis(BlockRefsMap &PhiM, RegisterSet &AllRefs,
   for (RegisterRef I : MaxDF)
     MaxRefs.push_back(MaxCoverIn(I, AllRefs));
 
   // Now, for each R in MaxRefs, get the alias closure of R. If the closure
   // only has R in it, create a phi a def for R. Otherwise, create a phi,
   // and add a def for each S in the closure.
 
   // Sort the refs so that the phis will be created in a deterministic order.
-  std::sort(MaxRefs.begin(), MaxRefs.end());
+  llvm::sort(MaxRefs.begin(), MaxRefs.end());
   // Remove duplicates.
   auto NewEnd = std::unique(MaxRefs.begin(), MaxRefs.end());
   MaxRefs.erase(NewEnd, MaxRefs.end());
 
   auto Aliased = [this,&MaxRefs](RegisterRef RR,
                                  std::vector<unsigned> &Closure) -> bool {
     for (unsigned I : Closure)
       if (PRI.alias(RR, MaxRefs[I]))

llvm/trunk/lib/Target/Hexagon/RDFLiveness.cpp

if (StmtA) {
         return false;
       // Both are phis. There is no ordering between phis (in terms of
       // the data-flow), so tie-break this via node id comparison.
       return A < B;
     }
   };
 
   std::vector<NodeId> Tmp(Owners.begin(), Owners.end());
-  std::sort(Tmp.begin(), Tmp.end(), Less);
+  llvm::sort(Tmp.begin(), Tmp.end(), Less);
 
   // The vector is a list of instructions, so that defs coming from
   // the same instruction don't need to be artificially ordered.
   // Then, when computing the initial segment, and iterating over an
   // instruction, pick the defs that contribute to the covering (i.e. is
   // not covered by previously added defs). Check the defs individually,
   // i.e. first check each def if is covered or not (without adding them
   // to the tracking set), and then add all the selected ones.
void Liveness::computeLiveIns() {
   LiveMap[&MF.front()].insert(DFG.getLiveIns());
 
   if (Trace) {
     // Dump the liveness map
     for (MachineBasicBlock &B : MF) {
       std::vector<RegisterRef> LV;
       for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I)
         LV.push_back(RegisterRef(I->PhysReg, I->LaneMask));
-      std::sort(LV.begin(), LV.end());
+      llvm::sort(LV.begin(), LV.end());
       dbgs() << printMBBReference(B) << "\t rec = {";
       for (auto I : LV)
         dbgs() << ' ' << Print<RegisterRef>(I, DFG);
       dbgs() << " }\n";
       //dbgs() << "\tcomp = " << Print<RegisterAggr>(LiveMap[&B], DFG) << '\n';
 
       LV.clear();
       const RegisterAggr &LG = LiveMap[&B];
       for (auto I = LG.rr_begin(), E = LG.rr_end(); I != E; ++I)
         LV.push_back(*I);
-      std::sort(LV.begin(), LV.end());
+      llvm::sort(LV.begin(), LV.end());
       dbgs() << "\tcomp = {";
       for (auto I : LV)
         dbgs() << ' ' << Print<RegisterRef>(I, DFG);
       dbgs() << " }\n";
 
     }
   }
 }