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

445–447

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

[nikic]

llvm/lib/CodeGen/RegAllocFast.cpp

435

Maybe just switch this to a SmallMapVector?

[yanok]

Just use SmallMapVector as suggested.

[yanok]

llvm/lib/CodeGen/RegAllocFast.cpp

435

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

445–447

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

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 *>>
       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);
+  // We can't iterate over SpilledOperandsMap directly as it can result in
+  // non-deterministic ordering. Instead we iterate over LRIDbgOperands again
+  // but keep track of already processed instructions.
+  SmallDenseSet<MachineInstr *> ProcessedSet;
+  for (MachineOperand *MO : LRIDbgOperands) {
+    auto DBG = MO->getParent();
+    if (ProcessedSet.contains(DBG))
+      continue;
+    ProcessedSet.insert(DBG);
+    MachineInstr *NewDV =
+        buildDbgValueForSpill(*MBB, Before, *DBG, FI, SpilledOperandsMap[DBG]);
     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
     // how the dbg_values are getting unassigned.
-    if (DBG.isNonListDebugValue()) {
-      MachineOperand &MO = DBG.getDebugOperand(0);
+    if (DBG->isNonListDebugValue()) {
+      MachineOperand &MO = DBG->getDebugOperand(0);
       if (MO.isReg() && MO.getReg() == 0) {
-        updateDbgValueForSpill(DBG, FI, 0);
+        updateDbgValueForSpill(*DBG, FI, 0);
       }
     }
   }
   // Now this register is spilled there is should not be any DBG_VALUE
   // pointing to this register because they are all pointing to spilled value
   // now.
   LRIDbgOperands.clear();
 }