Fix nondeterminism introduced in r353954

[kongyi]

Summary

DenseMap iteration order is not guaranteed, use MapVector instead.

Fix by srhines.

[srhines]

@jmorse can I get your approval on this CL before we submit it? Thanks.

[jmorse]

LGTM, many thanks for the find and fix!

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

 
 #ifndef LLVM_LIB_CODEGEN_SELECTIONDAG_SELECTIONDAGBUILDER_H
 #define LLVM_LIB_CODEGEN_SELECTIONDAG_SELECTIONDAGBUILDER_H
 
 #include "StatepointLowering.h"
 #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"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/CodeGen/SelectionDAGNodes.h"
 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/CodeGen/ValueTypes.h"
 #include "llvm/IR/CallSite.h"
public:
     unsigned getSDNodeOrder() { return SDNodeOrder; }
   };
 
   /// Helper type for DanglingDebugInfoMap.
   typedef std::vector<DanglingDebugInfo> DanglingDebugInfoVector;
 
   /// 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
   /// then emit token factor nodes when possible.  This allows us to get simple
   /// disambiguation between loads without worrying about alias analysis.
   SmallVector<SDValue, 8> PendingLoads;
 
   /// State used while lowering a statepoint sequence (gc_statepoint,

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

bool SelectionDAGBuilder::handleDebugValue(const Value *V, DILocalVariable *Var,
   }
 
   return false;
 }
 
 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();
 }
 
 /// getCopyFromRegs - If there was virtual register allocated for the value V
 /// emit CopyFromReg of the specified type Ty. Return empty SDValue() otherwise.
 SDValue SelectionDAGBuilder::getCopyFromRegs(const Value *V, Type *Ty) {
   DenseMap<const Value *, unsigned>::iterator It = FuncInfo.ValueMap.find(V);

llvm/test/CodeGen/Generic/selection-dag-determinism.ll

+; 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)