Index: lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
===================================================================
--- lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
+++ lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
@@ -163,8 +163,8 @@
 // types, then update all the second type to the first type
 typedef DenseMap<Value *, Value *> DefiningValueMapTy;
 typedef DenseSet<Value *> StatepointLiveSetTy;
-typedef DenseMap<AssertingVH<Instruction>, AssertingVH<Value>>
-  RematerializedValueMapTy;
+typedef SmallVector<std::pair<AssertingVH<Instruction>, AssertingVH<Value>>, 32>
+    RematerializedValueMapTy;
 
 struct PartiallyConstructedSafepointRecord {
   /// The set of values known to be live across this safepoint
@@ -1961,10 +1961,17 @@
   const unsigned int ChainLengthThreshold = 10;
 
   // Record values we are going to delete from this statepoint live set.
-  // We can not di this in following loop due to iterator invalidation.
+  // We can't do this in a single loop due to iterator invalidation.
   SmallVector<Value *, 32> LiveValuesToBeDeleted;
 
-  for (Value *LiveValue: Info.LiveSet) {
+  // Stabilize iteration order over LiveSet. We want deterministic naming of
+  // the rematerialized values.
+  SmallVector<Value *, 64> OrderedLiveSet;
+  OrderedLiveSet.insert(OrderedLiveSet.end(), Info.LiveSet.begin(),
+                        Info.LiveSet.end());
+  std::sort(OrderedLiveSet.begin(), OrderedLiveSet.end(), order_by_name);
+
+  for (Value *LiveValue: OrderedLiveSet) {
     // For each live pointer find it's defining chain
     SmallVector<Instruction *, 3> ChainToBase;
     assert(Info.PointerToBase.count(LiveValue));
@@ -2048,7 +2055,7 @@
       Instruction *InsertBefore = CS.getInstruction()->getNextNode();
       assert(InsertBefore);
       Instruction *RematerializedValue = rematerializeChain(InsertBefore);
-      Info.RematerializedValues[RematerializedValue] = LiveValue;
+      Info.RematerializedValues.emplace_back(RematerializedValue, LiveValue);
     } else {
       InvokeInst *Invoke = cast<InvokeInst>(CS.getInstruction());
 
@@ -2062,8 +2069,10 @@
       Instruction *UnwindRematerializedValue =
           rematerializeChain(UnwindInsertBefore);
 
-      Info.RematerializedValues[NormalRematerializedValue] = LiveValue;
-      Info.RematerializedValues[UnwindRematerializedValue] = LiveValue;
+      Info.RematerializedValues.emplace_back(NormalRematerializedValue,
+                                             LiveValue);
+      Info.RematerializedValues.emplace_back(UnwindRematerializedValue,
+                                             LiveValue);
     }
   }