Fix nondeterminism introduced in r353954

DenseMap iteration order is not guaranteed, use MapVector instead.

Fix provided by srhines.

Differential Revision: https://reviews.llvm.org/D59807

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@356988 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 52 insertions, 2 deletions

diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
index edb05fb6bcf..b1a7a13f5b5 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -1349,7 +1349,7 @@ bool SelectionDAGBuilder::handleDebugValue(const Value *V, DILocalVariable *Var,
 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();
 }
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
index e84214dbf5e..e0d397c2d41 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
+++ b/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 @@ class SelectionDAGBuilder {
 
   /// 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
diff --git a/test/CodeGen/Generic/selection-dag-determinism.ll b/test/CodeGen/Generic/selection-dag-determinism.ll
new file mode 100644
index 00000000000..d9bc90f9ee5
--- /dev/null
+++ b/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)