[Hexagon] Use stable sort for HexagonShuffler to remove non-deterministic ordering

[mgrang]

Summary

This fixes failures in the following tests uncovered by D39245:

LLVM :: CodeGen/Hexagon/args.ll
LLVM :: CodeGen/Hexagon/constp-extract.ll
LLVM :: CodeGen/Hexagon/expand-condsets-basic.ll
LLVM :: CodeGen/Hexagon/gp-rel.ll
LLVM :: CodeGen/Hexagon/packetize_cond_inst.ll
LLVM :: CodeGen/Hexagon/simple_addend.ll
LLVM :: CodeGen/Hexagon/swp-stages4.ll
LLVM :: CodeGen/Hexagon/swp-vmult.ll
LLVM :: CodeGen/Hexagon/swp-vsum.ll
LLVM :: MC/Hexagon/align.s
LLVM :: MC/Hexagon/asmMap.s
LLVM :: MC/Hexagon/dis-duplex-p0.s
LLVM :: MC/Hexagon/double-vector-producer.s
LLVM :: MC/Hexagon/inst_select.ll
LLVM :: MC/Hexagon/instructions/j.s

[mgrang]

In HexagonShuffler.h, the lessCore and lessCVI comparators sort insts based on the number of units set. Now, two insts can have the same units set so their relative ordering is not defined.
We could add an index field as a tie-breaker but that would mean changes to function APIs which I felt could be an overkill. Hence, I went with the simpler approach to just use stable_sort instead.
Please let me know your thoughts on this.

[mgrang]

Ping for reviews please.

llvm/trunk/lib/Target/Hexagon/MCTargetDesc/HexagonShuffler.cpp

for (unsigned int i = 0; i < MAX_JUMP_SLOTS; ++i) {
         continue;
 
       // both valid for this configuration, set new slot rules
       PacketSave = Packet;
       foundBranches[0]->Core.setUnits(jumpSlots[i].first);
       foundBranches[1]->Core.setUnits(jumpSlots[i].second);
 
       HexagonUnitAuction AuctionCore(reservedSlots);
-      std::sort(begin(), end(), HexagonInstr::lessCore);
+      std::stable_sort(begin(), end(), HexagonInstr::lessCore);
 
       // see if things ok with that instruction being pinned to slot "slotJump"
       bool bFail = false;
       for (iterator I = begin(); I != end() && !bFail; ++I)
         if (!AuctionCore.bid(I->Core.getUnits()))
           bFail = true;
 
       // if yes, great, if not then restore original slot mask
bool HexagonShuffler::check() {
   if (jumps <= 1 && !bOnlySlot3 && pSlot3Cnt == 1 && slot3ISJ != end()) {
     validateSlots = true;
     // save off slot mask of instruction marked with A_PREFER_SLOT3
     // and then pin it to slot #3
     unsigned saveUnits = slot3ISJ->Core.getUnits();
     slot3ISJ->Core.setUnits(saveUnits & slotThree);
 
     HexagonUnitAuction AuctionCore(reservedSlots);
-    std::sort(begin(), end(), HexagonInstr::lessCore);
+    std::stable_sort(begin(), end(), HexagonInstr::lessCore);
 
     // see if things ok with that instruction being pinned to slot #3
     bool bFail = false;
     for (iterator I = begin(); I != end() && !bFail; ++I)
       if (!AuctionCore.bid(I->Core.getUnits()))
         bFail = true;
 
     // if yes, great, if not then restore original slot mask
     if (!bFail)
       validateSlots = false; // all good, no need to re-do auction
     else
       for (iterator ISJ = begin(); ISJ != end(); ++ISJ) {
         MCInst const &ID = ISJ->getDesc();
         if (HexagonMCInstrInfo::prefersSlot3(MCII, ID))
           ISJ->Core.setUnits(saveUnits);
       }
   }
 
   // Check if any slot, core or CVI, is over-subscribed.
   // Verify the core slot subscriptions.
   if (validateSlots) {
     HexagonUnitAuction AuctionCore(reservedSlots);
 
-    std::sort(begin(), end(), HexagonInstr::lessCore);
+    std::stable_sort(begin(), end(), HexagonInstr::lessCore);
 
     for (iterator I = begin(); I != end(); ++I)
       if (!AuctionCore.bid(I->Core.getUnits())) {
         reportError(Twine("invalid instruction packet: slot error"));
         return false;
       }
   }
   // Verify the CVI slot subscriptions.
-  std::sort(begin(), end(), HexagonInstr::lessCVI);
+  std::stable_sort(begin(), end(), HexagonInstr::lessCVI);
   // create vector of hvx instructions to check
   HVXInstsT hvxInsts;
   hvxInsts.clear();
   for (iterator I = begin(); I != end(); ++I) {
     struct CVIUnits inst;
     inst.Units = I->CVI.getUnits();
     inst.Lanes = I->CVI.getLanes();
     if (inst.Units == 0)
for (unsigned nSlot = 0, emptySlots = 0; nSlot < HEXAGON_PACKET_SIZE;
           ++ISJ;
         else
           // Calculate the weight of the slot.
           slotWeight += ISK->Core.setWeight(HEXAGON_PACKET_SIZE - nSlot - 1);
 
       if (slotWeight)
         // Sort the packet, favoring source order,
         // beginning after the previous slot.
-        std::sort(ISJ, Packet.end());
+        std::stable_sort(ISJ, Packet.end());
       else
         // Skip unused slot.
         ++emptySlots;
     }
 
   for (iterator ISJ = begin(); ISJ != end(); ++ISJ)
     DEBUG(dbgs().write_hex(ISJ->Core.getUnits()); if (ISJ->CVI.isValid()) {
       dbgs() << '/';