Index: lib/Transforms/Scalar/ADCE.cpp
===================================================================
--- lib/Transforms/Scalar/ADCE.cpp
+++ lib/Transforms/Scalar/ADCE.cpp
@@ -19,6 +19,7 @@
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
@@ -135,7 +136,7 @@
   SmallPtrSet<const Metadata *, 32> AliveScopes;
 
   /// Set of blocks with not known to have live terminators.
-  SmallPtrSet<BasicBlock *, 16> BlocksWithDeadTerminators;
+  SmallSetVector<BasicBlock *, 16> BlocksWithDeadTerminators;
 
   /// The set of blocks which we have determined whose control
   /// dependence sources must be live and which have not had
@@ -389,7 +390,7 @@
   // Mark the containing block live
   auto &BBInfo = *Info.Block;
   if (BBInfo.Terminator == I) {
-    BlocksWithDeadTerminators.erase(BBInfo.BB);
+    BlocksWithDeadTerminators.remove(BBInfo.BB);
     // For live terminators, mark destination blocks
     // live to preserve this control flow edges.
     if (!BBInfo.UnconditionalBranch)
@@ -481,7 +482,9 @@
   SmallVector<BasicBlock *, 32> IDFBlocks;
   ReverseIDFCalculator IDFs(PDT);
   IDFs.setDefiningBlocks(NewLiveBlocks);
-  IDFs.setLiveInBlocks(BlocksWithDeadTerminators);
+  SmallPtrSet<BasicBlock *, 16> S(BlocksWithDeadTerminators.begin(),
+                                  BlocksWithDeadTerminators.end());
+  IDFs.setLiveInBlocks(S);
   IDFs.calculate(IDFBlocks);
   NewLiveBlocks.clear();
 
Index: test/Transforms/ADCE/adce_random0.ll
===================================================================
--- /dev/null
+++ test/Transforms/ADCE/adce_random0.ll
@@ -0,0 +1,66 @@
+; RUN: opt -S -adce < %s
+; Exposed a non-deterministic bitcode
+; Run it N times eg.
+; for i in `seq 10`
+; do opt -ipsccp  -o out < %s
+; shasum out
+; done | sort -u | wc -l
+
+define void @foo() {
+bb:
+  br i1 false, label %bb1, label %bb22
+
+bb1:                                              ; preds = %bb
+  br i1 undef, label %bb2, label %bb20
+
+bb2:                                              ; preds = %bb1
+  br label %bb5
+
+bb5:                                              ; preds = %bb16, %bb2
+  br i1 undef, label %bb6, label %bb17
+
+bb6:                                              ; preds = %bb5
+  br i1 undef, label %bb7, label %bb16
+
+bb7:                                              ; preds = %bb6
+  br i1 undef, label %bb9, label %bb8
+
+bb8:                                              ; preds = %bb7
+  br i1 undef, label %bb9, label %bb10
+
+bb9:                                              ; preds = %bb8, %bb7
+  br label %bb13
+
+bb10:                                             ; preds = %bb8
+  br label %bb12
+
+bb12:                                             ; preds = %bb10
+  br label %bb13
+
+bb13:                                             ; preds = %bb12, %bb9
+  br label %bb14
+
+bb14:                                             ; preds = %bb13
+  br label %bb15
+
+bb15:                                             ; preds = %bb14
+  br label %bb16
+
+bb16:                                             ; preds = %bb15, %bb6
+  br label %bb5
+
+bb17:                                             ; preds = %bb5
+  br label %bb19
+
+bb19:                                             ; preds = %bb17
+  br label %bb21
+
+bb20:                                             ; preds = %bb1
+  br label %bb21
+
+bb21:                                             ; preds = %bb20, %bb19
+  br label %bb22
+
+bb22:                                             ; preds = %bb21, %bb
+  ret void
+}