Index: llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
===================================================================
--- llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
+++ llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
@@ -17,6 +17,7 @@
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/CodeGen/ISDOpcodes.h"
@@ -121,7 +122,7 @@
 
   /// Keeps track of dbg_values for which we have not yet seen the referent.
   /// We defer handling these until we do see it.
-  DenseMap<const Value*, DanglingDebugInfoVector> DanglingDebugInfoMap;
+  MapVector<const Value*, DanglingDebugInfoVector> DanglingDebugInfoMap;
 
 public:
   /// Loads are not emitted to the program immediately.  We bunch them up and
Index: llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
===================================================================
--- llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -1350,7 +1350,7 @@
 void SelectionDAGBuilder::resolveOrClearDbgInfo() {
   // Try to fixup any remaining dangling debug info -- and drop it if we can't.
   for (auto &Pair : DanglingDebugInfoMap)
-    for (auto &DDI : Pair.getSecond())
+    for (auto &DDI : Pair.second)
       salvageUnresolvedDbgValue(DDI);
   clearDanglingDebugInfo();
 }
Index: llvm/test/CodeGen/Generic/selection-dag-determinism.ll
===================================================================
--- /dev/null
+++ llvm/test/CodeGen/Generic/selection-dag-determinism.ll
@@ -0,0 +1,49 @@
+; RUN: llc -O2 -o %t1.o < %s
+; RUN: llc -O2 -o %t2.o < %s
+; RUN: llc -O2 -o %t3.o < %s
+; RUN: llc -O2 -o %t4.o < %s
+; RUN: llc -O2 -o %t5.o < %s
+; RUN: cmp %t1.o %t2.o
+; RUN: cmp %t1.o %t3.o
+; RUN: cmp %t1.o %t4.o
+; RUN: cmp %t1.o %t5.o
+
+; Regression test for nondeterminism introduced in https://reviews.llvm.org/D57694
+
+define void @test(i32 %x) !dbg !4 {
+entry:
+	call void @llvm.dbg.value(metadata void (i32)* @f1, metadata !6, metadata !DIExpression()), !dbg !8
+	call void @llvm.dbg.value(metadata void (i32)* @f2, metadata !7, metadata !DIExpression()), !dbg !8
+	%cmp = icmp eq i32 %x, 0, !dbg !8
+	br i1 %cmp, label %cleanup, label %if.end
+
+	if.end:
+	%tobool = icmp eq i32 0, 0
+	%a = select i1 %tobool, void (i32)* @f1, void (i32)* null, !dbg !8
+	%b = select i1 %tobool, void (i32)* @f2, void (i32)* null, !dbg !8
+	call void %a(i32 %x)
+	call void %b(i32 %x)
+	unreachable
+
+	cleanup:
+	ret void
+}
+
+declare void @f1(i32)
+declare void @f2(i32)
+
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang", runtimeVersion: 0, emissionKind: FullDebug)
+!1 = !DIFile(filename: "test.cc", directory: "")
+!2 = !{}
+!3 = !{i32 2, !"Debug Info Version", i32 3}
+!4 = distinct !DISubprogram(name: "test", scope: !1, file: !1, type: !5, unit: !0)
+!5 = !DISubroutineType(types: !2)
+!6 = !DILocalVariable(name: "a", scope: !4, file: !1, type: !9)
+!7 = !DILocalVariable(name: "b", scope: !4, file: !1, type: !9)
+!8 = !DILocation(scope: !4)
+!9 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !5, size: 64)