Fix nondeterminism in debuginfo generation

[yanok]

Summary

Changes from commit 1db137b1859692ae33228c530d4df9f2431b2151
added iteration over hash map that can result in non-deterministic
order. Fix that by using a SmallMapVector to preserve the order.

[StephenTozer]

LGTM! Good catch on this one, I thought I'd removed all the DenseMap iteration errors but I guess this one slipped by. There's a small suggestion in the inline comments, but feel free to ignore it - it's more of a preference than a rule. Shouldn't need a test either since this patch is trivial and solves a determinism issue, so this should be fine as-is.

llvm/lib/CodeGen/RegAllocFast.cpp

449–451

Small suggestion - some prefer the above form for brevity, though personally I'm fine with either.

[nikic]

llvm/lib/CodeGen/RegAllocFast.cpp

436

Maybe just switch this to a SmallMapVector?

[yanok]

Just use SmallMapVector as suggested.

[yanok]

llvm/lib/CodeGen/RegAllocFast.cpp

436

Yes, that would have the same effect. Thanks for your suggestion, I've modified the patch.

449–451

Thanks for the suggestion, I'll note that. For this specific patch I think switching to SmallMapVector is a simpler way forward though.

llvm/lib/CodeGen/RegAllocFast.cpp

 /// time, attempting to keep values in registers and reusing registers as
 /// appropriate.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/IndexedMap.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/SparseSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
void RegAllocFast::spill(MachineBasicBlock::iterator Before, Register VirtReg,
   ++NumStores;
 
   MachineBasicBlock::iterator FirstTerm = MBB->getFirstTerminator();
 
   // When we spill a virtual register, we will have spill instructions behind
   // every definition of it, meaning we can switch all the DBG_VALUEs over
   // to just reference the stack slot.
   SmallVectorImpl<MachineOperand *> &LRIDbgOperands = LiveDbgValueMap[VirtReg];
-  SmallDenseMap<MachineInstr *, SmallVector<const MachineOperand *>>
+  SmallMapVector<MachineInstr *, SmallVector<const MachineOperand *>, 2>
       SpilledOperandsMap;
   for (MachineOperand *MO : LRIDbgOperands)
     SpilledOperandsMap[MO->getParent()].push_back(MO);
   for (auto MISpilledOperands : SpilledOperandsMap) {
     MachineInstr &DBG = *MISpilledOperands.first;
     MachineInstr *NewDV = buildDbgValueForSpill(
         *MBB, Before, *MISpilledOperands.first, FI, MISpilledOperands.second);
     assert(NewDV->getParent() == MBB && "dangling parent pointer");
     (void)NewDV;
     LLVM_DEBUG(dbgs() << "Inserting debug info due to spill:\n" << *NewDV);
 
     if (LiveOut) {
       // We need to insert a DBG_VALUE at the end of the block if the spill slot
       // is live out, but there is another use of the value after the
       // spill. This will allow LiveDebugValues to see the correct live out
       // value to propagate to the successors.
       MachineInstr *ClonedDV = MBB->getParent()->CloneMachineInstr(NewDV);
       MBB->insert(FirstTerm, ClonedDV);
       LLVM_DEBUG(dbgs() << "Cloning debug info due to live out spill\n");
     }
 
     // Rewrite unassigned dbg_values to use the stack slot.
     // TODO We can potentially do this for list debug values as well if we know